問題タブ [graph-algorithm]

まず・・・問題は・・・

有向グラフ G = (V, E)、V のソース頂点 s、および E に含まれる一連のツリー エッジ F の例を示して、V に含まれる各頂点に対して、グラフ内の一意の単純なパス ( V, F) s から v への最短経路は G の最短経路ですが、頂点が各隣接リストでどのように順序付けられていても、エッジのセット F は G で BFS を実行しても生成できません。

さて...これは宿題なので、率直な答えは望んでいませんが、見たり試したりするためのアイデアがもっと欲しいです. でも、ここまでで思ったことは…

私は基本的に、特定の頂点へのいくつかの最短経路を持つグラフを作成できると考えました。もちろん、これらのパスの 1 つは BFS にあります。しかし、代替ルートの 1 つを使用して F に適合させることができます。ただし、「頂点がどのように順序付けられていても」私を悩ませている部分は...それをどのように私の処理する。ループ、さまざまな方向フローを試しましたが、まだ何も試していません。

他のアイデアはありますか？

C# で組織ツリー グラフ (上から下または左から右) を実装しており、ツリーを描画するための適切なアルゴリズムを探しています。推奨事項はありますか？

ありがとう

アップデート

ようやく作業する時間ができたので、カスタムパネルを作成してツリーを保存および描画するための独自のライブラリを作成することになりました。特定のアルゴリズムに従っているかどうかわからないので、自分で作成しました-ペンと紙+時間に戻ります:)

必要な機能をすべて追加したら、codeplex でオープン ソースにするつもりです。codeplex にアップしたら、別の更新を投稿します。

ありがとう

一般的な言語 (Java、C#、Ruby、JavaScript など) には、ある種の成熟したNo-three-in-line 問題アルゴリズムがありますか?

ありがとう。

次の問題に直面しました。

• 互いに素な集合が 2 つありA、B
• 要素の各ペア ( a, b) ( aset に属し、 setAにb属するB) の確率pijは事前にわかっています。aこれは、 と一致する確率 (確実性レベル)、bつまり、どの程度a一致するか (および==bであるため、その逆も同様) を表します。pijpji
• 確率/確実性が最も高いマッチングを見つけ、マッチングを説明するペア ( a、b) を見つける必要があります。
• すべての要素は、他のセットの別の要素と1回だけ一致/ペアにする必要があります（標準の2部一致問題のように）
• 可能であれば、得られたマッチングの不確実性レベルを近似的に表す数値を計算したいと思います (0 はランダムな推測を表し、1 は確実性を表すとしましょう)。

そのようなアルゴリズムが必要とされる簡単な実用的な例を以下に示します (これは実際に私が解決しようとしている問題ではありません!):

• 2 人が紙に a ～ z の文字を書くように求められる
• 文字 ( a, ) の各ペアに対して、パターン マッチャーを実行して、人によって書かれた文字が人によって書かれた文字を表すb確率を決定します。これにより、文字の各ペア ( , )に対するある種の類似性相関を表す確率行列が得られます。aAbBab
• その人が書いた各文字について、その人Aが書いた対応する文字を見つける必要がありますB

現在のアプローチ:セットの要素がaセットの要素とA一致する確実性レベル/確率の対数に比例する重みを割り当ててから、最大加重二部マッチングを実行して最大合計を見つけること ができるかどうか疑問に思っています。対数は、複数の一致の合計確率を最大化したいためであり、単一の一致 (一致した要素のペアとして表される-bBab) 確率の積である一連のイベントを形成します。対数を取ることにより、これを確率の合計に変換します。これは、ハンガリーのアルゴリズムなどの加重二部マッチングのアルゴリズムを使用して簡単に最大化されます。しかし、私は、このアプローチが統計上の期待最大値の点で最良のマッチングを保証するとはどういうわけか疑問に思っています。

少し検索した後、私が見つけた最も近い問題は、NP困難である2段階の確率的最大加重マッチング問題でしたが、実際にはある種の「1段階」の確率的最大加重マッチング問題が必要です。

私の状況を理解するために少し時間を取ってください。わからない場合はコメントで教えてください。

ウェイポイントのArrayListがあります。これらのウェイポイントは順不同です。ウェイポイントには次のプロパティがあります。
{int type, float z, float y, float x, float rotation}

これは3次元の世界に適用されますが、私のパスファインディングは高さを気にする必要がないため（したがって、世界を2次元の世界として扱う）、y値は無視されます。この質問では、回転は重要ではありません。

• この2次元の世界では、xはx軸を表し、zはy軸を表します。
• xが増加すると、世界のオブジェクトは東に移動します。xが減少すると、世界のオブジェクトは西に移動します。
• zが大きくなると、世界のオブジェクトは北に移動します。zが減少すると、世界のオブジェクトは南に移動します。

したがって、これらの「新しい」ウェイポイントは次のように簡略化できますwaypoint = {float x, float y}。

現在、これらのウェイポイントは、オブジェクトのX軸（x）とY軸（z）の位置を表しています。さらに、現在の場所：curLocation = {float x, float y}とターゲットの場所：がありtarLocation = {float x, float y}ます。

これが私が取得したいものです：次の厳しい条件下でからに
つながるウェイポイント（別名：パスまたはルート）のすべての組み合わせ：curLocationtarLocation

1. 各ウェイポイント間の距離は、より大きくすることはできません(float) maxInbetweenDistance。これには、curLocation最初のウェイポイントからの最初の距離と、最後のウェイポイントからのまでの距離が含まれtarLocationます。そのようなウェイポイントの組み合わせが不可能な場合は、nullを返す必要があります。
2. ターゲットウェイポイントにつながるウェイポイントから複数のウェイポイントが見つかった場合maxInbetweenDistanceは、最も近いウェイポイントを選択する必要があります（少し離れた別のウェイポイントが、より長い距離の新しいパスになり、これも返される場合はさらに良いでしょう） ）。
3. 返されるウェイポイントの組み合わせ（パス）の順序は、最短ルート（最小距離）から最長ルート（最大距離）の順にする必要があります

最後に、次の点を考慮してください。

1. これは私がAI/パスファインディングを賢く行う必要がある唯一のことです。それが私が本格的なパスファインディングまたはAIフレームワークを使用したくない理由です。1つの関数で上記を処理できるはずだと思います。
2. ウェイポイントの可能なすべての組み合わせを返すとオーバーヘッドが大きくなりすぎる場合は、組み合わせの最大数を指定できれば問題ありません（ただし、最も近いものから最も遠いものの順に並べます）。例えば。最も近い5つのパス。

どうすればこれを達成できますか？フィードバックをいただければ幸いです。

このように書きましたが、50%のケースでしか機能しません。誰かが何が悪いのか教えてもらえますか?

ありがとう：）

ここで最短経路アルゴリズムについて質問しました： 2Dウェイポイントパスファインディング：curLocationからtargetLocationに移動するWPの組み合わせ

（私の状況を理解するために、この質問と同様にその質問を読んでください。）

ダイクストラ最短経路アルゴリズムは、私が必要とすることを実行できるようです。ただし、ルートマップには約500〜1000のノードがあります。

これまでに見た実装では、ノードの数が50未満に制限されていました。私の質問は、ダイクストラ最短経路アルゴリズムを使用する必要があるのか​​、それとも代替手段を使用するのかということです。Javaに実装はありますか？

最短経路アルゴリズム（2Dウェイポイントパスファインディング：curLocationからtargetLocationに移動するWPの組み合わせ）に関する一般的なアドバイスを求めた後、より具体的な実装（500以上のウェイポイント/ノードの最短経路アルゴリズム（例：Dijkstra））について尋ねた後I JUNGライブラリ（http://jung.sf.net/）を使用することを決定しました。

私の目標は、各ポイントがx距離内にあるすべてのポイントに直接接続されているポイントのリスト（サイズ〜1000）からのポイントの任意の組み合わせを使用して、ポイントAからポイントBへの最短経路を取得することです。

このために、ツリーマップを設定する必要があります。これはツリーマップの実装のリストだと思います：http：//jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics。 jung.algorithms.shortestpath

あれは正しいですか？現在、これらの実装はすべてスパースツリーマップに制限されていますが、かなり密度の高いツリーマップを作成する必要があります。

では、目標を達成するためにJUNGでどのツリーマップを使用する必要がありますか？

このツリー構造をどのように変えることができますか

....基本的にすべてのリーフノードから1（ルート）へのパスを含むこの「逆ツリー」構造に：

結果はツリーとして構造化する必要はなく、正しい順序の4つのフラット配列でも問題ありません。

深さ優先探索が関連するアルゴリズムのように見えますが、擬似コード（incidentEdges（）は何を返すのですか？）を理解できないため、かなり行き詰まっています。

誰かが元のネストされた配列を結果の配列に変換するためのRubyメソッド（または本当に理解しやすい擬似コード）を提供できれば、私は無限に感謝します。

そして、これは宿題ではなく、勉強してから長すぎる結果です...課題追跡システムで特定の課題の依存関係ツリーを適切な順序で印刷するには、これが必要です。

ノードとエッジのデフォルト操作が組み込まれたQtのグラフデータ構造の実装はありますか？