1

開始頂点と終了頂点、およびその間の頂点の数が不明な非巡回有向グラフがあります。パスは開始頂点から開始し、終了頂点で終了します。開始頂点と終了頂点の間の任意のパスに沿った頂点の数は 100 未満であることがわかっていますが、可能な頂点の数は非常に多くなる可能性があります。各頂点にはコストが割り当てられており、パスのコストはその間の頂点のコストの合計です。ランダム ウォークまたはその他の手段 (これは、すべての頂点を探索することを避けるため) を使用して、コストが最も高い (または最も高い) パスを見つける方法はありますか?

4

1 に答える 1

2

この問題は、Geekviewpoint.com で詳細な説明とともに解決されています。ダイクストラのアルゴリズムを強化します。http://www.geekviewpoint.com/java/graph/dijkstra_constrained

編集: 各パス間の 100 個の頂点を考慮します。

もともとあなたの問題は、開始頂点と終了頂点の間に100のパスがあると言っていました。しかし、あなたの修正により、実際にはパス上に 100 個の頂点があります。その場合、最適化は DFS を使用して簡単に行うことができます。

パスを組み立てようとするときに、見た頂点の数を追跡します。数が 99 に達し、最初から最後までリンクしない場合は、そのパスを中止し、別のユニットを試してみてください。存在する場合は答えが得られます。変更する必要があるアルゴリズムは、サイクル検出用の DFS です。どのアルゴリズムの教科書にも、そのうちの 1 つがあります。見つかったパスの中から最適なパスを選択する必要があるため、http://www.geekviewpoint.com/java/graph/count_pathsも確認する必要があります。

明らかな方法を説明する必要があるかどうかはわかりませんが、配列内の最大要素を見つける方法と同様に、見つけた過去のパスを追跡します。コードは難しくありません。いくつかの小さなアイデアを組み合わせる必要があります。

  • DFS (サイクル検出に似ており、パスのカウントに似ており、2 つが重複しています)

  • これまでに見た最適なパスを追跡します: アイデアがマップである 1 つのエントリ マップで、より短いパスを見つけた場合に置き換え続けます。

于 2013-01-26T19:02:52.183 に答える