那麼呢，就讓我們來試試看 implement 這個 greedy algorithm 吧。
好，所以做法呢，其實跟之前的也都差不多，反正無非就是幾個流程。
流程 1 一般來說，就是讀取相關的資料或者是提供相關的資料。
一般都是這樣嘛。
接著呢，就是要準備一些前置需要的 資訊，那再來呢，就是我們主要的演算吧，通常有一個 main loop。
然後最後呢，就把結果印出來。
一般來說，不外乎就是這幾個步驟。
那當然，題目變複雜了以後，你的演算法當然也會跟著 變得更複雜。
好，不過精神上呢，還是都是相通的。
好，所以首先請把資訊告訴我們吧，我們要先設定這個 problem
instance，所以呢，我們要先設置一個變數叫做 number of locations。
number location 有 dst 這個 list 是一個二維的
list，這個 list 裡面呢，我們讓 dst [i] [j]
表示 i 跟 j 這兩個地點之間的 distance，所以現在我們題目上
看到的這一個，好，直接寫在程式碼裡面的這個二維的 list
呢，我們可以 大概地想像一下就是說哦，它有五個點。
那我們呢，在這裡就把編號為 01234 好了。
好，編號 0 的點，0 到 0 的距離有沒寫成
0？ 即使寫成任何其他數字也無所謂，因為不會用到，然後呢，0 到 1 的距離是
9， 0 到 1 的距離是 9 就表示移動過來，大概要九分鐘的意思。
0 到 2 呢是 6、 0 到 3 呢是 7，0 到 4 是 10，是這個意思。
那麼我們今天呢，因為我們想要做的是雙向的距離是一樣的，所以你可以看到這個 4
那裡就是 4，這裡 1 那裡就是 1，好，這基本上這個二維的清單呢是對稱的。
那如果你今天要處理的題目不是對稱的，那很明顯你就做得到。
你就去把數字自己反過來寫就好了。
從 3 要到 2 的距離，跟從
2 要到 3 的距離，你可以設成不一樣，然後你自己知道你是怎麼設的就可以啦。
好，所以呢，這個圖實際上呢，就有很多很多條線，那我們就不一個一個把它畫出來了。
好，那你知道這一段程式碼，就是在設定說
我有五個點，而且它們之間的距離關係，用 dst 這個清單來表示。
那特別強調一下，這是一個二維的清單。
好，所以我們基本上 要存取一個距離資訊的時候呢，都要使用這個 dst [i] [j] 這樣子的方式來做。
那最後呢，我們要指定的一個起點嘛。
好 那就說 origin 是 0，我們想要從 0 這個地方出發繞一圈。
接著呢，我們要來準備兩個 list，這兩個 list
叫做 tour 跟 unvisited，基本上就是等一下要裝答案的東西啦。
所以在 tour 裡面 一開始的時候呢，它只有一個東西，只有一個數字，就是
origin 的 index，等一下會在回圈子中，慢慢長、 慢慢長
每一次我決定下一步我要去哪裡的時候，我就會把下一步的 next location
存到 tour 裡面去，最後我看 tour 我就會知道我要怎麼走。
然後呢，tourLen 是這個 tour length 嘛，就是表示我
整個走一圈，用我們的演算法要花多長的距離，這樣子。
那再來呢，是一個叫做 unvisited 的 list。
這個 list 的用途就是因為我每一個迴圈、
每一步 要往下走的時候呢，我是走去目前還沒有去過的點
之中挑一個，所以我必須隨時記錄目前還沒去過的是哪一些點。
好，所以比如說這裡，這個 unvisited 我要把它做出來，那我需要這幾個步驟。
先給它一個空的 list，接著呢，我要跑這個迴圈，在
unvisited 裡面把 0 1 2 3 4 一個一個地 加進去。
好，所以這個迴圈就會跑 numlocation 那麼多次。
這些數字一個一個看進去，但最後呢，我要記得把 origin 刪掉，我要把 origin 刪掉。
因為 origin 是第一個點嘛，它已經去過了，它並不是一個還沒去過的點。
好，所以我需要做這件事情。
好，所以這個是 remove 函數，list 的 remove 函數也跟大家展示一下它的用途。
好，那我們現在已經準備好了，我們的這個迴圈呢，基本上必須要跑 numLoc
-1 的更多個 iteration。
因為我如果有五個點的話，我必須要從原點出發， 也就是我的第一個點，我這條路的第一個點已經決定了。
接下來我要選四次就好了，那嚴格講起來，你只需要選 三次啦，因為你到最後一個點的時候，其實已經別無選擇了。
好，那 anyway 就寫說我們需要 numLoc-1 這麼多次。
在每一個iteration裡面呢 我們要去 check distance，什麼
distance？就是從目前的點到還沒有去過的點 一個一個檢查，去找出最近的，還沒有visit 過的點。
然後就移過去，這樣。
好，那我們來看一下這個演算法。
我們呢，需要兩個變數，一個叫 current，一個叫 next。
current 就是在這一圈之中，我目前站在哪； 而 next 就是我等一下要走過去的地方。
所以在迴圈 開始跑之前，我先把 current 設成 origin，因為一開始是從原點出發的嘛。
接下來的每一圈，我一開始不知道我要去哪裡，所以我先把這個去 去那裡的
distance 先設成一個很大的數，你也可以設成1000萬了，反正你確定夠大就好。
然後呢，對於每一個還沒有去過的點 去計算
current 到它要跑多遠。
好，對於這個距離，拿來跟目前的最短距離比 如果比較短，那就
update，跟之前看過的很多例子都很像。
好，於是呢，經過了這一番這個演算、 這個迴圈
我們就可以知道 next 會是我們要去的點。
那麼呢，我們就把 next 從 unvisited 裡面刪掉。
把它加到 tour 裡面去，所以在 univisted 裡面，我們要去 remove next 那個東西。
而在 tour 裡面呢，我們要把 next 加進去，對吧。
這樣子我 下一圈在跑的時候，這個還沒去過的點的清單就會少掉那個東西。
而我就目前要去的路徑就會 加一個 next。
也就是我知道，哦，下一步是去那、 下一步是去那。
然後距離把它加起來，但現在整個這個步驟都已經
完成了，我跑下一圈之前就是記得我要移過去 current 這個地方。
所以呢，我就是把 current assign 成 next，那麼下一圈迴圈要開始跑的時候
我就會從我剛剛決定要去的地方開始做下一輪的搜尋，大概是這樣。
好，那麼最後呢，就把結果印出來就可以了，那最後印結果之前，我還
得要記得，我們這樣子從 01234
我們這樣子繞了一圈以後 最後我要把 origin
再加回去我們的這一圈裡面，也就是加進 tour 這個 solution 的 list 的最後面。
當然，這個從最後的 current 移回去 的這個距離也是要加的。
好，那所以我們就加了這個動作。
然後呢，最後我們就可以把結果印出來了。
好，那我們來試試看。
那麼呢，程式碼在這裡已經這個複製貼上、 弄好了，
那麼我們在這個地方呢，我們先稍微地試一下，我們現在做的事情就是說
我其實實際上應該要使用讓使用者輸入那個地圖資訊
的做法，那我們等一下的影片會再跟大家介紹。
那為了簡單起見，我們先看這個部分就好，就是我已經把 資訊全部都寫入我們這個程式碼裡面了。
然後呢，我們把 origin 設好，然後這裡是我們剛剛說的，我們要去設定
tour 和 unvisited 這兩個 list，然後呢，這裡先 print 出來看一下。
當你在寫你的演算法的時候，你肯定會時不時地就把東西 print 出來看一下，
而不會一直寫、 一直寫、 一直寫、 一直寫，因為這樣很容易出錯嘛，你隨時要檢查一下才好。
然後呢，是演算法。
好，這個就是如我們剛剛所說的，我們要先去找哪一個點是
我們的目標，接著我們要移過去，那我們也把暫時的結果
每一個迴圈跑出來的結果，都暫時看一下，然後 最後我們就可以把結果完成，然後印出來，好。
那麼呢，我們可以看到，跑出來結果大概像這個樣子。
這個意思就是說啊，我們從 0 這個點
出發，先去 4、 再去2、 再去3、 再去 1，最後回到 0。
每加一個點的時候呢，我們把移動到那裡的總距離加進去，所以呢，到 4
需要 4 單位， 從 4 再到 2，一共要 5 單位，428 一共要 8 單位，以此類推。
因此最後我們演算法在這個 instance 上就給我們26的總距離。
那 26 這個總距離是最佳解嗎？這個我們就不回答了。
大家有興趣自己畫畫看。
是也好、 不是也好，其實不是、 沒有什麼太大的影響。
但總之，透過我們的這樣子的程式我們就可以 implement
我們剛剛的演算法，那麼呢，在實務上，你就可以得到一個 solution。
而且通常是還不錯的 solution 哪！
孔令傑副教授 (Associate Professor)
