6

X と O の迷路を解く迷路ソルバー プログラムを作成しようとしています。私がやりたいのは、ポイントのクラスを作成して、出力ページへの印刷とスタックの実装を比較的簡単にするポイントの 2 次元配列を作成できるようにすることです。

私が実際のプログラム自体に実装したい一般的なアイデアの最も単純なアルゴリズムは、次のようになるはずです。

1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved

しかし、より詳細なアルゴリズムを考え出すのと、ポイント クラスを配置するのに苦労しています。ポイントについては、X 座標を設定し、Y 座標と 2 つのゲッターも設定する必要があることを知っています。これらの 2 つよりも多くのメソッドが必要だと思いますか? 同様に、x 座標と y 座標をパラメーターとして渡すメソッドを作成して、x と y を個別に設定するのではなく、それらを 1 つにプッシュできるようにする必要がありますか?

サンプルの迷路は次のようになります。右下から開始し、左上にトラバースしようとします。X は壁、O は迷路の空きスペースです。

O O O O O X O
X X O X O O X
O X O O X X X
X X X O O X O
X X X X O O X
O O O O O O O 
X X O X X X O
4

7 に答える 7

1

あなたのアルゴリズムが迷路を解けると確信していますか? この単純なモックアップ (S が開始、F が終了) では行き詰まると思います。

xxxxxxxxxx
Sooooooxxx
xxxxxxoxxx
xxxxxxFxxx

あなたのアルゴリズムは最初のホールを落下に面するまで進み、左に曲がり、「北」の壁に面し、再び左に曲がり、最初の廊下を戻ります。ここで再び左に 2 回曲がり、この問題を繰り返し続けます。

右手の法則のアルゴリズム (ウィキペディアのページやその他の迷路アルゴリズムについては他のセクションを参照) は、ループなしで迷路を解く必要があり、Java での実装がかなり簡単なはずです。

于 2012-02-08T15:51:34.013 に答える
0

あなたは使用することができます

Stack<Point> points = new Stack<>();

// add a point
Point p = new Point(x, y);
if (points.contains(p))
   // been here before, in circles.
else
   points.add(p);
于 2012-02-08T15:48:27.327 に答える
0

このアルゴリズムでは、スタックは必要ありません。トラバーサルの決定を元に戻すためにバックトラッキングを使用する場合にのみ、スタックが必要になります。

于 2012-02-08T15:54:12.397 に答える
0

ウォール フォロワー アルゴリズムを使用: http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

于 2012-02-08T17:00:03.590 に答える
0

私が学校にいたとき、私たちはこの問題に一度取り組み、右手/左手の法則に似た解決策を使用しました. これは、Linked List について学習しているときに行ったと思います。一言で言えば、アルゴリズムは次のようになりました。

  1. 左に行きます。可能であれば、繰り返します。
  2. そうでない場合は、まっすぐ進みます。可能であれば、手順 1 に戻ります。
  3. そうでない場合は、右に行きます。可能であれば、手順 1 に戻ります。

各ステップで、自分が立っている場所がゴールかどうかも確認します。続行できない場合 (つまり、左、直進、または右に移動できない場合)、現在立っている場所を「訪問済み」としてマークし、元に戻します。すすいで繰り返します。

于 2012-02-08T18:54:50.043 に答える
0

アルゴリズムについては、バックトラッキングを使用できます（EDITただし、一般的な考えとは完全には一致しません。）動きが仮想スタックに「プッシュ」され、プッシュを解除する必要があることを認識する必要があります（したがって、元に戻す必要があります）。 「ロボット」が実際に動くオブジェクトの場合はスタックを自分で実装する必要がありますが、迷路を解きたいだけの場合はコール スタックを利用できます。

于 2012-02-08T15:52:19.527 に答える
0

アルゴリズム部分については、スタックを介した深さ優先再帰が推奨されます。次のようなもの：

currentSpot = (0,0)  // The starting point //

while(! currentSpot.isExit()) {

  if (! currentSpot.left().isWall()) stack.push(currentSpot.left());
  if (! currentSpot.forward().isWall()) stack.push(currentSpot.forward());
  if (! currentSpot.right().isWall()) stack.push(currentSpot.right());

  currentSpot = stack.pop();  // Get the next location //
}

ポイント クラスは、指定された各方向 (後方を除く) の次のポイントを返し、迷路の端にいることを検出する必要があります。おそらく、すべてのポイントを含み、印刷を行い、X/O を格納する Maze クラスが必要になるでしょう。したがって、最初の currentSpot = (0,0) を currentSpot = Maze.getStartingSpot() に置き換えることができます。 ;

于 2012-02-08T15:53:07.030 に答える