受阻网格的哈密尔顿路径与Python递归限制
我正在尝试在一个有障碍物的网格中找到任何汉密尔顿路径。我的问题是，我的代码已经运行了好几天，仍然没有结束。虽然这个问题属于NP完全问题，但从我看到的情况来看，我不确定是不是因为时间不够导致的。
我的方法是用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困难问题的一个标准症状吗？尽管我只是在尝试一个13x9的网格？ 我是否达到了Python的递归限制，导致我的代码不断重复运行相同的深度优先搜索分支？ 还是说我遗漏了什么其他的东西？
这是我搜索方法的简化版本：
#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
1 个回答
0
这里做了一个快速且粗略的计算，目的是估算一下这个问题的复杂程度。
你总共有 13*9 == 117 个节点，其中有5个是墙壁，所以剩下 112 个是可以通行的节点。每个可以通行的节点周围有 2 到 4 个邻居，假设平均每个节点有 3 个邻居（其实这个估算是偏低的）。这就意味着你需要检查的路径数量大约是 3^112 ≈ 2.7*10^53。
当然，有时候你会提前结束搜索，但这个估算依然成立：路径的数量是 巨大的，所以用暴力搜索的方法去检查所有路径是没有意义的。