2

幅優先探索を使用して迷路ソルバーを作成し、文字「*」を使用して最短経路をマークしようとしています。

迷路は実際には単なるテキストの集まりです。迷路は、壁である「＃」記号とピリオド「。」で構成されるnxnグリッドで構成されます。歩行可能なエリア/パスを表します。「S」は開始を示し、「F」は終了を示します。現在、この関数は解決策を見つけていないようです（不可能な場合でも解決策があると考えています）。私は4つのネイバーをチェックしていますが、それらが「不明」（-1）の場合、処理されるキューに追加されます。

迷路はいくつかの迷路で機能しますが、これでは機能しません。

...###.#.... 
##.#...####.
...#.#.#....
#.####.####.
#F..#..#.##.
###.#....#S.
#.#.####.##.
....#.#...#.
.####.#.#.#.
........#...

私のロジックには何が欠けている可能性がありますか？

int mazeSolver(char *maze, int rows, int cols)
{
int start = 0;
int finish = 0;
for (int i=0;i<rows*cols;i++) {
    if (maze[i] == 'S') { start=i; }
    if (maze[i] == 'F') { finish=i; }
}
if (finish==0 || start==0) { return -1; }

char* bfsq;
bfsq = new char[rows*cols]; //initialize queue array
int head = 0;
int tail = 0;
bool solved = false;
char* prd;  
prd = new char[rows*cols]; //initialize predecessor array
for (int i=0;i<rows*cols;i++) {
    prd[i] = -1;
}
prd[start] = -2; //set the start location
bfsq[tail] = start;
tail++;

int delta[] = {-cols,-1,cols,+1};   // North, West, South, East neighbors

while(tail>head) {
    int front = bfsq[head];
    head++;
    for (int i=0; i<4; i++) {
        int neighbor = front+delta[i];
        if (neighbor/cols < 0 || neighbor/cols >= rows || neighbor%cols < 0 || neighbor%cols >= cols) {
            continue;
        }
        if (prd[neighbor] == -1 && maze[neighbor]!='#') {
            prd[neighbor] = front;
            bfsq[tail] = neighbor;
            tail++;
            if (maze[neighbor] == 'F') { solved = true; }
        }   
    }
}

if (solved == true) {   
    int previous = finish;
    while (previous != start) {
        maze[previous] = '*';
        previous = prd[previous];
    }
    maze[finish] = 'F';
    return 1;
}
else { return 0; }

delete [] prd;
delete [] bfsq;

}
4

2 に答える 2

0

ネイバーを反復処理することは大幅に簡略化できます（これはkobraが提案するものと多少似ていますが、さらに改善することができます）。次のように、指定された移動のxおよびyデルタを定義する移動配列を使用します。

int moves[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

tisは、特定のセルからのすべての可能な移動を一覧表示するだけでなく、時計回りの方向にも一覧表示することに注意してください。これは、いくつかの問題に役立ちます。次に、配列をトラバースするために、を使用します。std::queue<pair<int,int> >この方法で、現在の位置は、それに対応する座標のペアによって定義されます。これが私がgienセルcの隣人を循環する方法です：

pair<int,int> c;
for (int l = 0;l < 4/*size of moves*/;++l){
  int ti = c.first + moves[l][0];
  int tj = c.second + moves[l][1];
  if (ti < 0 || ti >= n || tj < 0 || tj >= m) {
    // This move goes out of the field
    continue;
  }

  // Do something.
}

このコードは実際にはあなたのコードとは関係がないことは知っていますが、私がこの種の問題を教えているので、私がこのアプローチを示したとき、多くの学生が本当に感謝していたと信じています。

ここで質問に戻ります。終了位置から開始し、prd配列を使用してその親を見つけ、次にその親の親を見つけるというように、負の親を持つセルに到達するまで続ける必要があります。代わりに、訪問したすべてのセルを考慮し、それらの一部はからSへの最短経路上にありませんF。

これを設定solved = trueすると、アルゴリズムが少し最適化されます。

個人的には、フィールドから落ちるチェックがないので、常に解決策を見つけると思います。（if (ti < 0 || ti >= n || tj < 0 || tj >= m)私のコードのビット）。

これがあなたを助け、あなたのコーディングを改善する方法のいくつかのヒントを与えることを願っています。

于 2012-11-04T20:12:23.377 に答える
0

いくつかのコメント：

  1. キューコンテナはC++で使用でき、はるかに使いやすくなっています。
  2. このタスクでは、次のようなものを書くことができます。
int delta[] = {-1, cols, 1 -cols};

そして、4つの側面すべてを単純に繰り返すことができます。同じコードをコピーして、貼り付けることはできません。

  1. 配列の境界に問題が発生します。あなたはそれをチェックしていないからです。
  2. フィニッシュを確立したら、サイクルから抜け出す必要があります
  3. そして最後のサイクルでエラーが発生しました。それはあなたがいたすべてのセルに*を印刷します（最適な方法だけでなく）。次のようになります。
while (finish != start)
{
  maze[finish] = '*';
  finish = prd[finish];
}
maze[start] = '*';

そしてもちろん、このサイクルは最後にすべきです。なぜなら、その瞬間にあなたが終わりに到達したかどうかわからないからです。

PSそしてあなたが機能で割り当てたメモリをクリアする方が良いです

于 2012-11-04T19:45:48.483 に答える