cellualr Automata を使用して、グラフ (有向) 内のノードの到達可能性をテストできますか? 実際に考えているのは、CA を使用して、指定された頂点からノードの到達可能性をチェックするアルゴリズムを実装することです。それは可能ですか？CAはそれを行うことができますか？
何か案が？
3 に答える
2
コンウェイのライフゲームは完全にチューリング完全であるため、最初の質問に対する答えは「はい」です。これは、セルオートマトン（特に人生ゲーム）がPCで実行できるすべての機能を計算できることを大まかに意味します。
私は証明の詳細に精通していませんが、それはチューリングマシンを人生ゲームのインスタンスに変換する何らかの方法に基づいていると思います。問題を解決するためにチューリングマシンを構築できる場合は、おそらくその手法を使用してセルオートマトンに変換できます。
深さ優先探索を基礎となるアルゴリズムとして使用することをお勧めします。これは、ダイクストラのアルゴリズムよりもはるかに単純であり、セルオートマトンはおそらく問題を解決する効率的な方法ではないためです。
于 2011-08-19T13:50:52.883 に答える
1
任意のグラフでの到達可能性に関する一般的なセル オートマトンを私は知りませんが、1990 年代半ばに、セル オートマトンを使用した長方形格子迷路での迷路解決に関する研究がいくつかありました。技術のアクセシブルな説明の 1 つをここで見つけることができます。ACM にアクセスできる場合は、元の論文をここで読むことができます。グラフが 2D グリッドであると仮定すると、経路探索のアルゴリズムを到達可能性に適合させることは特に難しくありません。
より一般的なアルゴリズムを見つけることができるかどうかを調べ続けます。
于 2011-08-19T15:55:52.413 に答える
-2
CAがあなたの望むことをしてくれるとは断言できません。ただし、ダイクストラを使用して、あるノードから別のノードへの最短パス (パスが存在する場合も) を決定できます。ただし、ダイクストラの複雑度は高いです。
于 2011-08-19T13:41:55.987 に答える