algorithm - ハミルトン閉路の効率的なアルゴリズム

Question

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

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

# Global list to store the Hamilton Circuit
hamiltonPath = []

# Recursive DFS Function
def dfs(node, start, currentPath = [], depth = 1):
    # Return if the circuit is already discovered
    if hamiltonPath != []: return

    # Add current node to current path
    curPath.append(node)

    # Explore neighbors of the current node
    for neighbor in node.neighbors:
        # Check if the neighbor completes the circuit
        if neighbor == start and depth == totalNodes:
            curPath.append(neighbor)
            hamiltonPath = curPath.copy()
            return

        # Otherwise if neighbor is unvisited continue DFS search
        if neighbor not in curPath:
            dfs(neighbor, start, curPath.copy(), depth + 1)

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

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