5

36 個の頂点 (つまり、行ごとに 6 個の頂点、列ごとに 6 個の頂点) で構成される 6x6 の正方形があるとします。次のようになります。

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

すべての頂点は、1、2、3、または 4 つの近くの頂点に接続されているため、基本的には頂点とエッジを含むグラフが得られます。私の問題は次のとおりです。ロボットが頂点に配置された特定のオブジェクトを見つけるまで、エッジの「迷路」を通過する必要があります。そのオブジェクトを見つけるとすぐに、最も早い方法で開始点に戻る必要があります。

さて、これを実現する方法がよくわからないので、私の質問は次のとおりです。これらの頂点とエッジに関する情報をCで保存するための最良の構造は何ですか? (36x36 は非常に大きいため、隣接行列は非効率的と思われます)。そして、この情報を使用して、最初に戻る最も早い方法を見つけるにはどうすればよいでしょうか?

4

2 に答える 2

1

{上、右、下、左}のいずれかが「開いた」方向であること、つまり移動するのに有効であることを表すには、頂点ごとに4ビットが必要なようです。

したがって、次の総計が必要になります。

6 * 6
----- = 18 bytes
  2

すべての接続データを保存します。それよりもはるかに効率的になるとは想像しがたいです。

于 2013-03-18T15:28:20.873 に答える
1

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

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

于 2013-03-18T15:41:53.077 に答える