問題タブ [hamiltonian-cycle]

無向グラフでハミルトン閉路を見つけるための動的計画法アルゴリズムとは何ですか？O(n.2^n)時間計算量のあるアルゴリズムが存在することをどこかで見ました。

ハミルトニアンサイクルの出力を生成する隣接行列をJavaで実装しようとしています。これは、クラスラル、ジクストラ、2optアプローチなどのさまざまなアルゴリズムで解決できます。2 次元配列が必要であることはわかっていますが、どこから始めればよいかわかりません。マトリックスを保存して、現在持っているグラフに適用できるようにする必要があります。これは、現在「n」個のノードを持つ円です（マトリックスに依存）。すべての助けを歓迎します、ありがとう

比較的小さい (40 ～ 80 ノード) 立方 (3-正則) 平面グラフがあり、それらのハミルトニシティを決定する必要があります。このタスクが NP 完全であることは認識していますが、関心のあるグラフ サイズに対して非常に高速な漸近指数時間アルゴリズムを期待しています。

これは巡回セールスマン問題に関係しています。最初にすべての順列を生成し、次に宛先 (起点と同じ) をアタッチする必要があります。すなわち: 1) abcd abdc ....

2) abcda abdca ....a

私はすべての距離を持っており、それらを合計するアルゴリズムだけが必要です。これに使用できるアルゴリズム（Cが望ましい）があるか、または既製のソリューションがどこかにあるのだろうか。

こんにちは、私は TSP 問題を解決する必要があるプロジェクトに取り組んでいます。ここで必要なのは、グラフでハミルトニアン回路を見つける方法です。実際、私は現実の世界でこれを行う方法を知っています。しかし、実装とソースコードでは、これを行う方法がわかりません。ネストされたループを使用するインターネット上の記事を読んだことがありますが、それぞれが何をしているのか、ストーリー全体がどのように進んでいるのかはわかりませんでした。誰かがこれについて私を助けることができれば幸いです。そして、これを実装する方法の簡単な例を教えてください。ワーキングモデルは必要ありません。頂点の配列とパスの配列があると仮定してください (パスとは、パスの始点と終点の頂点を意味します)。この問題をどのように解決できるか。

この質問は実際にその1つを言い換えます。コードジャムの問題は次のとおりです。

N個のノードとK個の「禁止された」エッジを持つ完全な無向グラフが提供されます。N <= 300、K <= 15.K個の「禁止された」エッジを使用しないハミルトン閉路の数をグラフで見つけます。

の単純なDPアプローチは、このようなNO(2^N*N^2)では機能しません。勝者の解決策はであるように見えます。誰かがこの問題を解決する方法を知っていますか？O(2^K)

ハミルトン サイクルを実装する Java ソース コードを考え出さなければならないこのプロジェクトがあります。私はグーグルで検索しましたが、少なくともハミルトニアンサイクルとは何か、開始頂点を除くすべての頂点を一度だけ通過するパスは最後の頂点でもあるため、わかりました（間違っている場合は教えてください）。問題は、それを実装する方法がわからないことです。基本的に、私の質問は次のとおりです。

1. ハミルトニアン サイクルをどこでどのように実装しますか?
2. ハミルトニアン サイクルのアプリケーションは何ですか (なぜそれが重要なのかを理解するのに役立ちます)

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

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

ありがとう

これは以前に尋ねられたことは知っていますが、どの投稿にも答えが見つかりませんでした。グラフ内のすべてのハミルトニアン パスを列挙するアルゴリズムを提案してもらえますか?

ちょっとした背景: 私は、各ハミルトニアン パスを列挙し、何らかの分析を行い、結果を返さなければならない問題に取り組んでいます。そのためには、考えられるすべてのハミルトニアン パスを列挙できる必要があります。

ありがとう。

コードジャムの問題は次のとおりです。

N 個のノードと K 個の「禁止された」エッジを持つ完全な無向グラフが与えられます。N <= 300、K <= 15. K 個の「禁止された」エッジのいずれも使用しない、グラフ内のハミルトニアン サイクルの数を見つけます。

残念ながら、ここのスタックおよび Web 全体での説明は非常に不十分です。特定の 'n' : (n-1) の HamCycles を計算できます! / 2 .

そして、動的計画法で短いセットを実行できます。

しかし、ボローニャのサブセットをすべて取得することはできません。どうすれば O^K にできますか? 私は Python を使用していますが、利用可能な C++ をまだ解読していません。最終的には、時間をかけて C++ を学び、それを解読するつもりです。しかし、それまでの間、ウェブ上のどこかで誰かがこれをよりよく説明できないのはなぜですか? いつも中途半端な説明です。