問題タブ [hamiltonian-cycle]

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

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

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

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