セルラーオートマトンを使用したグラフの頂点の到達可能性解析

Question

グラフ内のノードの到達可能性のテスト（指示）は、cellualr Automataを使用して行うことができますか？実際には、CAを使用して、特定の頂点からノードの到達可能性をチェックするアルゴリズムを実装することが念頭に置かれています。それも可能ですか？ CAはこれを行うことができますか？

Answer 1

CAがあなたの望むことを確実に行うことはできません。しかし、Dijkstraを使用して、あるノードから別のノードへの最短パス（パスが存在する場合も）を判別できます。しかし、Dijkstraの複雑さは高いです。 Conway's Game of Lifeがturing completeあるので、

Answer 2

あなたの最初の質問への答えは、イエスです。つまり、セルオートマトン（特にGame of Life）は、あなたのPCができるあらゆる機能を計算することができます。

私は証拠の内容に精通していないですが、私はそれがライフゲームのインスタンスにチューリングマシンを変換するいくつかの方法に基づいていることを前提としています。あなたが問題を解決するチューリングマシンを構築することができれば、おそらくそのテクニックを使ってセルオートマトンに変換することができます。

Dijkstra's Algorithmよりはるかに簡単で、セルオートマトンはおそらく問題を効率的に解決する方法ではないため、深さのある最初の探索を基本アルゴリズムとして使用することをお勧めします。

Answer 3

私は任意のグラフで到達可能性はありません一般的なセルラオートマトンを知っているが、1990年代半ばにセルオートマトンを用いた迷路矩形格子における迷路解決にいくつかの研究がありました。この手法の説明は、hereです。 ACMにアクセスできる場合は、元の論文hereを読むことができます。グラフが2Dグリッドであると仮定すると、経路探索のアルゴリズムを到達可能性に適合させることは特に難しいことではありません。

もっと一般的なアルゴリズムが見つかるかどうか調べてみます。