問題タブ [hamiltonian-cycle]

私は最近、ハミルトニアン パスの総数を考え出そうとしていました (基本的には、開始頂点から開始し、各ノードを 1 回正確に訪れ、終了頂点に到達します)。ブルート フォース dfs は、7x8 の適度なサイズのグリッドで長い散歩をします。私はこれらの剪定戦略のいくつかを思いつきました。これらの刈り込み手法の目的は、ハミルトニアン パスにならない部分パスをそれ以上延長しないようにすることです。

DFS アルゴリズム: 開始頂点から開始し、その隣接ノードにアクセスして再帰します。訪問したノードの数をカウントし、終了頂点に到達したら、訪問したノードの合計がグリッド内のノードの合計と同じかどうかを確認します。これは、各頂点について 4 方向に進むことができるため、指数関数的に複雑になります。これは O(4^n) になります。そのため、できるだけ早くパスを拒否し、最後の頂点に到達するまで待機しないようにする必要があります。

剪定テクニック:

1) 特定の部分パスについて、残りのグラフが接続されているかどうかを確認します。そうでない場合、この部分パスは最終的にハミルトニアン パスになることはありません。

2) 特定の部分パスについて、まだ訪問されていない各ノードは、1 つの隣接ノードを使用してこのノードに入り、他の隣接ノードを使用して終了できるように、少なくとも 2 度必要です。

これらの剪定技術がどれだけ時間を節約できるか疑問に思っていました. また、速度が大幅に向上しないため、非常に重要な剪定テクニックが欠けています。

前もって感謝します ！！！

最小スパニング ツリー (重み付きグラフの場合) を見つけ、グラフにハミルトニアン パスがあるかどうか (ハミルトニアン サイクルの存在に依存する) を見つけるためのアルゴリズムを調べていました。私はすべてを台無しにしました。では、ハミルトニアン パスとスパニング ツリーの違いは何でしょうか? どちらもグラフのすべての頂点をカバーしています。スパニング ツリー (おそらく最小スパニング ツリー) を見つけるための効率的なアルゴリズムを使用できますが、ハミルトニアン サーキットを見つけるためのアルゴリズムを使用できないのはなぜですか?? サイクルに到達するまで、一度に 1 つのエッジを追加および削除し続けることができます。おそらく、ハミルトニアン サイクルを見つけることができますか??

ランダムグラフがあるとします。結果のグラフのすべてのエッジがハミルトン パスになるように、最小ステップ数でエッジを削除または追加するにはどうすればよいでしょうか?

誰かが何かアイデアを共有できれば、本当に感謝しています。

双方向の N*M グリッドで可能な限りランダムなハミルトニアン パスを見つけることができる効率的なアルゴリズムを探しています。

どこで見つけられるか、またはそのようなアルゴリズムを構築する方法を知っている人はいますか?

私はすでに効率的なアプローチを見つけました（下の画像を参照）。ここでの最終結果はハミルトニアン サイクルです。ランダム エッジを削除すると、ハミルトニアン パスになります。このアルゴリズムは効率的ですが、ランダム性が十分ではありません。このアプローチでは、パスの始点と終点が常に隣り合っていますが、それらをランダムな場所に配置したいと考えています。 空間充填曲線 http://img593.imageshack.us/img593/8060/sfc.png http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type= から取得した画像pdf

ハミルトン閉路問題は次のように要約できると思います。

無向グラフを考えると、ハミルトン閉路は、一度だけのすべての頂点を通過G = (V, E)するツアーです。GG

さて、私がやりたいのは、私の問題をこれに減らすことです。私の問題は：

の重み付き無向グラフG、整数k、および頂点u, v の両方が与えられた場合、 合計の重みが少なくともであるからへGの単純なパスはありますか？Guvk

したがって、ハミルトン閉路問題がNP完全であることを知っているので、この問題をハミルトニアンに還元することにより、この問題もNP完全であることが証明されます。私の問題は、それをハミルトニアンに還元する関数です。

1. 大きな問題は、ハミルトン閉路問題がエッジの重みを処理しないことです。そのため、グラフを重みのないグラフに変換する必要があります。
2. その上、この問題には開始と終了（uとv）が指定されていますが、ハミルトニアンはサイクルを検出するため、開始は終了と同じです。

（1）については、総重量がk未満の単純なパスをすべて取り出したグラフを通過する線に沿って考えています。（2）の場合、これは実際には問題ではないと思います。ハミルトン閉路がある場合、uからvへの単純なパスを切り取ることができるからです。

だから、私の本当の質問は次のとおりです。

1. 私の解決策は私に正しい答えを与えるつもりですか？
2. はいの場合、実際のソリューションでこれらのエッジの1つが必要になる可能性に影響を与えることなく、総重量がk未満の単純なパスを生成するエッジをどのように取り除くことができますか？エッジeがEのサブセットに対して重み<kの単純なパスを生成するために取り出された場合でも、エッジの異なる組み合わせを使用して重み>=kのパスを生成する単純なパスで使用できます。

ありがとう！

いくつかの単語が与えられた場合、たとえば、バナナ、猫、犬、象、タイプ、中間、湖

となる数列を見つける

(1) すべての単語がシーケンス上にある

(2) 隣接する単語に同じ文字を含めることはできません。

seq が見つからない場合は、false を返します。それ以外の場合は、true と seq を返します。

重複なし。単語の順列はありません。

私の考え:

グラフを設定し、ハミルトニアン パスを使用して seq を見つけます。

でも、NPコンプリートです。

ハミルトニアンパスを回避するには?

より良いアイデアはありますか？

ありがとう

有向グラフで最適なハミルトニアン パスを見つけるアルゴリズムを実装しています。かなりうまく機能しているように見えるアルゴリズムを実装しましたが、場合によっては微妙なバグやその他の問題があるかどうかは完全にはわかりません. したがって、ソリューションが既知のいくつかの多様なネットワークが必要であり、私の実装でも問題が解決されているかどうかを確認します。

ウィキペディアでは、ハミルトニアン パスは無向グラフの適切な用語にすぎないことを示唆しているため、「ハミルトニアン パス」とは、指定されたネットワーク上のすべてのノードを 1 回および 1 回だけ訪問するパスを意味すると仮定します。

簡単にするために、すべての接続 (または「エッジ」) が正の整数値 (または「長さ」) を持つと仮定できます。また、ノードはそれ自体に接続されておらず、任意の 2 つのノード間の各方向にエッジが 1 つしか存在しないと仮定することもできます。

たまたま全長が最も長いパスに興味があるので、「最適」とは最長を意味しますが、(従来の TSP のように) 最短の全長が必要な場合はおそらくほとんど違いはありません。また、たまたま貪欲なアルゴリズムを使用しています。

TSP が解決された有向ネットワークをどこで、またはどのように取得できますか? 実際の解決策と貪欲な (または他のヒューリスティックな) 解決策が利用可能であれば、さらに良いでしょう。ネットワークは、有益なテストを行うのに十分な大きさである必要がありますが、解決策を手動で確認するには十分に小さくする必要があります (解決策が最初に不明な場合)。それらは、「簡単な」ネットワークと「問題のある」ネットワークの両方をカバーするのに十分なほどトポロジ的に多様でなければなりません。

同じものを探している他の人のために。私が持っている最高のものは、次のネットワークです。

これは隣接リストで、行はエッジの起点、列は終点です。数字は各エッジの長さで、0 は「エッジなし」を示します。たとえば、4 は、DからA までのエッジの長さが 4 であり、 AからDまでの接続がない(長さ 0) ことを示します。

このネットワークのパスの最大長は、E->D->A->C->B です。その全長は 2+3+3+3=11 です。この場合、貪欲なアルゴリズムが最良の解を見つけることができると私は信じています。

私はランダムな無向ソーシャルグラフを持っています。

できればハミルトン路を見つけたいです。または、不可能な場合（または多項式時間で可能かどうかを知ることができない場合）、一連のパス。この「一連のパス」（N個のノードすべてが1回だけ使用される）では、パスの数を最小限に抑え、パスの平均の長さを最大限に増やしたいと思います。（したがって、単一ノードのNパスの自明な解決策はありません）。

すでにノードとエッジの隣接行列を生成しました。

助言がありますか？正しい方向へのポインタ？問題のNP完全（？）の性質のため、これにはヒューリスティックが必要になることを認識しており、「十分に良い」答えで大丈夫です。また、Javaでこれを実行したいと思います。

ありがとう！

私は昨日からこの問題で立ち往生しています。残念ながら/幸いなことに、この問題は私の非常に巨大な（私にとっては、C ++の初心者）アルゴリズムの約0.5％にすぎないため、適応して機能させることができる既存のコードのライブラリが必要です。

無向グラフのすべての円を検出して表示したいと思います。私のエッジは重み付けされていません。はい、私が本当に必要としているのは、すべてのサイクル、つまり、有向グラフのすべてのハミルトニアン サイクルのようなものです。

私はブースト グラフ ライブラリをいじっていましたが、DFS アルゴリズムは非常に有望に思えましたが、頂点を 1 回しか訪れないため、すべてのハミルトニアン サークルを与えることはできません。

現時点では、アルゴリズムの設計を続行できるように、コードが機能するだけで済みます。その後、パフォーマンスの問題を検討する可能性があります。5 ネストされた for ループを使用したソリューションも大歓迎です。

これは私がブーストから取得して遊んだコードですが、back_edgesの前任者を記録してアクセスする方法がわかりません。それが解決されたとしても、ブーストDFSは頂点を1回しか訪れません。

上記の例では、通常は 3 サイクルしかないことを示していますが、4 つ以上のサイクルが予想されるため、1 つの頂点が複数のサイクルで表示される可能性があります。back_edge()そして第二に、ブーストがこのように私に与える3つのサイクルすべてにアクセスすることさえできませんstd::vector<uInt32> fCycle1, fCycle2,fCycle3. 私が得るのback_edge()は、ソースとターゲットの頂点だけです。

どんな助けやヒントにも感謝します。これまでのところ、ここにあるすべての例はサイクルまたはその数の存在を検出するだけで、存在するすべてのサイクルを一覧表示する方法を示したものはありません。

このアルゴリズムは、ハミルトニアン パス問題を解決します。G無向グラフ、v開始頂点、 G.size()グラフのサイズG.get(v).gV、現在の頂点のすべての隣接頂点。

このアルゴリズムの複雑さは O(n!) であると言えますか?