使用oracle機器在多項式時間中查找Hamilton路徑

假設您有一個oracle可以確定（在多項式時間內）某個圖中是否存在Hamilton路徑。（提醒：漢密爾頓路徑問題在NPC中）。使用oracle機器在多項式時間中查找Hamilton路徑

描述如何使用oracle以便找到圖中的哈密爾頓路徑，在多項式時間內。

任何想法？

來源

2017-04-15 SKriheli

這可能更適合計算機科學堆棧交換 - 這不是關於*編程*。 –

哈密爾頓路徑只訪問一次頂點。

如果你有一個oracle，你可以測試依次去除每個邊緣。如果oracle說還有一條路徑，那麼保持邊緣被刪除，否則恢復邊緣並嘗試下一條路徑。

一旦你經歷了所有的邊緣，所有將留下的將是哈密爾頓路徑。

來源

2017-04-15 21:04:53

我不確定我的理解。當你說我們可以依次刪除每條邊 - 我怎麼知道我可以從我手中的圖中刪除一條邊？我的意思是，在某些圖表中，即使我試圖去除邊緣，也可能有一個機會，但是仍然不會有哈密爾頓路徑。那麼爲什麼我們刪除邊緣？ – SKriheli

這個想法是，我們從一個有很多邊的圖開始。甲骨文告訴我們，有一條哈密爾頓路徑 - 但不是它在哪裏。我們儘量通過在保留路徑的同時刪除邊來儘可能簡化圖。一旦我們完成刪除邊緣，我們將有一個非常簡單的鏈圖，它必須等於哈密爾頓路徑。你是對的，有時刪除邊會消除路徑，但在這些情況下，我們再次放回邊緣並嘗試不同的邊緣。 –

所以，oracle實際上得到了一個有很多邊的圖，而我們確實知道這個圖包含一個哈密爾頓路徑，但我們不知道在哪裏。如上所述，刪除邊緣最終只會將圖形留在哈密爾頓路徑的一部分。對？ – SKriheli

如果有N個 - 在圖中，我們就大功告成了1個邊（它必須是一個鏈條，否則，沒有漢彌爾頓路徑）。

否則，我們可以刪除一些邊緣。我們遍歷所有邊。如果在沒有固定邊的圖中仍有路徑，我們可以將其移除並繼續。

這種解決方案需要O（平方公尺）預言查詢，因此它工作在多項式時間。

來源

2017-04-15 21:05:16 kraskevich

使用oracle機器在多項式時間中查找Hamilton路徑

回答

相關問題