朱道元的郵路安排問題也涉及到路徑，運(yùn)量。所以有必要學(xué)習(xí)开缎。TSP問題涉及到的是最短圈問題，跟路徑變量聯(lián)系到一起了油航。
里面第一個(gè)基礎(chǔ)問題時(shí)哈密爾頓圈。
那么怎么對(duì)哈密爾頓圈建模怀浆？
目標(biāo)：最短圈
約束：給個(gè)點(diǎn)都走過。
變量：01路段路徑變量
Paste_Image.png
下面校對(duì)
- 很符合TSP的定義（旅行商問題）
- TSP問題是一個(gè)NPC/NP-hard問題怕享。
- 假設(shè)有一個(gè)旅行商人要拜訪N個(gè)城市执赡，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次函筋，而且最后要回到原來出發(fā)的城市沙合。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。一個(gè)目標(biāo)跌帐，一個(gè)約束
- 哈密頓通路（回路）與哈密頓圖 （Hamilton圖） 通過圖G的每個(gè)結(jié)點(diǎn)一次首懈，且僅一次的通路（回路），就是哈密頓通路（回路）. 存在哈密頓回路的圖就是哈密頓圖·
- 旅行商問題(TSP)
- 數(shù)學(xué)規(guī)劃模型
5.1 漢密爾頓圈的約束及決策變量
約束要防止子圈的形成谨敛。
Paste_Image.png
目標(biāo)函數(shù)很簡單
約束條件怎么定義
我是從邊的條數(shù)上約束的究履，不對(duì)。
從節(jié)點(diǎn)上約束脸狸。每走一步最仑，邊的條數(shù)上上都要約束。
建模上還是有點(diǎn)嫩炊甲。
