1.0Camdemy1.0http://media.usc.edu.twBranch-and-Bound TSP Part-2http://media.usc.edu.tw/user/http://media.usc.edu.tw/sysdata/doc/6/62ebf25dadf0b373/thumb_l.jpg360640<iframe width='720' height='405' id='ccShare3041' frameborder='0' src='http://media.usc.edu.tw/media/e/3041' allowfullscreen></iframe>video72040518:20Arc(6, 4) is changed to be infinity since it cannot be included in the solution.Without Arc(4, 6), the lower bound is 96+32=12801Without List:Arc(1, 2) = 9+1Arc(2, 1) = 17+0Arc(3, 5) = 1+17Arc(5, 1) = 4+0Arc(6, 1) = 8+0Arc(7, 2) = 0+1Arc(7, 3) = 0+8Arc(7, 4) = 0+402Arc(5, 3) is changed to be infinity since it cannot be included in the solution.Without Arc(3, 5), the lower bound is 99+18=11703Step 2.1: Choose Arc(2, 1) and Arc(1, 2) is changed to be infinity since it cannot be included in the solution.Step 2.1: Without Arc(2, 1), the lower bound is 99+26=125Step 3: With Arc(2, 1), total cost reduced: 99 + 9 + 4 = 112 (new lower bound).04Arc(1, 2) is changed to be infinity since it cannot be included in the solution.Without Arc(2, 1), the lower bound is 99+26=12505Step 2.1: Choose Arc(1, 4) and Arc(4, 1) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(1, 4), the lower bound is 112+41=153Step 3: With Arc(1, 4), total cost reduced: 112 + 14 = 126 (new lower bound).06Step 2.1: Choose Arc(1, 4) and Arc(4, 1) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(1, 4), the lower bound is 112+41=153Step 3: With Arc(1, 4), total cost reduced: 112 + 14 = 126 (new lower bound).07Without Arc(1, 4), the lower bound is 112+41=15308Step 2.1: Choose Arc(6, 7) and Arc(7, 6) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(6, 7), the lower bound is 126+15=141Step 3: With Arc(6, 7), total cost reduced: 126 + 0 = 126 (new lower bound).09L. B. = 99010Step 2.1: Choose Arc(5, 2) and Arc(2, 5) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(5, 2), no way to go, no solution!!!Step 3: With Arc(5, 2), total cost reduced: 126 + 0 = 126 (new lower bound).011L. B. = 99012Step 2.1: Choose Arc(5, 2) and Arc(2, 5) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(5, 2), no way to go, no solution!!!Step 3: With Arc(5, 2), total cost reduced: 126 + 0 = 126 (new lower bound).013Step 4: The decision tree:014Step 4: The decision tree:015fs1280x720720x4041280x720http://media.usc.edu.tw/sysdata/doc/6/62ebf25dadf0b373/thumb.jpghttp://media.usc.edu.tw/sysdata/doc/6/62ebf25dadf0b373/cover.jpghttp://media.usc.edu.tw/sysdata/doc/6/62ebf25dadf0b373/video/thumbs/storyboard.jpghttp://media.usc.edu.tw/sysdata/doc/6/62ebf25dadf0b3731