4

そのため、キュー、セット、ロケーション オブジェクト、および最終的に Maze オブジェクトになる Cell オブジェクトを使用して、迷路ソルバーを作成する必要があります。

完成したときに本質的にすべてのコードが何をするかを簡単に見てみましょう。

7
10
   _ _ _ _ _ _ _ _ _
|_ _ _  |  _ _   _  |
|  _ _| | |  _  |   |
| |   | |_| | | |_| |
|_ _|_ _   _| |_  | |
|  _    | |  _ _| |_|
| |_ _|  _|   |_    |
|_ _ _ _|_ _|_ _ _| |

これに：

 @ _ _ _ _ _ _ _ _ _
|@ @ @ @|  _ _   _  |
|  _ _|@| |@ @ @|   |
| |   |@|_|@| |@|_| |
|_ _|_ @ @ @| |@ @| |
|  _    | |  _ _|@|_|
| |_ _|  _|   |_ @ @|
|_ _ _ _|_ _|_ _ _|@|
                   @

これまでのところ、私が行ったことはすべて非常にうまくいっていますが、Maze オブジェクトで findPath() メソッドを実際にコーディングすると、私のコードは無効なパスを生成します。ファイルを取り込んで迷路を読み取ると、その迷路を多次元文字配列に変換し、その文字配列をセルの多次元配列に変換し、各セルの境界を北、南、東、西にマップしますブール値。

さて、実際に迷路をナビゲートする方法を理解することになります.MazeのfindPath（）メソッドで試みましたが、実際には失敗しました.

 @  @  @  @  .  .  .  .  .  . 
 .  .  .  @  .  .  .  .  .  . 
 .  @  @  @  .  .  .  .  .  . 
 .  @  @  @  @  .  .  .  .  . 
 .  .  @  @  @  .  .  .  .  . 
 .  @  @  @  @  .  .  .  .  . 
 .  .  .  .  .  .  .  .  .  .

まず、私が達成すべきことを説明するために、私の要件ドキュメントを見てみましょう。

The algorithm operates according to the following pseudo-code:

* Visit the starting Location.
* Add this Location to the set.
* Enqueue the Location in the queue.

while (ArrayQueue<E> != empty( )) 
{
    Dequeue a Location(next) from the queue

        For each neighbor of Location(next) which has
         not yet been placed in the set, repeat:
                * Visit the neighbor of Location(next).
                * Add the neighbor of Location(next) to the Set.
                * Enqueue the neighbor of Location(next)in the Queue.
 }

彼のアルゴリズムをある程度正しく使用したことはほぼ間違いありませんが、遭遇したパスを取得するために何が間違っていたのかわかりません。私の最大の頭痛の種は、以下に示した Maze オブジェクトの findPath() メソッドにあります。私の最大の質問は、何が間違っているのでしょうか? 私は何日もこれに取り組んできましたが、これを理解することはできません. どんな助けでも大歓迎です。私のコードは以下の通りです：

My Maze の findpath メソッド

public void findPath()
{
    Location startLocation = new Location(0, 0);
    theMaze[startLocation.getRow()][startLocation.getColumn()].setVisited(true);

    Location endLocation = new Location(6, 9);

    Location cursor;

    locationQueue.enqueue(startLocation);
    locationSet.enter(startLocation);

    while(!locationQueue.isEmpty())
    {
        cursor = locationQueue.dequeue();

        if(cursor == endLocation)
            break;

        for(int i = 0; i < 4; i++)
        {
            Location temp = cursor.getLoc(i);

            if(theMaze[cursor.getRow()][cursor.getColumn()].validDirection(i) && (!locationSet.isElement(temp)) && !(theMaze[temp.getRow()][temp.getColumn()].isVisited()))
            {
                cursor = cursor.getLoc(i);
                theMaze[cursor.getRow()][cursor.getColumn()].setVisited(true);

                if(theMaze[cursor.getColumn()][cursor.getColumn()].getPathAmount() < 2)
                {
                    cursor = startLocation;
                    continue;
                }

                locationSet.enter(cursor);
                locationQueue.enqueue(cursor);                          
            }               
        }           
    }

    for(int i = 0; i < locationSet.size(); i++)
    {
        System.out.println("Row " + locationSet.get(i).getRow() + " Column " + locationSet.get(i).getColumn());
        theMaze[locationSet.get(i).getRow()][locationSet.get(i).getColumn()].setPath();
    }

    for(int i = 0; i < theMaze.length; i++)
    {
        for(int j = 0; j < theMaze[i].length; j++)
        {
            System.out.print(theMaze[i][j].toString());
        }
        System.out.print("\n");
    }

}

編集:私の問題は、他のクラスではなく Maze オブジェクトにあるため、基本的にクリーンアップしています。

4

1 に答える 1

3

基本的なアルゴリズムに欠陥があります。パスにセルを追加するだけで、行き止まりになった場合は削除しないでください。

この種の問題は、再帰アルゴリズムに最適です。

function findExit(gameMap, listOfVisitedCells, currentCell, solution)
    listOfVisitedCells.add(currentCell);
    for each gameMap.NeighbourOf(currentCell)
        if neighbour not in listOfVisitedCells
             solution.add(neighbour)
             if (gameMap.isExit(neighbour)) {
               return true;
             }
             if (findExit(gameMap, listOfVisitedCells, currentCell, solution)) {
               return true;
             }
             solution.remove(neighbour);
        }
    }
    // No neighbours of the current cell got to find the exit.
    return false;
 }

もちろん、これはマップを深さ優先で探索するため、複数のパスが有効な場合、最短パスを見つける保証はありません (そのためには Djikstra のアルゴリズムを使用します)。

更新:コードのレビューから:

非常に多くのコード行を精神的にデバッグすることは困難であり、SO は、選択したデバッガーで公正な時間を過ごしたり、プログラムの実際の状態と期待される状態などを監視したりする代わりにはなりません。あまり期待しないでください。SO は、限られた量のコードで具体的な質問 (「このコードはこれを行うと予想していますが、そうではない、なぜですか」) に適しています。

とにかく、これは私を奇妙に思います:

        Location temp = cursor.getLoc(i);

        if(theMaze[cursor.getRow()][cursor.getColumn()].validDirection(i) && (!locationSet.isElement(temp)) && !(theMaze[temp.getRow()][temp.getColumn()].isVisited()))
        {
            cursor = cursor.getLoc(i);       <-- Why are you overwritting the current
                                             <-- location when you have still not checked
                                             <-- all the posible directions?
            theMaze[cursor.getRow()][cursor.getColumn()].setVisited(true);

            if(theMaze[cursor.getColumn()][cursor.getColumn()].getPathAmount() < 2)
            {
                cursor = startLocation;
                continue;
            }

            locationSet.enter(cursor);
            locationQueue.enqueue(cursor);                          
        }

これは正しくないと思います。もちろん、別の問題が隠されている可能性があります。自分でデバッグして、期待どおりに動作しないフラグメントを見つけた方がよいでしょう (そして、より多くの経験が得られます)。

于 2013-04-04T09:30:17.050 に答える