問題タブ [hamiltonian-cycle]

さまざまなノードに障害物を含む特定のグリッドでハミルトニアン パスを見つけようとしています。私の問題は、コードが何日も実行されていて、まだ終了していないことです。この問題は NP-Complete 領域にありますが、私が見ている限り、十分な時間がないことが私の問題であるかどうかはわかりません。

私のアプローチは、Python で、再帰を使用して、グリッドを介して行うことができる左、右、上、下の動きのすべての可能な順序で深さ優先検索を実行することでした。ハミルトニアン経路問題に対する他の方法を研究しましたが、それらは私が行ったことに対してより複雑であり、小さなグリッドではそれらが必要になるとは思いませんでした。

以下は私が探しているグリッドです。0 はオープン ノード、1 は障害物、S は開始点です。

以下は、実行中の関数の現在のグリッドの出力例です。1 は訪問したノードも表しています。

ただし、毎秒約 50000 ステップであっても、コードは右下隅の調査を停止しているようには見えません。たとえば、ノード (3,1) と (3,2) の 2 つの 0 には到達していません。

だから、これは私にいくつかの質問を残します.13x9 グリッドしか試していませんが、これは NP-Hard の標準的な症状ですか? Python の再帰制限に達したため、コードが同じ DFS ブランチを際限なく再実行していませんか? それとも、私が見逃しているものがありますか？

これは私の検索方法の簡略版です。

したがって、コードは、ハミルトニアン パスが形成されるまで、グリッド内のすべての可能なパスを反復処理する必要があります。参考までに、私が実行している実際のコードを次に示します。

以下は、バックトラッキングを使用してグラフにハミルトニアン パスが存在するかどうかを確認するコードです。そして、以下のコードによると、時間の複雑さはO(V^2)であり、Vは頂点の総数です。しかし、ハミルトニアン問題は NP 完全です。n^k私の理解によれば、これは多項式時間では解決できない問題であり、nは入力でkあり、定数です。以下のコードをテストしましたが、正常に動作しています。では、時間の複雑さを間違って計算しましたか?

ノード クラス:

次のようなポイントの X 座標と Y 座標を持つデータフレームがあります。

これらすべてのポイントを結ぶ最短経路を見つけ、その合計距離も返したいだけです。他の条件はありません。すべてのポイントを他のポイントに接続でき、開始または終了する特定のポイントがない、重みがないなど... igraph パ​​ッケージに関する多くのトピックを見つけましたが、データをフィードする方法がわかりませんそれに。これも見つかりましたが、R言語では見つかりませんでした。20ポイントしかないので、「ブルートフォース」スクリプトで問題ないかもしれません..ありがとう

DAG では、ハミルトニアン パスを見つけるために、まずトポロジー ソートを見つけ、次にトポロジカル ソートからハミルトニアン パスを見つけます。

この声明をどのように正当化しますか？

私の質問が繰り返されている場合は申し訳ありませんが、すべての頂点の次数が 2 である連結グラフがハミルトニアン グラフであることを証明する完全な答えを見つけることができませんでした。

私はこれとこれを読みました

ポイントのグラフを最短/最も効率的な方法で接続するパスを作成し、すべてのポイントが接続され、各ポイントが最大2つの接続を持つようにするアルゴリズムを作成しようとしています。

いくつかの調査を行った後、これは (無向の) ハミルトニアン パスのようです。私の現在のアルゴリズムは、ネットワーク内で可能なすべての接続のリストを作成し、最短の接続を順番に選択して、ポイントに 2 回以上接続しないことを確認するだけです。ただし、グラフ全体を接続することを妨げる閉じたループをチェックすることはできません。

私のアプローチは完全に間違っていますか、それとも閉じたループをチェックしてそれらを作成する接続を無視する簡単な方法はありますか?

関連するタプルのリストからツリー パスを作成する方法を見つけるのに苦労していますか? 各ノードが 1 回アクセスされるすべてのパス、別名ハミルトニアン パスのリストのみが必要です。

私は近づき続けていますが、いくつかの道がありません。

たとえば、次の接続リストがあるとします。

望ましい出力:

そのため、考えられる各パスが保存され、各ノードは 1 回だけアクセスされます。

ここに私が持っているものがありますが、多くのパスがありません:

中間試験で出題されました。誰でも答えを明確にできますか？

問題 A: 完全加重グラフ G が与えられたとき、最小加重のハミルトニアン ツアーを見つけます。

問題 B: 完全加重グラフ G と実数 R が与えられた場合、G は最大で R の重みを持つハミルトニアン ツアーを持ちますか?

B を解くマシンがあるとします。そのマシンで問題 A を解くために、(G と実数 R が与えられるたびに) B を何回呼び出すことができますか? M までの G のエッジの合計を想定します。

1) 数えられない状態があるので、これはできません。

2) O(|E|) 回

3) O(lg m) 回

4) A は NP 困難であるため、これは実行できません。