問題タブ [longest-path]

ここに投稿されたほとんどの質問は、最長のパスを除いてすべて解決しました。最長パスに関するウィキペディアの記事を読んだことがありますが、グラフが非循環的である場合は簡単な問題のようですが、私の場合はそうではありません。

どうすれば問題を解決できますか？可能性のあるすべてのパスをチェックして、力ずくで？どうすればそれを始められますか?

〜18000のグラフで多くの時間がかかることはわかっています。しかし、とにかくそれを開発したいのは、プロジェクトに必要なためです。テストして、実行時間がわずか 1 秒または 2 秒の小さなスケールのグラフでインストラクターに表示します。

少なくとも私は必要なすべてのタスクを実行し、それが機能するという概念実証を実行していますが、巡回グラフにはこれ以上の方法はありません。しかし、これらすべてのパスのチェックをどこから開始すればよいかわかりません...

ノードを再訪せずに、2 つのノード間の最長パスを見つける Lisp 関数をプログラムする必要があります。ただし、開始ノードと終了ノードが同じ場合は、このノードに再度アクセスできます。この関数は、再帰的かつ深さ優先検索の両方である必要があります。

私は何時間もこれに取り組もうとしてきましたが、解決策が思いつきません。関数の大まかな概要は知っていますが、正しくプログラミングできません。一部のコードとほとんどが擬似コード:

ネットは '((ab) (bc)) のように見えます。ここで、最初の項目はノードで、それ以外はすべてその隣接ノードです (たとえば、ノード a には隣接 b があり、ノード b には隣接 c があります)。

はい、これは宿題ですので、解決策やその一部を投稿することに自信がない場合は、投稿しないでください。私は Lisp を初めて使用するので、適切なスタートを切るためのヒント/ヘルプが必要です。

ありがとう

編集：まあ、私が得ることができたのはこれだけでした：

開始ノードと終了ノードが同じ場合を除いて、正しいソリューションが生成されます。同じなのに検索の仕方がわかりません。

DAG G では、重み付けされたエッジが負ではない場合、G の 2 つの頂点間の最大重み付けパスをどのように見つけますか?

君たちありがとう！

巡回グラフで最長パスを見つけようとするために、どのような最適化が存在しますか?

巡回グラフの最長経路は NP 完全であることが知られています。グラフ全体を DFS するよりも速く最長パスを見つけることができる最適化またはヒューリスティックは何ですか? 確率論的アプローチはありますか？

特定の性質を持つグラフがありますが、一般的なケースでこれに対する答えを探しています。論文へのリンクは素晴らしいでしょう。ここに部分的な答えがあります：

1. 周期的であることを確認します。非巡回グラフの最長経路は、動的計画法を使用して簡単に計算できます。

2. グラフが平面かどうかを調べます (どのアルゴリズムが最適か?)。そうである場合、それがブロック グラフ、プトレマイック グラフ、またはサボテン グラフであるかどうかを確認し、このペーパーに記載されている方法を適用します。

3. Donald B Johnson のアルゴリズム( Java 実装)を使用して、単純なサイクルがいくつあるかを調べます。単純なサイクルでエッジを削除することにより、循環グラフを非循環グラフに変更できます。その後、ウィキペディアのページにある動的プログラミング ソリューションを実行できます。完全を期すために、各サイクルでこれを N 回実行する必要があります。ここで、N はサイクルの長さです。したがって、グラフ全体の場合、DP ソリューションを実行する必要がある回数は、すべてのサイクルの長さの積に等しくなります。

4. グラフ全体を DFS する必要がある場合は、事前に各ノードの「到達可能性」を計算することで、いくつかのパスを削除できます。主に有向グラフに適用されるこの到達可能性は、各ノードが繰り返しなしで到達できるノードの数です。これは、そのノードからの最長パスの最大値です。この情報を使用して、現在のパスと子ノードの到達可能性を合わせたものが、既に見つけた最長パスよりも短い場合、より長いパスを見つけることは不可能であるため、その分岐を使用しても意味がありません。

グラフ内の最長パスを決定するコード セグメントを作成しました。以下はコードです。しかし、途中で再帰的な方法があるため、計算の複雑さを取得する方法がわかりません。最長パスを見つけることはNP完全問題なので、O(n!)またはのようなものだO(2^n)と思いますが、実際にどのように決定できますか?

次の問題が NP-HARD にあることを知っています: 単純なグラフ G=(V,E)、2 つの頂点 v、V の v'、整数 B、および非負の長さ関数 len: E-> Z+ が与えられた場合、長さが B 未満の v から v' への単純なパスはありますか?

私の質問は次のとおりです。以前と同じ条件が与えられた場合、頂点 v から v' までの G 内の必ずしも単純ではない最長のパスを見つけることに関心がある場合、問題はまだ NP-HARD にありますか?

注: ハミルトンパスをそれに還元しようとしましたが、NP に還元可能な問題があるかどうかを証明することはまだできません。ゲイリー＆ジョンソンも調べましたが、見つかりませんでした。

この問題が NP-HARD であるかどうかを証明するためのヒントを教えてください。前もって感謝します！

有向加重グラフで最長の巡回パスを見つけるアルゴリズムがあるかどうかを知りたいです (これは、最大のハミルトニアン サブグラフを見つける問題だと思います)。

1 つの頂点から開始し、同じ頂点に戻る必要があります。最も可能性の高いノードが横断されます。

ありがとう

これが機能することを確認したいだけです。ダイクストラのアルゴリズムを使用して最大のパスを見つけることができますか？最初に距離を-1のようなものに初期化してから、relaxサブルーチンを変更して、それよりも大きいかどうかを確認する必要がありますか？

これは、負の重みがない問題の場合です。

これが実際の問題です。

電話網の図が与えられたとします。これは、頂点がスイッチの中心を表し、エッジが2つの中心間の通信回線を表すグラフGです。エッジは、最も低い帯域幅のエッジの帯域幅によってマークされます。ダイアグラムと2つのスイッチセンターaとbが与えられた場合、aとbの間のパスの最大帯域幅を出力するアルゴリズムを与えます。

これは機能しますか？

編集：

私はこれを見つけました：

ヒント：基本的なサブルーチンは、ダイクストラのサブルーチンRelaxと非常によく似ています。エッジ（u、v）があると仮定します。min {d [u]、w（u、v）}> d [v]の場合、d[v]をmin{d [u]、w（u、v）}に更新する必要があります（aからuからvへの帯域幅はmin{d[u]、w（u、v）}であり、これは現在の帯域幅よりも大きくなります）。

初期化時にはすべての距離が無限大であるため、それが何を意味するのか正確にはわかりません。だから、これがどのように機能するのかわかりません。手がかりはありますか？

ダイクストラのアルゴリズムを使用して、有向非循環パスで最長パスを見つけることができるかどうかを調べようとしています。負のコスト サイクルがあるため、一般的なグラフでダイクストラの最長パスを見つけることができないことはわかっています。しかし、それはDAGで動作するはずです。Google を通じて、多くの矛盾する情報源を見つけました。すぐに機能すると言う人もいれば、機能しないと言う人もいますが、証明や反例は見つかりませんでした。誰かが私に証明または反例を指摘できますか?

過去 2 日間から、グラフの最長パスを計算するためのロジックを見つけようとしています。DAG で簡単に見つけることができ、一般に多項式時間アルゴリズムであることがわかっています。正式には、最長パスを計算するためのヒューリスティックを実装したいと思います。さらに、グラフにエッジが存在する確率 p が与えられている場合、どのように問題を解決できますか..ヘルプ...