PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [閒聊] Hamiltonian Cycle Problem is in P？

看板Prob_Solve (計算數學 Problem Solving)作者c910335 (達人)時間3年前 (2021/05/28 20:25)推噓2(2推 0噓 2→)

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

※ 引述《alan23273850 (God of Computer Science)》之銘言： : 最近 arxiv 上出現了一篇很有趣的 paper： : https://arxiv.org/abs/2105.07608 : 各位的看法如何呢？先打個預防針我並不保證我的理解是正確的只是在這裡說說我的看法這幾天花了點時間讀這篇我的結論是：這篇是錯的而錯誤的地方是儘管演算法本身是多項式時間但它並沒有正確的判定 Hamiltonian Cycle 是否存在先來稍微說明一下他的演算法首先任意決定一個起點 u 拆成兩個節點 u1, u2 這兩個點都有連到原本的鄰居於是新圖上的 Hamiltonian Path 一定會以這兩個節點為起點終點這兩點接起來就會變回原圖的 Hamiltonian Cycle 這部分沒有任何問題演算法主要是用 Dynamic Programming 來設計定義 PS[v, i, j] = v 當終點長度 i 以下的最長簡單路徑可以用到的倒數第 i - j 個節點的集合 PS[v, i] = 對於所有可能的 0 <= j <= i 把 PS[v, i, j] 串起來 i.e. PS[v, i] = { PS[v, i, 0], PS[v, i, 1], ..., {v} } 注意由於 v 一定是終點所以任何 PS[v, i, i] = {v} 另外由於起點和終點已經固定是 u1 和 u2 了所以當 1 <= i < n 的時候 PS 只考慮 u1 u2 以外的點當 i = 0 的時候 PS 只考慮 u1 當 i = n 的時候 PS 只考慮 u2 （這裡省略了 Path Hologram 的說明因為很麻煩）於是如果能正確定義 DP 的轉移式最後算出 PS[u2, n, 0] 如果剛好是 {u1} 就表示這張圖存在 u1 到 u2 的 Hamiltonian Path 也就是原圖存在 Hamiltonian Cycle 對於一條邊 v -- w 當我們要用 PS[v, i - 1] 來更新 PS[w, i] 的時候會分成兩個 case： 1. 如果 PS[v, i - 1] 裡並沒有 w 也就是說最後面直接接上 w 也還是簡單路徑可以很單純的用 PS[v, i - 1] + {w} 來更新 PS[w, i] （保留比較長的，如果一樣長就每層各別聯集） 2. 如果 PS[v, i - 1] 有 w 那我們就必須先把 PS[v, i - 1] 裡的 w 去掉並且簡單路徑上必須經過 w 的其他節點也去掉（看一下論文 Figure 1 就懂了）才能用 PStemp[v, i - 1] + {w} 來更新 PS[w, i] （由於去掉 w 之後的結果並沒有要存回 PS[v, i - 1] 所以用 PStemp[v, i - 1] 來表示去掉 w 之後的 PS[v, i - 1]）我認為問題就出在這第二個 case 考慮 K5（五個點的完全圖）+ 一個分離節點的 case 令其節點集合為 {a, b, c, d, e} + {f} 首先把 a 拆成 a1, a2 當我們要用 PS[b, 4] 來更新 PS[c, 5] 的時候 PS[b, 4] 明顯為 {{a1}, {c, d, e}, {c, d, e}, {c, d, e}, {b}} 可以發現中間有三個 c 需要去掉於是去掉 c 得到 PStemp[b, 4] = {{a1}, {d, e}, {d, e}, {d, e}, {b}} 後面再接上 c 變成 PStemp[c, 5] = {{a1}, {d, e}, {d, e}, {d, e}, {b}, {c}} 到這裡各位應該察覺到問題所在了 PStemp[c, 5] 所得到長度 6 的路徑其中有三個位置在搶兩個節點但是該論文的演算法並沒有辦法察覺這件事於是會錯誤地判斷這張圖存在 Hamiltonian Cycle 其實在我看來該論文似乎也有考慮過類似的情形所以避免掉有兩個以上的位置搶一個節點了（CM operator Line 19）但他沒考慮到的是：三個以上的位置搶兩個節點、四個以上的位置搶三個節點、以此類推以上就是我對於這篇的看法再說一次結論：這篇論文是錯的該演算法並沒有正確的判定一張圖是否存在 Hamiltonian Cycle -- ︿︿︿︿︿︿︿︿︿︿︿︿ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╳ キ ╳ ╳ ズ ╳ ╳ ラ ╳ ╳ ン ╳ ╳ ダ ╳ ╳ ム ╳ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ﹀﹀﹀﹀﹀﹀﹀﹀﹀﹀﹀﹀ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.230.194 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1622204710.A.2A2.html