問題タブ [hamiltonian-path]

私は現在、グラフ内のハミルトニアン パスの存在を確認する必要があるプロジェクトに取り組んでいますが、パスがどこで開始または終了するかは問題ではなく、グラフ内に存在することだけです。

ここで別のユーザーからこのコードをコピーしました：

明らかに、開始値のパラメーターがあります。今、私の最初の本能は、関数を反復してすべての開始頂点に対して実行することですが、100以上の頂点を持つグラフでこれを実行するので、完了するまでに時間がかかります. すべての頂点を通るパスが何であるかを実際に知る必要はありません。それが役立つ場合は、そのパスが存在することを知る必要があるだけです。

任意の開始位置を与えるためにこれをどのように適応させますか?

私は最近、 CodeBulletの Snake AI ビデオでハミルトニアン パス/回路を発見し、自分で試してみることにしました。グラフ内のすべてのノードを訪問し、回路が完成したときにパスを保存する基本的な深さ優先検索アルゴリズムを作成しました。

アルゴリズムの擬似コードは次のとおりです。

この実装は、6x6 グリッド以下のソリューションを提供するため、理論的には機能しますが、問題は非常に遅いことです。ビデオでは、50x50 グリッドのハミルトニアン回路を計算したため、非常に高速なアルゴリズムであることが示されていましたが、8x8 グリッドのソリューションを提供することさえできませんでした。

どうすればこれをスピードアップできるか知りたいです。なぜなら、私の初心者のスキルでは、おそらく非常に簡単に見られる明らかな欠陥を指摘するには不十分であると確信しているからです。どんな助けでも大歓迎です。