9

だから私は次の問題があります：

x x y 次元のグリッドが与えられた場合、1 つの隅 (たとえば左上) から始まり、別の隅 (右下) で終わり、すべての頂点を通過するルートの数を計算します。

したがって、私の現在の方法は、すべての可能なパスを試し、フィニッシュに到達してすべてのノードをトラバースするパスをカウントすることで、力ずくで実行するだけです。動作している間、それは O(n^2) であり、非常に急速に信じられないほど遅くなります。パスがすべての頂点を通過する必要があるため、組み合わせで行う方法がわかりません。

より複雑なアルゴリズムを調べたところ、オイラー経路を計算するための Hierholzer のアルゴリズムは多少関連しているように見えますが、このためにノードを複数回トラバースできないため、完全ではありません。

そのままでは、私のプログラムは動作しますが、うまく動作しません。より効率的にしたいと考えています。私が使用できるより良いアルゴリズムはありますか?

編集これまでの回答に感謝します。明確にするために、2D グリッド内のすべてのノードは n/e/s/w で接続されています

また、グリッドは正方形である必要はありません

4

3 に答える 3

2

NP完全であるハミルトン閉路問題であるため、できることはあまりありません。

ただし、実際には他の何かを検索して、解決しようとしている問題にいくつかの制限を追加することができます...

編集：

@JanDvorakが指摘したように、特定の制限は、正方形のグリッドを使用していることです。これまでの私の調査結果：

偶数の場合x、左上隅から右下で終わるすべての頂点を通過する方法はありません。証拠：

軸に沿った方向付けられた動きを数えましょう。たとえば、上は、下-1は1、左は-1、右-1です。したがって、x x xグリッドを使用すると、全体の動きはになります2*x。各頂点（最後の頂点を除く！）では、1つの方向のみを選択しています。したがって、通過する必要のある頂点の数が偶数の場合、全体の動きは偶数になり、逆の場合は奇数になります。偶数の場合x、頂点の数は奇数ですが、全体の動きは偶数です=>方法を見つけることができません。

于 2013-01-09T23:33:01.170 に答える
0

まず、x が偶数の場合、答えが常にゼロであることを示す単純なパリティ引数があります。グリッドをチェッカーすると、左上と右下の四角形が同じ色であり、 n 2が偶数で 1 が奇数であるため、最初と n 2番目の両方でその色にアクセスできないことに注意してください。

x が奇数の場合、パスをカウントする方法がわかりませんが、合計数が少なくとも指数関数的に急速に増加することに注意してください。n*n グリッドのトラバースは、(n+2) の 2 つの異なるトラバーサルに持ち上げることができます。 *(n+2) グリッド。一番上の行に沿って右に、2 番目の行に沿って左に、最初の列に沿って下に、2 番目の列に沿って上に移動し、残りの正方形で n*n グリッド トラバーサルを実行して 1 つを取得します。最初の 2 つの行と列を逆の順序でカバーすることによって、もう一方を取得します。

これは、ブルート フォース ソリューションがうまく機能する可能性が低いことを示しているはずです。

于 2013-01-10T00:10:01.710 に答える
0

私は今学期、このような問題に取り組みました。私たちのようなメタヒューリスティックアルゴリズムを見ることができると思います：

ただし、本当に改善が必要でない限り、ブルートフォースにとどまることをお勧めします。それらは非常に複雑だからです。

于 2013-01-09T23:51:16.367 に答える