TSP路線建構法
Construction Heuristics
|
路線建構是根據某種法則將點逐一加入路線，最後形成一個完整的路線。 通常產生的路線仍有不少缺點，因此還需要後續的路線改善。以下介紹兩種常見的路線構建法： 近鄰法(nearest neighbor)與插入法(insertion) 。
Nearest Neighbor 推銷員從某個城鎮出發，永遠選擇前往最近且尚未去過的城鎮，最後再返回原先的出發點。這方法簡單，也許是多數人的直覺做法，但是近鄰法的短視使其表現非常不好，通常後段的路程會非常痛苦，下面的Java小程式足可說明： |
需要Microsoft VM，剛開始速度會有點龜慢，請忍耐
Insertion
| 另一種路線建構的方法是先產生連接部分點的子路線，再根據某種法則將其他的點逐一加入路線。下面的Java程式先針對外圍的點建構子路線，然後Cheapest Insertion是從剩餘的點裡面評估何者加入後路線總長度增加的幅度最小，再將這個點加入路線。Farthest Insertion是從剩餘的點裡面選擇距離子路線最遠的點，有點先苦後甘的滋味。 |
本網頁參考自http://itp.nat.uni-magdeburg.de/~mertens/TSP/node2.html
原作者: Stephan Mertens