私は最近、ハミルトニアン パスの総数を考え出そうとしていました (基本的には、開始頂点から開始し、各ノードを 1 回正確に訪れ、終了頂点に到達します)。ブルート フォース dfs は、7x8 の適度なサイズのグリッドで長い散歩をします。私はこれらの剪定戦略のいくつかを思いつきました。これらの刈り込み手法の目的は、ハミルトニアン パスにならない部分パスをそれ以上延長しないようにすることです。
DFS アルゴリズム: 開始頂点から開始し、その隣接ノードにアクセスして再帰します。訪問したノードの数をカウントし、終了頂点に到達したら、訪問したノードの合計がグリッド内のノードの合計と同じかどうかを確認します。これは、各頂点について 4 方向に進むことができるため、指数関数的に複雑になります。これは O(4^n) になります。そのため、できるだけ早くパスを拒否し、最後の頂点に到達するまで待機しないようにする必要があります。
剪定テクニック:
1) 特定の部分パスについて、残りのグラフが接続されているかどうかを確認します。そうでない場合、この部分パスは最終的にハミルトニアン パスになることはありません。
2) 特定の部分パスについて、まだ訪問されていない各ノードは、1 つの隣接ノードを使用してこのノードに入り、他の隣接ノードを使用して終了できるように、少なくとも 2 度必要です。
これらの剪定技術がどれだけ時間を節約できるか疑問に思っていました. また、速度が大幅に向上しないため、非常に重要な剪定テクニックが欠けています。
前もって感謝します ！！！