Branch-and-Bound TSP Part-2
  • 18:20,
  • 799 views,
  • 2021-05-19,
  • 上傳者: 系統管理者,
  •  0
 
 
 
  • 1. Arc(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=128
  • 2. Without 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+4
  • 3. Arc(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=117
  • 4. Step 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).
  • 5. Arc(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=125
  • 6. Step 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).
  • 7. Step 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).
  • 8. Without Arc(1, 4), the lower bound is 112+41=153
  • 9. Step 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).
  • 10. L. B. = 99
  • 11. Step 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).
  • 12. L. B. = 99
  • 13. Step 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).
  • 14. Step 4: The decision tree:
  • 15. Step 4: The decision tree:
1/15
Volume
  • 速度 :
  • 畫質 :
  • 播放設定
00:00/18:20
00:00/00:44
 
 
    訪客如要回應,請先 登入
      解析度 : x
      資料夾 :
      發表時間 :
      2021-05-19 15:01:34
      觀看數 :
      799
      長度 :
      18:20
      發表人 :
      系統管理者
      部門 :
      www
      QR Code :