Гамильтонов путь по преграде из сетки и Python
Я пытаюсь найти любые гамильтоновы пути в данной сетке, которая содержит препятствия в различных узлах. Моя проблема в том, что мой код работает уже несколько дней и еще не закончен. Хотя эта проблема находится в области 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 шагов в секунду код, кажется, никогда не прекращает исследовать правый нижний угол. Например, два 0 в узлах (3,1) и (3,2) никогда не были достигнуты.
Таким образом, это оставляет у меня некоторые вопросы: является ли это просто стандартным симптомом 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
1 ответ
Быстрый и очень грубый расчет, дающий оценку сложности задачи.
У вас есть всего 13*9 == 117 узлы, из них 5 стен, которые выходят 112 открытые узлы. Каждый открытый узел имеет от 2 в 4 соседи, скажем в среднем у них есть 3 соседи (это на самом деле недооценка). Это означает, что количество путей, которые вы должны проверить, составляет около 3^112 ≈ 2.7*10^53,
Конечно, иногда вы сокращаете свой поиск раньше, но оценка остается: количество путей огромно, поэтому нет смысла проверять их все с помощью обратного отслеживания методом перебора.