1

セルのあらゆる方向にやみくもに実行して、ゴールが見つかったかどうかを確認する単純な迷路探索アルゴリズムを作成しました。ゴールを見つけることができますが、ゴールが見つかったときに他の再帰呼び出しを終了せず、ゴールへの可能なパスを 1 つだけではなく、行ったすべてのパスを描画するため、ソリューションはまだ悪いです。どうすればそれを改善できますか？

疑似コードの基本的なアルゴリズムは次のようになります。

function searchMaze(start_point, end_point, maze) {

 // If current point is goal I would like to abort other recursive calls
 if(start_point.equals(end_point)) {
   pathFound = true;
   drawPathInArray(); 
    return;
  }
 else {
    // if current point is not inside the array
   if(start_point_not_within_array)
   return
   else {
     // if current point is a wall or a cell that has already been visited
     if(cell_is_wall || cell_is_visited)
       return;
      else {
           // mark cell as possible path
           markCellInPathArray("#");
           setCellVisited();
           searchMaze(left_from_start_point, end_point, maze);
           searchMaze(right_from_start_point, end_point, maze);
           searchMaze(above_start_point, end_point, maze);
           searchMaze(below_start_point, end_point, maze); 
      }
   }
  }
}
4

3 に答える 3

1

関数がブール値を返すようにします。ゴールへの道が見つかった場合はいつでも true を返し、それ以外の場合は false を返します。いずれかの再帰呼び出しから true の戻り値を取得したら、戻ります。

関連する変更は、適切な return ステートメントであり、4 つの再帰呼び出しを次のように変更します。

if (searchMaze(left_from_start_point, end_point, maze))
  return true;
if (searchMaze(right_from_start_point, end_point, maze))
  return true;
if (searchMaze(above_start_point, end_point, maze))
  return true;
if (searchMaze(below_start_point, end_point, maze))
  return true;

また、最後に a を付けるべきではありませんsetCellNotVisited()か？

注:pathFound変数 (おそらくクラス変数)が既にあるようです。この場合、マルコの解決策がおそらく好まれますが、代わりに戻り値に変更する方がよい場合があります。

于 2013-04-19T10:21:41.630 に答える
1

各再帰呼び出しにフラグを追加する必要があります。

pathFound = pathFound || searchMaze(left_from_start_point, end_point, maze);
pathFound = pathFound || searchMaze(right_from_start_point, end_point, maze);
pathFound = pathFound || searchMaze(above_start_point, end_point, maze);
pathFound = pathFound || searchMaze(below_start_point, end_point, maze);

pathFound が true の場合、呼び出しは無視されます。

于 2013-04-19T10:22:09.403 に答える
1

else ブロックで true を設定すると、

1) cell_is_wall when wall is visited 
2) set start_point_not_within_arrary when it is not in the array

その後、コードが機能するはずです。他の再帰呼び出しは、すでに持っているこれらの条件付きチェックによって処理されます。

于 2013-04-19T10:23:18.647 に答える