0

問題は次のとおりです。放浪者はグリッド座標 (x,y) から開始し、座標 (0,0) に到達したいと考えています。すべてのグリッドポイントから、放浪者は北に 8 歩、南に 3 歩、東に 5 歩、西に 6 歩 (8N/3S/5E/6W) 移動できます。

幅優先探索を使用して (X,Y) から (0,0) への最短ルートを見つけるにはどうすればよいですか?

説明:

  • 無制限のグリッド
  • 負の座標を使用できます
  • キュー (リンクされたリストまたは配列) を使用する必要があります
  • 障害物はありません
4

4 に答える 4

2

この問題のアルゴリズムは次のようになります。

各軸について、もう一方の軸での位置が 0 になるまで、その方向に進みます。

擬似コード:

while (x!=0) {
  if (x>0) x-=6;
  else x+=5;
}
while (y!=0) {
  if (y>0) y-=8;
  else y+=3;
}

ただし、ルートを検索する必要がある理由がわかりません。それほど複雑ではありません。

于 2010-11-21T12:37:42.160 に答える
1

キューを使用する私の答えは次のとおりです（実際にはjhの答えに基づいています）。

//set x to start position
//set y to start position
do {
  if (x<0) Queue.Push(8N);
  if (x>0) Queue.Push(3S);
  if (y<0) Queue.Push(5E);
  if (y>0) Queue.Push(6W);
  while (!Queue.Empty())
  {
    Move(Queue.Pop());
  }
} while (x && y);

複雑ですが、指示に従います。

于 2011-01-05T00:02:13.637 に答える
1

「thejh」が述べたように、検索の必要はありませんが、あなたの割り当ては検索を必要とします。

合理的なアプローチは

  1. 分析します。任意の（x、y）開始位置ですべて可能ですか？許可された動きをチェックすると、それらを組み合わせて1ステップの水平方向の動きと1ステップの垂直方向の動きを生み出すことができることがわかります。

  2. 「幅優先探索」とは何かを理解します。ウィキペディアはあなたの友達です（ただし、大学図書館にアクセスできる場合は、パトリックヘンリーウィンストンの古い人工知能をお勧めします。これは非常にわかりやすく説明されています）。もっと簡単な問題で試してみてください。

  3. 割り当ての問題をほぼ同じ方法で実行します。技術的なC++の問題が発生した場合は、ここで質問してください。

乾杯＆hth。、

于 2010-11-21T12:47:42.647 に答える
-2

今後の参考のために、私自身の質問に答えてみましょう。

疑似コード:

while (true) {
    if (destination reached)
        break;
    addToQueue(go north);
    addToQueue(go south);
    addToQueue(go east);
    addToQueue(go west);
    getNextFromQueue;
}

また、このアプリケーションの実行時間は非常に急速に長くなるため、小さい座標値でテストしてください。たとえば、座標 (1,1) は 7 レベルの幅を与え、16384 回の反復が必要です。

于 2010-11-27T19:12:17.493 に答える