問題タブ [depth-first-search]

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

人々のグループ[たとえば1874人]がいて、全員が世界のさまざまな会社[たとえば236人]を代表しています。私の仕事は、一人一人がどの会社で働いているかを最もよく特定することです。秘訣は、「どこで働いているのか」と単純に聞いて答えを出すことはできないということですが、私が持っているのは、いくつかの質問（たとえば290の質問）と従業員に期待すべき正確な回答を含む質問票です。各社の 答えが同じ会社もあるので、最終的には、どの会社に勤めているのか正確にわからなくても、絞り込んで、その会社に勤めなければならないと言うことができるはずです。

複数の値のマップと他のいくつかのデータ構造を使用して、1つの質問[クエリ]で識別できるすべての会社を特定するところまで行きました。これらのクエリを使用してツリーデータ構造のルートを表すには、他のクエリ/質問をブランチとして使用して残りのツリーを構築し、残りを識別する必要があります。

アドバイス/ヘルプ/提案はありますか？

状況は次のとおりです。

• アプリケーションの世界は、数十万の州で構成されています。
• 状態が与えられると、他の3つまたは4つの到達可能な状態のセットを計算できます。単純な再帰は、非常に速く非常に大きくなる状態のツリーを構築できます。
• ルート状態からこのツリーの特定の深さまでDFSを実行して、「最小」状態を含むサブツリーを検索する必要があります（ノードの値の計算は質問とは無関係です）。

シングルスレッドを使用してDFSを実行することは機能しますが、非常に低速です。15レベル下をカバーするには数分かかることがあり、この凶悪なパフォーマンスを改善する必要があります。各サブツリーにスレッドを割り当てようとすると、作成されるスレッドが多すぎて、が発生しましたOutOfMemoryError。を使用することThreadPoolExecutorはそれほど良くありませんでした。

私の質問：この大きな木を横断する最も効率的な方法は何ですか？

BFS と DFS の実行時間が O(V+E) である理由は、特に次のサイトのこの例のように、頂点から到達できるノードに有向エッジを持つノードがある場合です。

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

バックエッジhttp://cs.wellesley.edu/~cs231/fall01/dfs.pdfを検出することにより、DFS アルゴリズムでサイクルを検出できることは理解しています。上記の方法に従っている間、サイクル内のノードを効率的かつ「クリーン」な方法で出力する方法を理解できません。

いくつかの助けに感謝します

ありがとう

反復ごとに n-1 レベルのノードを再スキャンするのは冗長ではありませんか?

その瞬間、私はこのようなオブジェクトを持っています。

そして、ループを許可しないという事実を除けば、非常によく似た別のオブジェクトに変換しようとしています。

すでにより深い位置に出現しているノードの子を拡張しないことにより、ループを処理する必要があります。反復深化はこれを解決します（深さ優先探索の実装ですが、幅優先探索の順序）が、次の構造を使用した実装に苦労しています。

私が見つけたすべての実装は、ある種のゴールノードを見つけることに依存していますが、ツリー全体を拡張する必要があります。

どんな助けでもいただければ幸いです。：D

私はツリー（グラフの意味で）ツリー（物理的な意味で）の表現を持っています。ツリーは、各頂点に半径と位置のプロパティが含まれる BGL 隣接リストとして表されます。つまり、グラフは次の形式で定義されます。

ブランチのリストを作成するために、ツリーで DFS を実行したいと考えています。追加の要件は、頂点に複数の未探索の隣接頂点がある場合は常に、最大の半径を持つ頂点を選択することです。このルールにより、グラフの走査順序が物理的なツリー ブランチを表すようになります。

DFS ビジターはプライオリティ キューをサポートしていないようです。そのため、おそらく A* 経由でこの情報を取得する別の検索方式があるかどうか疑問に思っていました。

別の方法として、頂点をソートして独自の DFS アルゴリズムを実装することもできますが、可能であれば BGL フレームワークを活用したいと考えています。

ありがとう

-ジョン

3D形状のメッシュサーフェスを定義する三角形コレクションがあります。各三角形の法線を修正して、形を外したいと思います。

私は次のことを試みていました（疑似）：

1.最初の三角形の法線方向が正しい方向であることを定義します
2.次のようなDFSを使用してメッシュを通過します：
3。三角形=最初の三角形
4.triangle.getNeighboursのforeachneigbour5
.隣接する三角形と三角形の間の角度が180より大きい場合neighbor.flip（）
6.三角形=ネイバー
7.ネイバーがすでに選択されている場合は、次のネイバーに
進みます8.4に再帰的に進みます。

しかし、アルゴリズムのステップ5は、角度が180より大きいかどうかがわからないため、機能しません。これは、ウィッチ方向（時計回りまたは反時計回り）を知る必要があるためです。

アルゴリズムを修正する方法を理解するのを手伝ってもらえますか？

本 (Intro to Algorithm) によると、dfs では、エッジは 4 種類に分類されます。

1. ツリー エッジ、エッジ (u,v) で v が最初に検出された場合、(u, v) はツリー エッジです。
2. バック エッジ、……、v が既に発見されていて、v が先祖である場合、それはバック エッジです。
3. 前方エッジ、……、v が既に発見されていて、v が u の子孫である場合、前方エッジです。
4. クロス エッジ、上記 3 つを除くすべてのエッジ。

私の質問は、(u, v) がバック エッジかフォワード エッジかを把握しようとしているときに、v が u の祖先か子孫かをどのように識別できるかということです。