那麼呢,就讓我們來試試看 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 哪!