重念一次早該補起來的「資料結構與演算法」。這篇筆記下 旅行推銷員問題。
![[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74](https://smlpoints.com/wp-content/uploads/notes-theideaofalgorithm-javascript-1.jpg "[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74")
課程相關資訊
[連結]：https://hiskio.com/en/courses/572/lectures/30017
本篇範圍：Chapter 13
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
Travelling Salesman Problem ( TSP )
在列表中的兩兩城市的最短距離都是已知的，如何找到滿足以下條件的最短路徑？
1. 每個城市僅能拜訪一次，而且每個城市一定都要去
2. 旅程結束，需回到最一開始出發的城市
其實本質上，就是一個 Hamilton Cycle 問題。每個城市就是一個節點，然後彼此之間有連結。換言之，你需要找出 Hamilton Cycle 中距離最短的 ( 最佳解 )
它是一個最佳解問題，可使用 Branch and Bond 來解
