6

私は、最小数の右折と左折なしで迷路を解く必要があるプロジェクトに取り組んでいます。

右折が最小限に抑えられている限り、移動距離は関係ありません。バックトラッキング アルゴリズムと最適な (時間) アルゴリズムの両方を使用してプログラムを実装するよう求められます。

バックトラッキング アルゴリズムでは、スタックを使用するつもりでした。私のアルゴリズムは次のようになります。

  • スタック上の 4 つの可能な開始方向すべてをプッシュします。
  • 可能な限りまっすぐに進みます。
  • 迷路の終わりに到達すると、現在のパスの長さが最良のものとして返されます。
  • 行き止まりに到達した場合は、可能な限り最後の右折に戻り、それを取ります。
  • 現在のパスの長さが現在のベストよりも長い場合は、可能な限り最後の右折に戻り、それを実行します。

誰かがこれに最適なアルゴリズムの方向に私を向けることができるかどうか疑問に思っていました.

バックトラックよりも良いものを考えるのに苦労しています。

4

2 に答える 2

7

最初に右折 0 回で到達できるすべてのポイントを見つけることでできると思います。次に、右折を 1 回だけ行います。そのためにキューを使用できます。n 番目のフェーズでは、n 回の右折で到達できるすべてのポイントの最適解が得られていることに注意してください。さらに、まだ到達していないポイントは、> n ポイントで到達可能であるか、まったく到達できません。最適な時間計算量を実現するには、適切な方向に未到達の隣接点がある到達点からのみ、新しい到達可能点を検索する必要があるという事実を使用する必要があります。すべてのポイントには 4 つの近傍しかないため、そこから 4 回だけ検索します。これは、方向 D ごとに個別のリストを維持することで実装できます。これには、到達したすべてのポイントと、その方向に未到達の隣接ポイントが含まれています。

以下に、グラフィカルな例を示します。

 .  .  .  .  .  .   (0) .  .  .  .  .    0  1  1  1  1 (1)   0  1  1  1  1  1
 .  #######  .  .    0  ##########  .    0  ##########  .    0  ##########  2
 .  #  .  #  .  .    0  #  .  #  .  .    0  #  .  #  .  .    0  #  .  #  . (2)
 .  #  .  .  .  .    0  #  .  .  .  .    0  #  .  .  .  .    0  #  .  .  . (2)
 .  ####  .  #  .    0  ####  .  #  .    0  ####  .  #  .    0  ####  .  #  2
(.) .  .  .  .  .   (0) .  .  .  .  .    0  1  1  1  1  1    0  1  1  1  1  1

 0  1  1  1  1  1    0  1  1  1  1  1
 0  ##########  2    0  ##########  2
 0  #  .  #  3  2    0  #  4  #  3  2
 0  # (3) 3  3  2    0  #  3  3  3  2
 0  ####  .  #  2    0  ####  4  #  2
 0  1  1 (1) 1  1    0  1  1  1  1  1

( )未到達の適切な隣接点を持つ到達点を示す

于 2011-04-09T23:00:44.080 に答える
4

迷路のすべての位置に対して 4 つのノードを構築してグラフを作成します。すべてのノードは、N、S、E、W の特定の方向に対応します。

すべてのノードとそれに隣接する最大 3 つのノードの間にエッジがあります: 「前」、「後」、「右」 (存在する場合) のエッジです。「前」と「後」のノードにつながるエッジの重みは 0 になります (パスの長さは重要ではないため)。一方、「右」のノードへのエッジの重みは 1 になります (これは、右折のコスト）。

グラフが設定されると (これを行う最善の方法は、迷路の元の表現を再利用することです)、幅優先探索アルゴリズムの修正版が問題を解決します。

0/1 のエッジ ウェイトを処理する秘訣は、標準のキュー実装の代わりに両端キューを使用することです。具体的には、重みが 0 のエッジを介して到達したノードは両端キューの前にプッシュされ、重みが 1 のエッジを介して到達したノードは後ろにプッシュされます。

于 2011-04-09T23:00:05.017 に答える