java - 再帰的迷路解法

Question

セルで構成されたものを再帰的に解く方法に取り組んでいます。

メソッドはまったく機能していません。任意の提案をいただければ幸いです。

パラメータ: srow = 開始 x 値。scol = 開始 y 値 erow = 終了 x 値。ecol = 終了 y 値。L = 解決済みパスポイントのリンクリスト

コード：

private InputGraphicMaze2 maze;
private int R, C; 

//code added by me
private String[] [] cell; //an array to keep track of cells that are proven dead ends. 


public YourMazeWithPath2() 
{       
   // an R rows x C columns maze
  maze = new InputGraphicMaze2();

  R=maze.Rows(); C=maze.Cols();  

  //code added by me
  cell = new String[R+2][C+2];
  for (int i=0; i<R+2; i++) {
      for (int k=0; k<C+2; k++) {
          cell[i][k] = "no";
      }
  }

  // Path holds the cells of the path
  LinkedList<Point> Path = new LinkedList<Point>();
   // Create the path
   CreatePath(maze, 1, 1, R, C, Path);
   // show the path in the maze
   maze.showPath(Path);
}

private void setDead(int x, int y) {
    cell[x][y] = "dead";
}

private void setVisited(int x, int y) {
    cell[x][y] = "visited";
}

public boolean CreatePath(InputGraphicMaze2 maze,      
  int srow, int scol, int erow, int ecol, LinkedList<Point> L)
{

    int x = srow;
    int y = scol;
    Point p = new Point(x, y);

    if ((x<1) || (y<1) || (x>R) || (y>C)) {
        return false; //cell is out of bounds
    }

    else if ((x==R) && (y==C)) {
        return true; // cell is the exit cell
    }

    else {
        if ((maze.can_go(x, y, 'U')) && (x!=1) && (!cell[x-1][y].equals("dead")) && (!cell[x-1][y].equals("visited"))) {
            L.addLast(p);
            setVisited(x,y);
            CreatePath(maze, x-1, y, R, C, L);
            return false;
        }
        else if ((maze.can_go(x, y, 'R')) && (y!=C) && (!cell[x][y+1].equals("dead")) && (!cell[x][y+1].equals("visited"))) {
            L.addLast(p);
            setVisited(x, y);
            CreatePath(maze, x, y+1, R, C, L);
            return false;
        }
        else if ((maze.can_go(x, y, 'D')) && (x!=R) && (!cell[x+1][y].equals("dead")) && (!cell[x+1][y].equals("visited"))) {
            L.addLast(p);
            setVisited(x, y);
            CreatePath(maze, x+1, y, R, C, L);
            return false;
        }
        else if ((maze.can_go(x, y, 'L')) && (y!=1) && (!cell[x][y-1].equals("dead")) && (!cell[x][y-1].equals("visited"))) {
            L.addLast(p);
            setVisited(x, y);
            CreatePath(maze, x, y-1, R, C, L);
            return false;
        }
        else {
            if ((maze.can_go(x, y, 'U')) && (x!=1) && (cell[x][y-1].equals("visited"))) {
                setDead(x, y);
                if (L.contains(p))
                    L.remove(p);
                CreatePath(maze, x-1, y, R, C, L);
                return false;
            }
            else if ((maze.can_go(x, y, 'R')) && (y!=C) && (cell[x][y+1].equals("visited"))) {
                setDead(x, y);
                if (L.contains(p))
                    L.remove(p);
                CreatePath(maze, x, y+1, R, C, L);
                return false;
            }
            else if ((maze.can_go(x, y, 'D')) && (x!=R) && (cell[x+1][y].equals("visited"))) {
                setDead(x, y);
                if (L.contains(p))
                    L.remove(p);
                CreatePath(maze, x+1, y, R, C, L);
                return false;
            }
            else if ((maze.can_go(x, y, 'D')) && (y!=1) && (cell[x][y-1].equals("visited"))) {
                setDead(x, y);
                if (L.contains(p))
                    L.remove(p);
                CreatePath(maze, x, y-1, R, C, L);
                return false;
            }
            else {
                return false;
            }
        }
    }



}

score 1 · Accepted Answer

別の同様のスレッドから、より冗長な言語で問題を確認するためだけに、ユーザー @Sergey Rudenko によって作成されたこの小さな JS 再帰的迷路ソルバーを見てください。

var map = [
    [1,1,0,0,0,0,0,0],
    [0,1,1,0,0,0,0,0],
    [1,1,1,0,0,0,0,0],
    [1,0,0,1,1,1,1,1],
    [1,1,0,0,1,0,0,1],
    [0,1,1,0,1,0,0,1],
    [1,1,1,0,1,0,0,1],
    [1,0,0,0,1,1,1,1]
]

var goalx = 7;
var goaly = 7;

function findpath(x,y){

    // illegal move check
    if (x < 0 || x > (map[0].length -1) || y < 0 || y > (map.length - 1)) return false; //if it is outside of map
    if (map[y][x]==0) return false; //it is not open

    // end move check
    if (x== goalx && y== goaly){
        console.log('Reached goal at: ' + x + ':' + y);
        return true; // if it is the goal (exit point)
    }

    if(map[y][x] == 9 || map[y][x] == 8)
        return false;

    console.log('Im here at: ' + x + ':' + y);

    map[y][x]=9; //here marking x,y position as part of solution path outlined by "9"

    if(findpath(x+1,y)) 
        return true;    
    if(findpath(x,y+1)) 
        return true;    
    if(findpath(x,y-1))
        return true;
    if(findpath(x-1,y)) 
        return true;                    

    return false;
};

findpath(0, 0);

JSフィドル

うん。小さくて、単純で、素朴で、欠けていますが、再帰的で、機能します! また、多くの迷路探索アルゴリズムに共通する部分がはっきりとわかります。

より真剣に読むために、このページには、多くのゲーム関連のアルゴリズムに関する、詳細でありながら科学的な論文ではない優れたチュートリアルがあります。

アルゴリズムを購入する際に答える必要がある関連する質問がいくつかあります。

解決策が必要ですか？

すべてのソリューションが必要ですか?

最速が必要ですか？

迷路の地形は？グリッド？グラフ？

将来的に移動コストを実装したいですか？

ヒューリスティックを実装して最適なルートを選択したいですか?

最後に、まだ見つけていない場合は、* アルゴリズムを確認してください。非常に人気があります。

楽しむ！

score 0 · Accepted Answer

これは基本的なグラフトラバーサルの問題です。bfs ではなく dfs を使用することをお勧めします。アルゴリズムとデータ構造に関するほぼすべての教科書に実装があります。

再帰部分を微調整して、目標に到達したら検索を停止するだけです。一方、ゴールへのすべてのパスを探している場合は、すべてのパスを実行してから、そこから進みます。ヒントについては、Bellman–Ford または Dijkstra のアルゴリズム (http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) を調べることができます。繰り返しますが、グラフに関する章がある優れた教科書です。

java - 再帰的迷路解法

2 に答える 2

Related

Reference