問題タブ [maze]

迷路を解くためのバックトラッキングアルゴリズムを実装しようとしている部屋検索アルゴリズムを誰かが手伝ってくれるかどうかを探しています。すでに訪れた部屋を覚えておかなければならない場所で立ち往生しています。
迷路は部屋で構成されており、各部屋には北、東、南、西の4つの側面があります。各部屋は、希望する側にドアを作成することで次の部屋にリンクされます。つまり、room1.createNorth(roomName) 北に新しい部屋が作成され、新しい部屋には、私の部屋のクラスでわかるように、最初の部屋にリンクする南のドアがあります。

これが私の刻んだ部屋のクラスで、迷路の中の各部屋を表しています。北側を扱う方法と同じ南、西、東の方向を削除しました。

迷路は次のようになります：http：//i.stack.imgur.com/2KePs.jpgここで、Sは開始点です

私の迷路のクラス

これが私のメインクラスのパブリッククラスですMain{

問題はfindPathTo(roomName)、部屋へのルートを見つける私の方法にあります。部屋D4に入ると、アルゴリズムは「A4」から「B4」の部屋に東に1回だけ移動し、そこで無限にループし、スタックは部屋「B4」だけで大きくなります。たとえば、隣の部屋「B3」や「C4」に進んでみませんか？

編集：ここに作業コードがあります

基本的に、私はこれを持っています：最初に、コードの束は、横断できない迷路を生成します。いくつかのパラメータに基づいて、2D配列の特定のスペースに壁をランダムに設定します。次に、バックトラッキングアルゴリズムを使用して、すべてが通過可能になるまで壁をノックアウトします。問題は、プログラムがスタックに戻っていないように見えることです。

これはかなり標準的なバックトラッキングコードです。アルゴリズムはランダムな場所から始まり、擬似コードで進行します。

move（x、y）{上に移動
でき、まだ行っていない場合：
move（x、y --1）
右に移動でき、まだ行っていない場合：
move（x + 1、y）
。 ..
}

他の方向についても同様です。移動するたびに、ブール値の2つの別々の2D配列（1つは一時的、もう1つは永続的）が座標に設定され、特定の要素にいることを示します。それ以上進むことができなくなると、永続的な2D配列をチェックして、どこにでもあるかどうかを確認します。そうでない場合は、訪問済みスペースと非訪問済みスペースの間にある壁をランダムに選択し（一時的な配列に従って）、それを削除します。このすべてがwhileループで呼び出されるため、迷路のチャンクを通過すると、一時的な2D配列がリセットされ、もう一方は保持され、永続的な2D配列が迷路全体にトラバースされました。moveメソッドのチェックは、永続的な配列ではなく、一時的な2D配列と比較されます。

これはほぼ機能しますが、最終的に生成された迷路の中で到達できない領域をいくつか見つけ続けました。そうでなければ、それは私が望むように迷路を生成するという素晴らしい仕事をしています。問題は、これの理由は、スタックに完全に戻らないことであることがわかりました。

永続的なものではなく一時的な2D配列の完了を確認するように変更すると（したがって、複数の反復にわたって完全な実行を行うのではなく、1回の実行で1回の完全なトラバーサルを実行して、完了をマークします）、継続しますと。私はそれを壊すためにカウンターを設定する必要があります。その結果、非常に多くの壁が削除された「迷路」ができあがります。アルゴリズムがたどるルートを確認すると、アルゴリズムが適切にバックトラックされておらず、スタック内で十分に遠くまで戻っておらず、理由もなく終了したと宣言する前に、単一の要素で数十回の再帰でスタックすることがよくあります。まったく、ゼロの壁を削除する必要があります。

以前のものを2回実行してみましたが、ノックアウトする必要のない壁をノックアウトし続け、迷路をまばらにしすぎています。なぜこれが起こっているのか私にはわかりません。

プログラミングコンテストに向けて練習していて、過去に答えることができなかったいくつかの難しい問題に取り組んでいます。それらの 1 つは王の迷路でした。-50<x<50基本的に、 「トークン」を表す数値の NxN 配列が与えられます。位置 1,1 から開始し (配列インデックスでは 0,0 であると仮定します)、N,N で終了する必要があります。訪問したセルでトークンを取得する必要があり、トークンのないセル (0 で表される) を踏むことはできません。0 に囲まれると負けです。迷路に解決策がない場合は、「解決策なし」と出力します。それ以外の場合は、拾ったトークンを合計して得られる最大の数を出力します。

この問題を解決する方法がわかりません。それを解くための迷路アルゴリズムを書けると思ったのですが、それには時間がかかります。プログラミング コンテストでは、複数の問題を解くのに 2 時間しか与えられません。見落としているパターンがあると思います。これにどのようにアプローチすればよいか知っている人はいますか？

また、この問題は高校生向けであることを言及しておくと役立つかもしれません。

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

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

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

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

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

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

ノードからその隣接ノードへの訪問をランダム化するのに問題があります。グラフ全体（このテストでは4x4のMxN配列）が訪問されることはめったにありません。ここで間違っていることがわかりません。

このコードは私に次のような出力を与えています：

次の移動の位置を検証していますが（ブール値southValid、eastValidなどを介して）

Java での DFS 迷路の生成では、DFS の再帰呼び出しが行われる順序をランダム化したい:

どうやってやるの？

WPFでボックスのレイアウトを生成するためのユーザーコントロールを提供しようとしています。行と列を追加/削除し、各ボックスを0度または45度のいずれかで回転するように設定できるようにしたいと思います。結果は、一種の正方形のハニカムになります。ListBoxとWrapPanelを使ってこれに取り組むことを考えていましたが、考えてみると、Canvasの方が良いと思います。私が従うことができる簡単な方法論はありますか、それともキャンバスの位置で試行錯誤するだけですか？

ゲームに深さ優先探索アルゴリズムを実装しようとしています。私はこの Web ページを研究してきました: http://www.mazeworks.com/mazegen/mazetut/index.htm、壁の代わりにブロックで使用できないことがわかりました。ブロックとは、エッジだけでなく、セル全体を覆う正方形のことです。この方法の方が簡単だと思っていましたが、今はよくわかりません。誰かがこれをしましたか？もしそうなら、どのように？（疑似コードは問題ありません）。または、簡単な場合は、壁の方法を使用する必要がありますか?

隣接リストとして表される複数の「迷路」を含むテキスト ファイルからグラフを作成する必要があります。リストは次のとおりです。

各「迷路」の最初の行には、迷路の開始ノード (最初の文字) と迷路の終了ノード (2 番目の文字) が含まれています。

テキスト ファイルをすべての行 (空白行を含む) の ArrayList に解析し、次に行の ArrayLists の ArrayList (個別の迷路のリスト) に解析しました。これを行うには、テキスト全体を空白行で分割しました。私の問題は、ノードクラスを使用してこれらの「迷路」からグラフを作成する方法がわからないことです。ここに私のノードクラスがあります:

誰かが私を正しい方向に向けることができますか?

部屋のドアのリストを定義しました：

そしていくつかの述語:

そして、私は部屋から部屋への道を探しています：

この述語は機能し、以下を返します。

Jest droga:フェバ

Jest droga:フェデクバ

これは、a から f に渡さなければならない部屋のリストです。run():- stdio::write("\nDroga zf do a"), R_list=["f"], go("f", "a", R_list), 失敗。しかし、これは何も返しません。お気づきかもしれませんが、これは前のケースの逆です。