1

以下のsudoコードを使用して左手の出口ルールを使用して迷路を解こうとしていますが、ほとんど機能していますが、行き止まりにぶつかって戻ってきたときに新しい方向を選択することに問題があります(上が真であるが左、下、右の壁が偽である正方形の場合、最初のフェーズでコードが正しく移動し、エントリが下または右の2つのいずれかに左に移動した場合、戻ってきたときに左が選択されます下ではなく方向、下を選択するにはどうすればよいですか）。

誰かが新しい方向を選択する方法について私にアドバイスできますか - 私はあなたの参考文献のために問題の方法の周りに二重アスタリスク (**) を入れました。

Set int entr to LEFT;
Set int exit to-1;
Set boolean backtrack to false;
Set currentSquare to startingSquare;
Set previousSquare to null;
Set currentSquare.onpath to true;
While (currentSquare != endingSquare) {
    **Set exit to currentSquare.getLeftHandExit(entr);**
    Set previousSquare to currentSquare;
    Set currentSquare to currentSquare.adjacentSquare(exit);
    If (backtracking is false and exit is same as entrance)
        Set backtracking to true;
        Remove previousSquare from path;
    }
    Else if backtracking is true and currentSquare is not on the path
        Set backtracking to false;
        Add previousSquare to path;
    }
    If backtracking is true, remove currentSquare from path;
    else add currentSquare to path;
    entr = currentSquare.oppositeSide(exit);
} // end of While
4

2 に答える 2

1

いつも左を向いていたら、後ろを向くだけです。方向を変えれば、左側が右側に変わってしまいます。

次の廊下に出たら、まだ左に曲がります。

左手を壁につけたままにしておけば、やがて抜け出すことができると思います。

迷路の複雑さに応じて、ループに陥る迷路を設計することができます。そのため、どこかのセクションを往復したことを検出できるように、行った場所の色を変更したい場合があります。再びあなたの道を繰り返しています。

于 2010-12-06T02:45:24.030 に答える
1

バックトラッキング システムを使用します。再帰的な方法 (好ましくない) を使用するか、スタックを使用してステップを戻すか。理想的には、アルゴリズムがウェイを選択するすべてのジャンクションにもマーカーを設定して、同じパスを再度選択しないようにする必要があります (特定のジャンクションでマークされていないパスのみを選択します)。

ウィキペディアには、これを実現する方法に関する優れた擬似コードがあります。「再帰バックトラッカー」アルゴリズムに注意してください。「未訪問の隣人をランダムに選択する」を「未訪問の隣人から左折を選択する」に置き換えます (左のセルから時計回りに選択することを意味します)。

また、再帰性に関するこの電子書籍もチェックしてください。

私は（テストされていないコード）のようなものに行きます：

maze.clearAllVisited();
Stack<Point> paths = new Stack<Point>();
int x = maze.getStartX();
int y = maze.getStartY();
while (!maze.isExit(x, y)) {
   maze.setVisited(x, y);
   if (maze.canGoWest(x, y)) {    // check if west cell is accessible from x,y and has not been visited
      paths.push(new Point(x, y));
      x--;
   } else if (maze.canGoNorth(x, y)) { // check if north cell is accessible from x,y and has not been visited
      paths.push(new Point(x, y));
      y--;
   } else if (maze.canGoEast(x, y)) {  // ...
      paths.push(new Point(x, y));
      x++;
   } else if (maze.canGoSouth(x, y)) { // ...
      paths.push(new Point(x, y));
      y++;
   } else {
      if (paths.isEmpty()) {
         break;  // no more path for backtracking, exit (aka no solution for maze)
      }
      // dead end! go back!
      Point last = stack.pop();
      x = last.x;
      y = last.y;
   }   
}
于 2010-12-06T02:33:05.160 に答える