java - Java で迷路を解くアルゴリズムを作成する

Question

Java で迷路ソルバーを作成するタスクが割り当てられました。割り当ては次のとおりです。

Write an application that finds a path through a maze.  
The maze should be read from a file.  A sample maze is shown below.

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

文字「X」は壁またはブロックされた位置を表し、文字「O」は開いた位置を表します。迷路の入り口は常に右下隅にあり、出口は常に左上隅にあると考えてよいでしょう。プログラムは、その出力をファイルに送信する必要があります。パスが見つかった場合、出力ファイルにはパスが含まれている必要があります。パスが見つからない場合は、メッセージをファイルに送信する必要があります。迷路には複数のソリューション パスがある場合がありますが、この演習では、すべてのソリューションではなく、1 つのソリューションのみを見つけるよう求められていることに注意してください。

プログラムは、スタックを使用して探索中のパスを記録し、ブロックされた位置に到達したときにバックトラックする必要があります。

コードを記述する前に、必ず完全なアルゴリズムを記述してください。課題を完了するのに役立つ追加のクラスを自由に作成してください。

Here's my Algorithm:
1)Initialize array list to hold maze
2)Read text file holding maze in format
    o x x x x o
    o o x o x x
    o o o o o x
    x x x x o o
3)Create variables to hold numbers of columns and rows
3)While text file has next line
    A. Read next line
    B. Tokenize line
    C. Create a temporary ArrayList
    D. While there are tokens
        i. Get token
        ii. create a Point
        iii. add point to temp ArrayList
        iv. increment maximum number of columns
    E. Add temp to maze arraylist, increment max rows
    F. initialize a hold of points as max rows - 1
    G. Create a start point with x values as maximum number of rows - 1, and y values as maximum number of columns - 1
    H. Create stack of points and push starting location
    I. While finished searching is not done
        i. Look at top of stack and check for finish
        ii. check neighbors
        iii. is there an open neighbor?
            - if yes, update flags and push
            - if no, pop from stack
    J. Print solution
4. Done is true

とにかく、私が設定したのは、次のようにブール値を返すすべての基本方向に移動するための set/get メソッドを持つ Points クラスです。

public class Points<E>
{
private int xCoord;
private int yCoord;
private char val;
private boolean N;
private boolean S;
private boolean E;
private boolean W;

public Points()
{
    xCoord =0;
    yCoord =0;
    val =' ';
    N = true;
    S = true;
    E = true;
    W = true;

}

public Points (int X, int Y)
{
        xCoord = X;
        yCoord = Y;

}

public void setX(int x)
{
    xCoord = x;
}
public void setY(int y)
{
    yCoordinate = y;
}

public void setNorth(boolean n)
{
    N = n;
}
public void setSouth(boolean s)
{
    S= s;
}
public void setEast(boolean e)
{
    E = e;
}

public void setWest(boolean w)
{
    W = w;
}

public int getX()
{
    return xCoord;

}

public int getY()
{
    return yCoord;
}
public char getVal()
{
    return val;
}

public boolean getNorth()
{
    return N;
}
public boolean getSouth()
{
    return S;
}

public boolean getEast()
{
    return E;
}
public boolean getWest()
{
    return W;
}

public String toString1()
{
    String result = "(" + xCoord + ", " +yCoord + ")";
    return result;
}

}

私は実際の解決策を主に理解するのに問題があります。ここに私が持っているものがあります:

import java.io.*;
import java.util.*;
import java.lang.*;
import java.text.*;


public class MazeSolve1
{
  public static void main(String[] args)
  {
//Create arrayList of Points
ArrayList<ArrayList<Points>> MAZE = new ArrayList<ArrayList<Points>>();
Scanner in = new Scanner(System.in);

//Read File in
System.out.print("Enter the file name: ");
String fileName = in.nextLine();
fileName = fileName.trim();
FileReader reader = new FileReader(fileName+".txt");
Scanner in2 = new Scanner(reader);

//Write file out
FileWriter writer = new FileWriter("Numbers.out");
PrintWriter out = new PrintWriter(writer);
boolean done = false;
int maxCol = 0;
int maxRow = 0;

while(!done) {

    //creating array lists
    while (in2.hasNextLine()) {
        //Read next line
        String nextLine = in2.nextLine();
        //Tokenize Line
        StringTokenizer st = new StringTokenizer(nextLine, " ");
        //Create temp ArrayList
        ArrayList<ArrayList<Points>> temp = new ArrayList<ArrayList<Points>>();

        //While there are more tokens
        while (st.hasNextToken()) {
            String token = st.nextToken();
            Points pt = new Points();
            temp.add(pt);
            maxCol++
        }
        MAZE.add(temp);
        maxRow++;
    }

    //create hold arraylist for max rows of maze -1 
    //create variables for start x and y coordinates
    ArrayList<ArrayList<Points>> hold = new ArrayList<ArrayList<Points>>();
    hold = MAZE.get(maxRow - 1);
    int startColumn = hold.get(maxCol - 1);
    int startRow = hold.get(maxRow - 1);
    Point start = new Point();
    start.setX(startColumn);
    start.setY(startRow);

    //initialize stack, and push the start position
    MyStack<Points> st = new ArrayStack<Points>();
    st.push(start.toString1());
    //south and east of start are edges of array
    start.setSouth(false);
    start.setEast(false);

    //while your position is not equal to point (0,0) [finish]
    while (st.peek() != "(0, 0)") {

        //getting the next coordinate to the North
        int nextY = start.getY() - 1;
        int nextX = start.getX();

        //if character to the North is an O it's open and the North flag is true
        if (hold.get(nextY) = 'O' && start.getNorth() == true) {
            //set flags and push coordinate
            start.setNorth(false);
            st.push(start.toString1());
        }
        //else pop from stack
        else { st.pop(); }

        //look at coordinate to the East
        nextX = start.getX() + 1;
        //if character to the East is a O and the East flag is true
        if (hold.get(nextX) = 'O' && start.getEast() == true) {
            //set flags and push coordinate
            start.setEast(false);
            st.push(start.toString1());
        }
        //else pop from stack
        else { st.pop(); }

        //look at coordinate to the South
        nextY = start.getY() + 1;
        //if character to the South is a O and the West flag is true
        if (hold.get(nextY) = 'O' && start.getSouth() == true) {
            //set flags and push coordinate
            start.setSouth(false);
            st.push(start.toString1());
        }
        //else pop from stack
        else { st.pop() }

        //keep looping until the top of the stack reads (0, 0)
    }

done = true;
}

//Print the results
System.out.println("---Path taken---");   
for (int i = 0; i< st.size(); i++) {
    System.out.println(st.pop);
    i++
}

構文エラーは別として、何か助けてもらえますか? どうもありがとう。

Answer 1

ここで同様の回答を提出しましたMaze Solving Algorithm in C++。

それを解決するチャンスを得るには、次のことを行う必要があります。

• ルーチンを作成し、Solve()それ自体を再帰的に呼び出します。
  • 1st, 2nd, 3rd, ... が true の場合Solve、解を見つけることに成功しています
  • 1st、2nd、3rd、... に false が含まれている場合は、バックトラックして別の方法を見つける必要があります
• 無限ループを避けるために、行ったことのある場所のバッファーを作成する必要があります
  • あなたが動きをするとき、それを監視し続ける必要があります
  • 行き止まりになったら、悪い動きを消す必要があります
  • 推測を焼き付けて、間違っている場合は削除することで上記を実装できます

ソリューションの擬似コードを次に示します。

boolean solve(int X, int Y)
{
    if (mazeSolved(X, Y))
    {
        return true;
    }

    // Test for (X + 1, Y)
    if (canMove(X + 1, Y))
    {
        placeDude(X + 1, Y);
        if (solve(X + 1, Y)) return true;
        eraseDude(X + 1, Y);
    }

    // Repeat Test for (X - 1, Y), (X, Y - 1) and (X, Y + 1)
    // ...

    // Otherwise force a back track.
    return false;
 }

Answer 2

おそらくプログラムをモジュール化する必要があります-私が理解しているように、ファイルから迷路を読み取り、同時に解決しようとしています。

より良いアプローチは、プログラムを 2 つの異なる部分に分割することです。

1. 入力ファイルを読み取り、すべてのデータを含む行列を作成します
2. 与えられた行列から迷路を解く

そうすることで、各部分を個別にビルドしてテストするのに役立ち、おそらくより優れた信頼性の高いプログラムになります。

迷路の解決は、単純なBFSによって行うことができます。これは、アルゴリズムが最初に提案したものに似ています。これはDFSです。

Answer 3

amit が言ったように、最初に迷路全体を読み取り、それを 2 次元配列として保存する必要があります。これにより、行ごとに解かなくても迷路全体を見ることができます。

最初に配列のサイズを見つける必要があるため、テキスト ファイルを文字列のリストに読み込む必要があります。

List<String> strs = new ArrayList<String>();

//Pseudocode, choose however you want to read the file
while(file_has_next_line) {
    strs.add(get_next_line);
}

List のサイズは行数を示します。常にグリッドであると仮定すると、split().length, (count space + 1) を使用するか、いずれかの文字列のシンボルを数えて列数を取得できます。 .

マップ データを格納する最も簡単な方法は、ブール値の 2D 配列を使用することです。true は壁、false は空きスペースです。

boolean[][] wallMap = new boolean[rows][cols];

for(int i = 0; i < wallMap.length; i++) {

    //Separate each symbol in corresponding line
    String[] rowSymbols = strs.get(i).split(" ");

    for(int j = 0; j < wallMap[i].length; j++) {

        //Ternary operator can be used here, I'm just keeping it simple
        if(rowSymbols[j].equals("X")) {
             wallMap[i][j] = true;
        } else {
             wallMap[i][j] = false;
        }

    }

}

マップ データが配列に格納されたので、マップを走査して選択するのがはるかに簡単になりました。既製のアルゴリズム (amit の回答を参照) を使用するか、独自のアルゴリズムを作成することができます。これは宿題なので、自分で考えてみてください。

楽しむ。

Answer 4

プログラムを 2 つのフェーズに分ける必要があります。1 つ目は、迷路の説明とプレイヤーの初期位置を読み取る初期化です。この後、ボードを表すデータ構造ができました。2 つ目は実際のゲームで、3 つの抽象化が必要です。

• プレイヤーの状態。あなたの場合、ボード上の実際の位置は非常に単純です。
• 環境である迷路そのもの。特定の位置を訪れたかどうか、訪れた位置をマークする機能、ゴールはどこか、次に到達可能なセルなどを示す機能が必要です...
• 検索アルゴリズムであるロジック。

これらのいずれも、他のものをあまり変更せずに変更できるはずです。たとえば、検索アルゴリズムを改善するよう求められる場合や、複数の目標がある問題を解決するよう求められる場合があります。現在の問題からわずかに変更された問題への切り替えの容易さは、プログラム設計の真の指標です。