問題タブ [hamiltonian-cycle]

最初にいくつかの定義:

定義 1

グラフ G = (V, E) は、隣接していない頂点 u と v の各ペアについて、d(u) + d(v)>=n (n = |V|) である場合、「密」と呼ばれます。d(*) は頂点の次数を表します *

定義 2

G 上の「ハミルトニアン サイクル」は、すべての l!=h に対して vil != vih であり、{ vil, vil} が G の辺であるような一連の頂点 ( vi1, vi2,....vin, vi1 ) です。 .

問題は次のとおりです: 密な無向グラフ G = (V; E) が入力として与えられたとき、G が G 上のハミルトニアン サイクルを許容するかどうかを判断し、存在する場合はそのサイクルを出力するか、「N」を出力するプログラムを作成します。ない場合。

私の解決策は、ソースから始まるすべての可能なパスを見つけ、このソースに戻るパスが存在するかどうかを確認することです。残念ながら、このソリューションは効率的ではありません。

助言がありますか？ありがとうございました。

「密な」グラフでは、パーマーのアルゴリズムを使用してハミルトニアン サイクルを構築しようとしています。ただし、このアルゴリズムを実装するとうまくいかないため、このアルゴリズムについて詳しく説明する必要があります。ウィキペディアの説明には不明な部分があるようです。

誰かがそれをより明確に説明したり、読むためのリンクを教えてくれたりするとありがたいです.

アルゴリズムステートメントは次のとおりです。

Palmer (1997) は、Ore の条件を満たすグラフでハミルトニアン サイクルを構築するための次の単純なアルゴリズムについて説明しています。グラフ内の隣接関係を無視して、頂点を任意にサイクルに配置します。サイクルに 2 つの連続する頂点が含まれてviおりvi + 1、それらがグラフ内で隣接していない場合は、次の 2 つの手順を実行します。

• j4 つの頂点vi、vi + 1、vj、およびvj + 1がすべて異なり、グラフに from と from のエッジが含まれるようなviインデックスvj + 1を検索しますvj。vi + 1

• vi + 1とvj(両端を含む)の間のサイクルの一部を逆にします。

より具体的には、「頂点を任意にサイクルに配置する」という部分がわかりません。この場合、この権利は 0,1,2,3,4,0 です。

そして、「サイクルの一部を逆にする」とはどういう意味ですか?

n² パス ノードを持つグラフがあり、開始ノードが常に右上隅 (点 A) にあり、終了ノードが常に右下隅 (点 B) にある場合、C# プログラムを作成する必要があります。与えられた n (n <=10 と仮定) で、A から B へのハミルトニアン パスの数を決定します。言い換えると、A で始まり B で終わるすべてのパスを見つける必要があります。ここで、各ノードは 1 回だけアクセスされ、ノード間の移動は左、右、上、下 (対角線なし) に制限されます。

たとえば、n = 5 の場合、考えられるパスの 1 つは、次の図に示すパスになります。

理想的には、いくつかのヒューリスティックを利用するインテリジェントなアルゴリズムを開発したいと考えていますが、今のところ、最初は力ずくの方法を開発する必要があります。幅優先検索を使用すると仮定していますが、C# を使用してそれを実装するためにどこから始めればよいか本当にわかりません。

v^2 時間で可能な限り長いハミルトニアン サイクルを見つけるアルゴリズムはありますか。まばらなグラフ (最大で 4v エッジ) でサイクルを見つける必要があるプログラムを実行しています。計算によると、v^2 以上が必要です。v^2 で操作するには、ヒューリスティックである必要があり、おそらくあまり正確ではないことを理解しています。可能かどうかわからないので、不可能か教えてください。

私はC ++プログラムをやろうとしています.私はポイントの数がある問題をやろうとしています. 次に、すべてのポイントを通過するパスを見つける必要があります。これは実際には TSP ではありません。TSP に関する私の知識によれば、すべてのポイントから他のすべてのポイントに移動できるからです。しかし、私の場合、ポイント間のパスネットワークは固定されており、すべてのポイントが他のすべてのポイントに接続されていない可能性があるという条件で、すべてのポイントを通過する適切なパスを見つける必要があります。

完全な無向グラフのすべてのハミルトニアン サイクルを生成したいと考えています (ループとリバースが重複としてカウントされ、除外されるセットの順列)。

たとえば、{1,2,3} の順列は

標準順列:

プログラム/アルゴリズムに出力してもらいたいもの:

321 はちょうど 123 後ろにあるので、312 はちょうど 123 1 回転した場所などです。

特定の集合に含まれるこれらのサイクルの数と、グラフにハミルトン サイクルがあるかどうかを検出するアルゴリズムについては多くの議論が見られますが、それらを完全な無向グラフ (つまり、数値の集合セット内の他の番号が先行または後続する可能性があります)。

このタスクを達成するためのアルゴリズムまたは C++ コードが本当に必要です。または、このトピックに関する資料がある場所を教えていただければ幸いです。ありがとう！

再帰を使用して、可能なすべてのハミルトニアン サイクルをリストに追加する方法を実装しようとしています。これまでのところ、私の停止条件は十分ではなく、リストに頂点を追加する行に「OutOfMemoryError: Java heap space」が表示されます。

誰かが私が間違っていること、または私のアプローチが完全に間違っていることを教えてもらえますか?

編集:コメントで示唆されているように、犯人は親配列であり、無限ループを引き起こしました。修正できず、子要素を格納するように配列を変更しました。今、すべてがうまくいくようです：

スキエナのアルゴリズムに関する本を参照しています。

Gグラフに aHamiltonian pathが含まれているかどうかをテストする問題はですNP-hard。ここで、ハミルトニアン パスPは、各頂点を 1 回だけ訪れるパスです。ハミルトニアン サイクル問題とは異なり、 G の終了頂点から P の開始頂点までのエッジが存在する必要はありません。

有向非巡回グラフ G ( DAG) が与えられ、O(n + m)それがハミルトン路を含むかどうかをテストする時間アルゴリズムを与えてください。

私のアプローチ、

DFSとを使用する予定ですTopological sorting。しかし、問題を解決するために 2 つの概念をどのように結び付ければよいかわかりませんでした。ソリューションを決定するためにトポロジカル ソートをどのように使用できますか。

助言がありますか？

ハミルトンサイクルを解くのが「難しい」と考えられる穴のあるグリッドグラフのデータベースまたは引用はありますか?