使用元胞自動機對圖中頂點的可達性分析

可以使用cellualr自動機來測試圖（指示）中節點的可達性。實際上，要實現的算法是使用CA來檢查指定頂點的點頭可達性。它甚至有可能嗎？ CA有能力做到這一點嗎？使用元胞自動機對圖中頂點的可達性分析

有什麼想法？

2011-08-19 Faria

我無法回答這是可行的，但我強烈懷疑它會比執行常規圖搜索更好，如A *或Dijkstra算法。 – carlpett

-2

我不能肯定地說CA會做你想做的事。但是可以使用Dijkstra來確定從一個節點到另一個節點的最短路徑（如果存在路徑）。迪傑斯特拉的複雜性很高。

2011-08-19 13:41:55

是的，我知道迪傑斯特拉可以找到最短的路徑，但我需要這樣做，與CA.但我猶豫是否有可能。 – Faria

這不回答這個問題。此外，我不同意Dijksrra算法的複雜性很高，它運行在一個快速的O（E + V lg V） – templatetypedef

@templatetypedef當然_if_它使用最小優先級隊列。如果不是，那麼它就是O（n^2），這是低效的。 –

您的第一個問題的答案是肯定的，因爲Conway's Game of Life是turing complete。這大致意味着細胞自動機（特別是生命遊戲）可以計算您的個人電腦的任何功能。

我對這個證明的細節並不熟悉，但我會認爲它是基於某種方式將圖靈機轉化爲生命遊戲的一個實例。如果你可以構建一個圖靈機來解決這個問題，你可以用它來轉換成一個元胞自動機。

我建議使用深度優先搜索作爲底層算法，因爲它比Dijkstra算法簡單得多，而元胞自動機可能不是解決問題的有效方法。

2011-08-19 13:50:52

感謝您的回覆。正如你所提到的，DFS或BFS比Dijkstra的算法更簡單。首先構建圖靈機來解決這個問題，然後將其轉化爲cellualr自動機是個好主意。然而，似乎網上沒有明確的資源，因爲我試圖用圖靈機來解決這個問題，但什麼也沒有發現。無論如何，感謝您的回覆。任何進一步的指導 – Faria

通常，要解決TM的問題，首先需要找到編碼問題的好方法。例如，在這裏，您可以將它編碼爲兩組：頂點和邊。例如，假設輸入實例爲0^V.111。（0^a.1.0^b）^ E.11111，其中V是頂點數，所有a，b Patrick87

我知道任意圖表中的可達性沒有一般的元胞自動機，但在20世紀90年代中期，有人用矩陣自動機對矩形網格迷宮中的迷宮求解進行了一些研究。該技術的一個可訪問的描述可以在here找到。如果您有ACM訪問權限，您可以閱讀原始文件here。假設您的圖形是2D網格，將路徑查找算法適用於可達性應該不是特別困難。

我會繼續尋找並看看我能否找到更一般的算法。

2011-08-19 15:55:52 templatetypedef

回答