問題タブ [hamiltonian-cycle]

この問題は、ハミルトニアン サイクル Hcycle(V,E) 関数を 1 回使用して、グラフ G にハミルトン パスが含まれているかどうかをテストします。この関数は、G にハミルトン サイクルが含まれているかどうかにかかわらず、true または false の出力を返します。

多項式の時間計算量を持つプログラムを作成する必要があります。このプログラムは、この問題に出力を与える必要がある 1 つのハミルトニアン サイクル関数を使用して、無向グラフ G に少なくとも 1 つのハミルトニアン パスが含まれているかどうかを判断する必要があります。

また、逆の問題を持つプログラムを作成する必要があります。(Hpath 関数を使用して、グラフに Hemiltonian Cycle が含まれているかどうかを調べます)。

この問題の解決策が見つかりません。Hcycle と Hpath の両方を一度しか使用できません。

関数 Hcycle と Hpath は線形時間計算量で実行されると仮定します。

いくつかのハミルトニアン サイクル アルゴリズムを探していましたが、実装が見つからず、疑似コードが 1 つも見つかりませんでした。サイクルを出力する必要さえありません。グラフにサイクルがあるかどうかを確認するだけです。入力は、V 頂点と E エッジを持つグラフです。また、グラフにハミルトニアン パスがあるかどうかを確認するアルゴリズムが必要です。パスを出力する必要はありません。パスがあるかどうかを確認するだけです。どちらも多項式時間でなければなりません。

私は大きな加重グラフを持っています。最小コストですべてのノードを通過する近似最短ハミルトニアン パスを計算したいと考えています。グラフが大きすぎて記憶に収まりません。そのため、いくつかのエッジをランダムに無視し、残りをメモリにロードすることにしました。しかし、問題は、ほとんどの Java TSP 実装が完全なグラフを必要とすることであり、私の場合は巨大なメモリを必要とし、それほど多くのメモリがありません。imcpmlete グラフで TSP を計算する Java ライブラリはありますか? 私の戦略は、最初の頂点セットをより小さな部分に分割したことでした。それぞれのショレスト ハミルトニアン パスを計算し、すべての最短ハミルトニアン パスを接続しました。それは TSP の適切な近似値ですか? 大きなグラフのTSPのより良い近似アルゴリズムを知っている人はいますか?

グラフにハミルトニアン パスがあるかどうかを調べるには、多項式時間では計算できないと言われました。多項式時間で解けると仮定しましょう。これを証明するにはどうすればよいでしょうか? NP困難問題だから無理？

そこで、8*8 のチェス盤のナイツ ツアーを解決するために、この実装を思いつきました。しかし、実行に長い時間がかかっているようです (停止しなければならないほど長い)。しかし、dx、dy 配列をコメントに書かれているものに置き換えると、プログラムは魔法のように機能し、出力が得られます。ブルートフォースアルゴリズムが解決策を迅速に見つけることができるように、配列を巧みに選択していると彼らは言います。

しかし、そもそもこの配列 (dx,dy) は、他のコードから取得したものです。では、なぜこのコードがそれらの配列 (コメント内) で機能し、私のものではないのか、誰でも説明できます。

ノードの数として n を指定し、エッジのリストとしてエッジを指定

誰かが私のコードの何が問題なのか教えてもらえますか? 一部のインスタンスでは機能しますが、すべてのインスタンスでは機能しません

巡回セールスマンの問題で任意のサイクルを見つける指数関数よりも高速なアルゴリズムを探しています。サイクルがどれほど悪いかは関係ありません。サイクルである必要があります。私が本当に探しているのは、ハミルトニアン回路のアルゴリズムです。ある点から始まり、他のすべての点に到達し、次のようなグラフの開始点で終わる何か: http://neogen.amdurs.com/wikipics/projects/tsp.png

これまでのところ、私の例ではうまくいかないように見えるこのランダムアルゴリズムを見つけました: http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Hamiltonian_path_problem.html

そして、私が理解するのに苦労している「パーマーのアルゴリズム」： ハミルトンサイクルのパーマーのアルゴリズム

これを行うためのこれらの 2 つのアルゴリズム以上のものはありますか?

ハミルトン経路がグラフに存在するかどうかを見つける問題はNP完全であり、ダイクストラの最短経路アルゴリズムは多項式時間で実行されるため、最短ハミルトン経路を見つけるために変更できないことを読みました。（このロジックは有効ですか？）

しかし、無向グラフ (すべてのエッジが非負のコストを持つ) に 2 つのノード (A と Z など) が与えられ、与えられたノード (A と Z) を持つハミルトニアン パスが少なくとも 1 つあると仮定するとどうなるでしょうか。エンドポイントとして。これらの仕様が与えられた場合、Dijkstra のアルゴリズムを変更して、A と Z を終点とする最短のハミルトニアン パスを見つけることができるでしょうか? (多項式時間)

注: 特に 2 つのノードから最短のハミルトニアン パスを見つけることにのみ関心があります。たとえば、26 個のノード (A から Z までのラベルが付いている) を含むグラフがある場合、すべての点を通過するが、A で始まり Z で終わる最短のパスは何ですか? (異なるエンドポイント、A と Z のみ)

追加の質問: 答えが「いいえ」で、これを解決するために使用できる別のアルゴリズムがある場合、それはどのアルゴリズムで、その時間計算量はどれくらいですか?

(注: この質問にはタグとして「hamiltonian-cycle」が含まれています。タグ「hamiltonian-path」を作成するのに十分な担当者がいないため、Hamiltonian PATH を探しています。ただし、A と Z としましょう。がちょうど 1 つのエッジで接続されている場合、最短のハミルトニアン サイクルを見つけてから、A と Z を接続するエッジを削除することで、最短のハミルトニアン パスを見つけることができます)。