java - 特定の重みを持つ特定のノードを持つ循環パスを見つける

Question

ナビゲーションアプリを構築しようとしています。特定のノードを含み、合計が特定の重みになる循環パスを見つけるアルゴリズムを考えようとしています。アルゴリズムの入力は、ノードと重みになります。

例: algo(a,30) - アルゴリズムは、ノード A から開始してノード A で終了できるパスを返し、その合計は 30 です。

追加情報: すべての w:weights w>0 について、グラフは方向性があります (道路と同様)。

ありがとうギャル

Answer 1

一般的な問題は NP 困難であり、最長経路問題から還元可能であり、したがってNP 困難であり、この問題に対する既知の多項式解はありません (一般的な仮定では、そのような解は存在しません)。

G最長経路の問題は次のとおりです。重み関数wと頂点のペアを持つグラフが与えられた場合u、 - からまでvの最長経路を見つけます。uv

証明:
問題に多項式アルゴリズムがあると仮定すると、二分探索を使用して最長経路問題のアルゴリズムを構築できます (解がなくなるまで、必要な重みを指数関数的に増やしてから、二分探索)。各ステップは多項式であり、ステップがありO(log|PATH|)ます。は入力で多項式であるためlog|PATH|(単純なパスを想定)、アルゴリズムは多項式です。

ハミルトニアン経路問題や巡回セールスマン問題とも密接な関係があります。

Answer 2

この問題は、ハミルトニアン サイクル問題よりも強力 (より困難) です 。この問題の解が既にある場合algo(a,b)、任意のハミルトニアン サイクル問題Pについて、 Pのエッジの重み = 1 とそうでないエッジの重み = 0 で新しいグラフを設計できるalgo(1,n)ため、ハミルトン サイクルを見つけるために使用できnます。グラフ内のノード。ここに NP 完全問題があります。

が小さいアプリケーションの場合n、特定の「プルーニング」を使用したブルートフォース検索は十分に高速に機能するはずです。