6

ハミルトニアン パス問題のわずかに修正されたバージョンを解こうとしています。開始点と終了点が与えられ、解が存在するかどうかを判断する代わりに、解の数(0 の場合もある) を見つけたいという点で変更されています。

グラフは 2D 配列として与えられ、ノードは配列の要素です。また、移動できるのは水平または垂直のみで、斜めには移動できません。言うまでもなく、1 つの都市から 2 つの都市に移動することはできません。そのためには、1 つの都市を 2 回訪問する必要があります。

各ノードで 4 つ (エッジ上のノードの場合は 3 つまたは 2 つ) の可能な移動をすべて試行し、ソリューションの数をカウントするブルート フォース ソリューションを作成しました (これは、ゴールに到達し、他のすべてのノードも見たときです)。適度なサイズの入力（たとえば、7x7配列など）で途方もない時間実行されました。

目標がわかっているので双方向検索を使用することも考えましたが、フリンジを満たしたいだけでなく、すべてのノードが訪問されたことを確認したいので、これはあまり役に立ちませんでした。さらに、すべてのノードが 2 つのフリンジ間で使い果たされると、結合できないような形で終了する可能性があります。

力ずくの解決策しか残されていないように感じます。問題自体は NP 完全であることはわかっていますが、ブルート フォースに対する改善点があるかどうか疑問に思っています。誰かが何か他のことを提案できますか?

- 編集 -

双方向検索を使用しても実際には役に立たないと言いましたが、そう考えた理由を明らかにしたいと思います。左上と右下のノードがそれぞれ開始点と目標点である 2x3 グラフを考えてみましょう。双方向検索のフリンジをスタートから右に移動させ、ゴールから左に移動させます。2 回の移動の後、すべてのノードが訪問されますが、1 つのノードから一方向にしか移動できないため、フリンジに参加する方法はありません。ただし、David が以下の回答で指摘したように、いくつかの変更を加えてアルゴリズムを機能させることは可能かもしれません。

4

6 に答える 6

3

Wolfram Alphaによると、

... 与えられた一般グラフがハミルトニアン パスを持つかどうかを判断する唯一の既知の方法は、徹底的な検索を行うことです。

単一のハミルトニアン パスを見つけることから始めて、それを 2 つのパスに分割し、2 つのパスをできるだけ明確に分離する分割ポイントを作成することから始めたいと思うと思います。次に、サブグラフで順列を見つけることができます（もちろん、再帰も！）

正確なアルゴリズムはわかりませんが、そのような分割統治法から始めます。

于 2011-03-16T23:51:51.177 に答える
1

https://mathoverflow.net/questions/36368/effective-way-to-count-hamiltonian-paths-in-a-grid-graph-for-a-givenの Math Overflow で、誰かがあなたとよく似た質問をしました。 -pair-of-vertおよび (1) 「効率的に行う方法は次のとおりです」という大量の応答が得られなかった (これはおそらく、簡単な方法がないことを意味します)、(2) Mathematica ではカウントに 5 時間かかるようです7x7 グリッドの反対側のコーナー間のパスなので、特に間違ったことをしていない可能性があります。(3) 回答の中には興味深いヒントがいくつかあります。

于 2011-03-16T23:56:25.180 に答える
1

双方向検索を引き続き使用できます。検索に制約を追加して、以前に表示されたノードが検索の候補にならないようにするだけです。

並列化可能なソリューションに役立つ別のアプローチは、検索をより小さな検索に分割することです。

たとえば、次のようにして、元の問題を解決してみてください。

開始ノードでも終了ノードでもない各ノード n について、開始から n (set1) および n から終了 (set2) までのすべてのパスを検索します。

set1とを見つけたらset2、 node 以外の共通ノードを持つそれらの外積のすべての要素を破棄できますn。

于 2011-03-16T23:51:01.610 に答える
0

7x7アレイ（つまり、合計7 * 7 = 49ノード）では、O（n！）アルゴリズムまたはO（2 ^ n * n ^ 2）アルゴリズムのいずれかを使用すると、どちらも時間がかかりすぎます。

おそらく、この特定のグラフの特別な特性を考慮に入れてこれを高速化する方法があります（たとえば、各ノードには最大4つのエッジがあります）が、高速な解決策はありそうにありません（誰かがハミルトン閉路問題自体の多項式時間アルゴリズムを偶然見つけない限り） ）。

于 2011-03-17T05:57:41.257 に答える