4

迷路を通過するための一連の if-then ルールを作成する際に助けが必要です。これが問題です：

「迷路は、迷路内の任意のセルから壁のない迷路の外縁までの経路が存在するように、セルのいくつかのエッジを横切って壁を配置することにより、正方形のセルのグリッド上に構築されていると仮定します.

1 つの方法は左手の法則ですが、この戦略では循環的に移動できます。

壁を横断してサイクルを検出するための if-then ルールを英語で記述します。グリッドのサイズと、迷路から逃れるために移動しなければならない最大距離を知っていると仮定します。」

これは私がこれまでに持っているものです:

  1. 始める

  2. パスが 1 つだけ (左または右またはストレート) 見つかった場合は、そのパスに従います。

  3. Else 複数のパスが見つかった場合:

    左の道が見つかった場合は、左折します。

    それ以外の場合は、直線パスが見つかった場合は、直線パスに従います。

    そうでなければ、正しい道が見つかったら、右折してください。

  4. それ以外の場合は、行き止まりが見つかった場合、「U」ターンを行います。

    ステップ 2 へ

  5. 終わり

しかし、これはサイクルの問題を解決していません。誰でも助けてもらえますか？

4

1 に答える 1

3

グラフを探索するための一般的なアルゴリズムには、幅優先探索 (BFS) と深さ優先探索 (DFS) の 2 つがあります。これらのアルゴリズムの秘訣は、未調査リスト内のすべてのパスから開始し、パスにアクセスすると、それらを調査済みリストに追加することです。各ノードにアクセスすると、そのノードは未調査リストから削除され、再度アクセスすることはありません。それぞれの場合に未調査のリストからノードを引き出すだけで、自分自身を倍増させるケースはありません.

サイクルと BFS を防ぐためのチェックを含む DFS の例を次に示します。

function DFS(G,v):
  label v as explored
  for all edges e in G.adjacentEdges(v) do
      if edge e is unexplored then
          w ← G.adjacentVertex(v,e)
          if vertex w is unexplored then
              label e as a discovery edge
              recursively call DFS(G,w)
          else
              label e as a back edge

今 BFS:

procedure BFS(G,v):
  create a queue Q
  enqueue v onto Q
  mark v
  while Q is not empty:
      t ← Q.dequeue()
      if t is what we are looking for:
          return t
      for all edges e in G.adjacentEdges(t) do
           u ← G.adjacentVertex(t,e)
           if u is not marked:
                mark u
                enqueue u onto Q
  return none
于 2013-05-16T02:46:22.067 に答える