加分題：請用爬山演算法求解旅行推銷員 TSP 問題

[ccckmit]

• 旅行推銷員 TSP 問題

更大的測試資料

• TSP : Data for the Traveling Salesperson Problem

提示：

後來我想到一個比 swap 更好的方法，就是對一個 circle 取兩個點，然後將其夾住的鏈翻轉過來。

資料結構可用一個整數陣列 n[0..k-1] 表示，例如 0=>1=>2=>3=>0 的圖可用以下陣列表示：

n[0] n[1] n[2] n[3]
  1    2    3    0

表示成 Graph 如下：

  graph TD;
      0-->1;
      1-->2;
      2-->3;
      3-->0;

若我們挑出 0=>1 與 2=>3 兩個邊交換，那就會變成

n[0] n[1] n[2] n[3]
  2    3    0    1

表示成 Graph 如下：

  graph TD;
      0-->2;
      2-->3;
      3-->1;
      1-->0;

重點是鄰居可以用：《對一個 circle 取兩個點，然後將其夾住的鏈翻轉過來》的方法處理。

也就是：

a<=>b
c<=>d

調過來後，變成

a<=>d
b<=>c

其餘結構不變，如下圖所示

[FUYUHSUAN]

https://github.com/FUYUHSUAN/ai110b/tree/master/HW/2022_03_10

[austin362667]

https://gist.github.com/austin362667/b90c2ef7884bdfe9d0f2a6fd48ed832e

[NubletZ]

資工三 110810538 魏美亞 notes code

[ChiaYunn]

110810535

[07Nick-kciN21]

110810518徐仁鴻 作業