哈密尔顿电路的一种有效算法

Question

我最近在CodeBullet的Snake A.I.视频中发现了哈密顿路径/电路，并决定自己试一试。我编写了一个基本的深度优先搜索算法来访问图中的所有节点，并在电路完成时存储路径。

以下是算法的伪代码：

# 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网格的哈密顿电路。

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

Answer 1

正如上面的评论中所提到的，我发现了一种在网格中查找哈密尔顿路径的硬编码方法。唯一需要注意的是，它不适用于奇数x奇数网格

这是代码：

def HamiltionPath(rows, cols):
# No solution case 
if rows%2 != 0 and cols%2 != 0:
print("No solution exists")
return []

# Initialize path
path = []

# If rows are even
if rows%2 == 0:
# Starting point
j = 0
# Start traversal
for i in range(rows):
if j <= 1:
while j < cols - 1:
#print(i, j)
path.append(i * cols + j)
j += 1
elif j == cols - 1:
while j != 1:
#print(i, j)
path.append(i * cols + j)
j -= 1
#print(i, j)
path.append(i * cols + j)
# Final row
j = 0
for i in range(rows):
#print(rows - i - 1, j)
path.append((rows - i - 1) * cols + j)
# If cols are even
else:
# Starting point
i = 0
# Start traversal
for j in range(cols):
if i <= 1:
while i < rows - 1:
#print(i, j)
path.append(i * cols + j)
i += 1
elif i == rows - 1:
while i != 1:
#print(i, j)
path.append(i * cols + j)
i -= 1
#print(i, j)
path.append(i * cols + j)
# Final row
i = 0
for j in range(cols):
#print(i, cols - j - 1)
path.append(i * cols + (cols - j - 1))

return path
path = HamiltionPath(6, 6)
print("Path:")
for i in path: print(i, end = ' ')
Path: 0 1 2 3 4 5 11 10 9 8 7 13 14 15 16 17 23 22 21 20 19 25 26 27 28 29 35 34 
33 32 31 30 24 18 12 6 0