2

フラッド フィル アルゴリズムのバージョンを実装して、マイクロ マウスの迷路の最短距離パスを解決しようとしています。埋められていない隣接する各場所に、その場所から開始場所までの距離を表す番号が割り当てられることを除いて、通常の塗りつぶしと同じように機能します。アルゴリズムが別のセルに移動するたびに、数値が 1 ずつ増加します。左下隅から始まる壁のない迷路の例を次に示します。

2 3 4
1 2 3
0 1 2

ここに私が持っている現在のコードがあります...

void nav_flood_rec(struct nav_array *array, int row, int column, int flood_num)
{
    //Check the base case (not shown here)
    if (base_case)
        return;

    //Assign the flood number
    arrray->cells[row][column]->flood_number = flood_num;

    //North
    nav_flood_rec(array, row + 1, column, flood_num + 1);

    //East
    nav_flood_rec(array, row, column + 1, flood_num + 1);

    //South
    nav_flood_rec(array, row - 1, column, flood_num + 1);

    //West
    nav_flood_rec(array, row, column - 1, flood_num + 1);
}

私が抱えている問題は、再帰が一度に1ステップずつ進んでいないことです(漠然としていますが、説明させてください)。すべての方向を確認してからアルゴリズムに進む代わりに、北に移動し続け、他の方向は確認しません。他の方向がチェックされるまで、他の再帰呼び出しをどうにかして譲りたいようです。誰か提案はありますか？

4

3 に答える 3

4

深さ優先検索に似たものを実装しましたが、説明しているのは幅優先検索が必要なように聞こえます。

スタックの代わりにキューを使用します。ここではスタックを明示的に使用していませんが、再帰は本質的に暗黙のスタックです。キューは、スタック オーバーフローの問題も解決します。

また、G.Bach が言うように、アルゴリズムが終了するようにセルを訪問済みとしてマークする必要があります。

于 2013-04-03T00:07:56.977 に答える
1

件名に関するウィキペディアの記事：

明示的なキューベースの実装を以下の疑似コードで示します。これは単純な再帰ソリューションと似ていますが、再帰呼び出しを行う代わりに、消費のためにノードを LIFO キュー (スタックとして機能) にプッシュする点が異なります。

 Flood-fill (node, target-color, replacement-color):
 1. Set Q to the empty queue.
 2. Add node to the end of Q.
 4. While Q is not empty: 
 5.     Set n equal to the last element of Q.
 7.     Remove last element from Q.
 8.     If the color of n is equal to target-color:
 9.         Set the color of n to replacement-color.
 10.        Add west node to end of Q.
 11.        Add east node to end of Q.
 12.        Add north node to end of Q.
 13.        Add south node to end of Q.
 14. Return.
于 2013-04-03T00:14:44.607 に答える
1

north()条件をテストせずに呼び出します。したがって、再帰は次の順序で行われます。

  • 1) ベースケースのテスト
  • 2) 新しいフラッド番号を設定する
  • 3) 出会い//northと呼び声nav_flood_rec()
  • 4)繰り返します。

ご覧のとおり、他の通話に到達することはありません。テスト条件を実装したり、分岐したりする必要があります。

何をしようとしているのかよくわかりませんが、別の構造体をパラメーターとして渡し、各方向の値を持ち、それらが等しいかどうかをテストできます...のように...

struct decision_maker {
  int north;
  int south;
  int west;
  int east;
};

次に、コードで：

/* assume dm is passed as a pointer to a decision_maker struct */

if (dm->north > dm->south) {
  if (dm->south > dm->east) {
    dm->east++; // increment first
    // call east
  } else if (dm->south > dm->west) {
    dm->west++; // increment first
    // call west
  } else {
    dm->south++;
    // call south
} else {
    dm->north++;
    // call north
}
/* 
*  needs another check or two, like altering the base case a bit
*  the point should be clear, though.
*/

少し面倒になりますが、仕事はします。

于 2013-04-03T00:37:42.767 に答える