Re: [問題] 小題目：各點之間的最小連結步數

看板Fortran作者yin0416 (冷色鉛筆)時間15年前 (2009/12/08 11:43)推噓1(1推 0噓 2→)

留言3則, 1人參與討論串4/6 (看更多)

首先非常感謝mantour大大的解釋：另外在此鄭重的向mantour道個歉，當天投水球問問題時，我的行為顯得突兀冒失...... 希望mantour大人大量不予計較。最後提出我對這個演算法的發現與疑問，當i,j,k任兩個為相同時，其路徑長 D(i,j) 不會產生任何改變，所以可以跳過這些情況，不必去考慮！雖然我現下瞭解這個演算法中，每個迴圈的作用為何，但我很疑惑的是，為什麼最外層Ｋ的順序不影響最後之結果？這演算法其先運算的結果可能會在後運算時再次的被拿來運用。例如，依迴圈順序 (a).k=3,j=2,i=5的執行順序是在 (b).k=4,j=2,i=3之前，假設(b)的情況是V3與V2之間可以透過V4來減少距離，即　V3-><-V2 = inf　可由　V3-->V4-->V2 = 2　來取代。但若(a)的情況是V5與V2之間無法透過V3來減少距離，且V5與V2之間無直接連結，即　V5-><-V2 =inf　且(b)的情況仍未執行，所以　V3-><-V2 = inf ，在這樣的情形下，我們得到　V5-->V3-><-V2 = inf　，而非真實情況下的　V5-->V3-->V4-->V2 = 3 。以上是我自以為合理的推演，看起來最外層K的執行順序會影響到最終的執行結果，但我實際上操作的結果卻沒有這樣的發現，這中間是否還有什麼我沒弄懂的地方，希望瞭解的大大可以為在下指點迷津！謝謝各位！ ※ 引述《mantour (朱子)》之銘言： : 這個問題是典型的dynamic programming的例子 : 基本上可以直接套用floyd最短路徑演算法 : 就演算法的精神說明一下 : 一開始用一個矩陣D表示節點的相鄰性 : D(i,i) = 0 : 若vi,vj之間有連結，則D(i,j)=1 : 若沒有連結 : D(i,j) = Inf (Inf 為自設的常數，比任二點可能的最大步數大) : 此時D(i,j)表示了vi,vj直接相連的步數 : 接著考慮從vi走到vj，中間可以經過v1的最少步數 : 如果經過v1的步數比本來直接走短，就把D(i,j)重設為新路徑的步數 : 也就是說對所有的i,j : if( D(i,1)+D(1,j) .lt. D(i,j)) then : D(i,j) = D(i,1) + D(1,j) : end if : 再來考慮vi,vj中間可經過v1,v2的最少步數 : 這裡有一點tricky的地方是，我們不需要真的去算所有經過v1或v2的組合 : 只要分成二點來考慮就可以了的大小就可以了 : 1) 由vi到vj 可經可不經v1 但不經v2 也不經過其他點的最小步數 : 2) 由vi到vj 可經可不經v1 但必須經過 v2 不經過其他點的最小步數 : 只要比較這二個數值中比較小的就是由vi到vj 可經可不經v1,v2 的最少步數 : 其中 1)前面已經算過了，就是目前的D(i,j) : 而2)呢？可以想一想，如果有一條最短的路線從 vi 經過 v2 到 vj : 中間可經可不經v1 但不可經過其他點 : 則其中由vi到v2和由v2到vj這二段分別一定也是走可經可不經v1 而不經其他點的最短路徑 : 也就是 2) = D(i,2) + D(2,j) : 因此假如對所有i,j再進行一次重設 : if( D(i,2)+D(2,j) .lt. D(i,j)) then : D(i,j) = D(i,2) + D(2,j) : end if : 就得到任二點之間可經可不經 v1,v2 ，但不經其他點的最短步數 : 重複這個動作 : 就可以得到任二點之間，可經可不經其他所有點的最短步數 : 也就是我們要的答案 : 整個演算法寫出來只需要三層迴圈 : do k=1,N : do j=1,N : do i=1,N : if (D(i,k)+D(k,j) .lt. D(i,j)) then : D(i,j) = D(i,k) + D(k,j) : end if : end do : end do : end do : 時間複雜度為O(N^3) : 其中由於連結沒有方向性，因此D是對稱的，實際上只需計算上三角的部份即可 : 所以還可以再修改節省一點時間 : 打了半天好像還是講得不是很清楚 : 不過只要把演算法的名字丟到google應該就可以找到更詳細的說明 : 希望對原PO有幫助 : 也希望我有寫錯的地方大家可以幫我指出來 : ※ 引述《yin0416 (冷色鉛筆)》之銘言： : : 假設有Ｎ個點，每個點相互之間有些有連結，有些沒有連結。 : : 給你一個Ｎ乘Ｎ的矩陣，代表每個點相互之間連結的有或無。 : : 請算出每個點與點之間的最小連結步數， : : 例如點１與點２有連結，點２與點３之間有連結，而點１與點３之間沒有直接連結， : : 則點１與點３之間的最小連結步數即為２步。 : : 老師並不要求我寫出來，所以我不是為了應付作業而來發問的。 : : 這個程式的結構我想了很久，但沒有想出來。 -- ◥ ◢◥◣ △ㄑ◤◢◥ ／◤〝 ▇▇ 〞◥＼ ◢ㄑ◥◣\ ◣ / \ ◣ \◤〝／／＼＼〞◣/ ◥◥◤◤◤◥◤◥◢ !◣ ◤◤◤)◥◥ ◤! ／＼／＼ ◣◤ 〒〒 ◥◢ ◣◤ ● ● ◥◤ ── ／ ◣ —lm ◢ ◥◣"" v ""◢◤ ╱▇ ◣ ※╲ ◣ ◢◥ ◤◣ ψg80046 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.128.128.158 ※ 編輯: yin0416 來自: 140.128.128.158 (12/08 11:45)