我试图在给定的网格中找到任何哈密顿路径，其中包含各个节点的障碍。我的问题是我的代码已经运行了好几天，还没有结束。虽然这个问题出现在 NP-Complete 区域，但从我所看到的情况来看，我不确定是否缺少足够的时间是我的问题。
我的方法是，在 python 中，使用递归来执行深度优先搜索，通过网格可以进行的所有可能的左、右、上和下移动顺序。我研究了哈密顿路径问题的其他方法，但是对于我所做的来说它们更复杂，我认为小网格不需要它们
以下是我正在搜索的网格。0 是开放节点，1 是障碍物，S 是起点。
[0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,1,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,1,0,0,1,0,1,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,S]
[0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,1,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0]
这是正在运行的函数当前网格的示例输出，其中 1 现在也代表访问过的节点。
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0]
[1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1]
然而，即使每秒大约 50000 步，代码似乎也从未停止检查右下角。例如，从未到达节点 (3,1) 和 (3,2) 处的两个 0。
所以这给我留下了一些问题：这是否只是 NP-Hard 的标准症状，即使我只尝试 13x9 网格？我是否达到了 python 递归限制，导致我的代码无休止地重新运行相同的 DFS 分支？还是我还缺少其他东西？
这是我的搜索方法的简化版本：
#examines options of steps at current marker cell and iterates path attempts
def tryStep():
global path #list of grid movements
global marker #current cell in examination
set marker to traveled
if whole grid is Traveled:
print path data
end program
#map is incomplete, advance a step
else:
if can move Up:
repeat tryStep()
if can move left:
repeat tryStep()
if can move down:
repeat tryStep()
if can move right:
repeat tryStep()
#Failure condition reached, must backup a step
set marker cell to untraveled
if length of path is 0:
print 'no path exists'
end program
last = path.pop()
if last == "up":
move marker cell down
if last == "left":
move marker cell right
if last == "down":
move marker cell up
if last == "right":
move marker cell left
return
因此，代码应该遍历网格中所有可能的路径，直到形成哈密顿路径。这里是我正在运行的实际代码供参考：
'''
Created on Aug 30, 2014
@author: Owner
'''
#Search given grid for hamiltonian path
import datetime
#takes grid cord and returns value
def getVal(x,y):
global mapWidth
global mapHeight
global mapOccupancy
if (((x < mapWidth) and (x >-1)) and (y < mapHeight and y >-1)):
return mapOccupancy[y][x]
else:
#print "cell not in map"
return 1
return
#sets given coord cell value to visted
def travVal(x,y):
global mapWidth
global mapHeight
global mapOccupancy
if (((x < mapWidth) and (x >-1)) and ((y < mapHeight) and (y >-1)))== True:
mapOccupancy[y][x] = 1
else:
#print "cell not in map"
return 1
return
#sets given coord cell value to open
def clearVal(x,y):
if (((x < mapWidth) and (x > -1)) and ((y < mapHeight) and (y > -1)))==True:
mapOccupancy[y][x] = 0
else:
#print "cell not in map"
return 1
return
#checks if entire map has been traveled
def mapTraveled():
isFull = False
endLoop= False
complete = True
for row in mapOccupancy:
if endLoop ==True:
isFull = False
complete = False
break
for cell in row:
if cell == 0:
complete = False
endLoop = True
break
if complete == True:
isFull = True
return isFull
#examines options of steps at current marker cell and iterates path attempts
def tryStep():
global path
global marker
global goalCell
global timeEnd
global timeStart
global printCount
travVal(marker[0],marker[1])
printCount += 1
#only print current map Occupancy every 100000 steps
if printCount >= 100000:
printCount = 0
print ''
print marker
for row in mapOccupancy:
print row
if mapTraveled():
print 'map complete'
print "path found"
print marker
print path
for row in mapOccupancy:
print row
print timeStart
timeEnd= datetime.datetime.now()
print timeEnd
while True:
a=5
#if map is incomplete, advance a step
else:
#Upwards
if getVal(marker[0],marker[1]-1) == 0:
marker = [marker[0],marker[1]-1]
#print "step: " + str(marker[0])+' '+ str(marker[1])
path.append('up')
tryStep()
#left wards
if getVal(marker[0]-1,marker[1]) == 0:
marker = [marker[0]-1,marker[1]]
#print "step: " + str(marker[0])+' '+ str(marker[1])
path.append('left')
tryStep()
# down wards
if getVal(marker[0],marker[1]+1) == 0:
marker = [marker[0],marker[1]+1]
#print "step: " + str(marker[0])+' '+ str(marker[1])
path.append('down')
tryStep()
#right wards
if getVal(marker[0]+1,marker[1]) == 0:
marker = [marker[0]+1,marker[1]]
# print "step: " + str(marker[0])+' '+ str(marker[1])
path.append('right')
tryStep()
#Failure condition reached, must backup steps
clearVal(m[0],m[1])
last = path.pop()
#print 'backing a step from:'
#print last
if last == "up":
marker = [marker[0],marker[1]+1]
if last == "left":
marker = [marker[0]+1,marker[1]]
if last == "down":
marker = [marker[0],marker[1]-1]
if last == "right":
marker = [marker[0]-1,marker[1]]
return
if __name__ == '__main__':
global timeStart
timeStart = datetime.datetime.now()
print timeStart
global timeEnd
timeEnd= datetime.datetime.now()
global printCount
printCount = 0
global mapHeight
mapHeight = 9
global mapWidth
mapWidth =13
#occupancy grid setup
r0= [0,0,0,0,0,0,0,0,0,0,0,0,0]
r1= [0,0,0,0,0,0,1,0,0,0,0,0,0]
r2= [0,0,0,0,0,0,0,0,0,0,0,0,0]
r3= [0,0,0,1,0,0, 1 ,0,1,0,0,0,0]
r4= [0,0,0,0,0,0,0,0,0,0,0,0, 0]
r5= [0,0,0,0,0,0,0,0,0,0,0,0,0]
r6= [0,0,0,0,0,0,1,0,0,0,0,0,0]
r7= [0,0,0,0,0,0,0,0,0,0,0,0,0]
r8= [0,0,0,0,0,0,0,0,0,0,0,0,0]
global mapOccupancy
mapOccupancy = [r0,r1,r2,r3,r4,r5,r6,r7,r8]
#record of current trail attempt
global path
path = []
#marker for iterating through grid
global marker
start = [12,4]
#start =[0,2]
m = start
global goalCell
goalCell = [6,3]
print marker
tryStep()
#no path avalible if this point is reached
print'destination is unreachable'
print 'last path: '
for row in mapOccupancy:
print row
print path
print m
print mapOccupancy
print timeStart
timeEnd= datetime.datetime.now()
print timeEnd