Cプログラミング：最短経路を見つけるには？

Question

このようなものに見える、私は36個の頂点（すなわち、行当たり6つの頂点と列あたり6つの頂点）からなる6×6の正方形を有する想像：

• • • • • • 
• • • • • • 
• • • • • • 
• • • • • • 
• • • • • • 
• • • • • • 

をすべての頂点のいずれかである1、2、3または4に接続され私たちは基本的に頂点とエッジを持つグラフを取得します。 私の問題は次のとおりです。ある頂点にある特定のオブジェクトが見つかるまで、ロボットがその迷路を通過して欲しいと思います。そのオブジェクトを見つけたらすぐに最も早くという方法で出発点に戻ってください。

これを実現する方法がわからないので、私の質問は次のとおりです。Cの頂点とエッジに関する情報を保存するのに最適な構造は何ですか？ （36x36がかなり大きいので、隣接行列は私にとっては非効率的だと思われます）。そして、この情報を使って、どのようにして最初から最も速い方法を見つけることができますか？

Answer 1

あなたは{アップ、右、下、左}のいずれかに移動し、有効なつまり、方向を「オープン」していることを表現するために、頂点あたり4ビットを必要とするように見える。

だから、あなたは壮大が必要になります合計：

すべての接続データを保存します。それよりもずっと効率的になるとは想像もしません。

Answer 2

Path Findingソリューションでよく使用されるA *アルゴリズムを調べることをお勧めします。

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html