0

我最近在CodeBullet的 Snake AI 视频中发现了 Hamiltonian Path/Circuit，并决定亲自尝试一下。我编写了一个基本的深度优先搜索算法来访问图中的所有节点并在电路完成时存储路径。

下面是算法的伪代码：

# 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 及以下网格的解决方案，但问题是，它非常慢。在视频中，它甚至无法为 8x8 网格提供解决方案，并提到这是一种非常快速的算法，因为他已经计算了 50x50 网格的哈密顿电路，所以它也显示出来了。

我真的很想知道如何加快速度，因为我确信我的初学者技能不足以指出一些你可能很容易看到的明显缺陷。任何帮助表示赞赏。

4

0 回答 0