#python #recursion #depth-first-search #maze
#питон #рекурсия #поиск по глубине в первую очередь #Лабиринт
Вопрос:
Я пытаюсь найти (используя Python) все возможные решения лабиринта. У меня есть скрипт DFS, который возвращает одно решение. Я пытаюсь адаптировать его, но мне действительно трудно разобраться во всей этой истории с рекурсией.
Вот код, который у меня есть, который работает для поиска одного возможного решения с использованием DFS: любые советы или помощь будут очень признательны! («Lett» в массиве можно игнорировать / считать обычным «путем»)
def DFS(x,y,Map):
if (Map[x][y]=="exit"): #check if we're at the exit
return [(x,y)] #if so then we solved it so return this spot
if ((Map[x][y]!="path") and (Map[x][y]!="lett")): #if it's not a path, we can't try this spot
return []
Map[x][y]="explored" #make this spot explored so we don't try again
for i in [[x-1,y],[x 1,y],[x,y-1],[x,y 1]]: #new spots to try
result = DFS(i[0],i[1],Map) #recursively call itself
if len(result)>0: #if the result had at least one element, it found a correct path, otherwise it failed
result.append((x,y)) #if it found a correct path then return the path plus this spot
return result
return [] #return the empty list since we couldn't find any paths from here
def GetMap():
return [
["wall","wall","wall","wall","wall","wall","wall","wall"],
["wall","path","path","path","path","path","path","wall"],
["wall","wall","wall","path","wall","lett","path","wall"],
["wall","path","path","path","wall","wall","path","wall"],
["wall","path","wall","lett","path","path","path","wall"],
["wall","path","wall","wall","wall","wall","path","wall"],
["wall","path","lett","path","path","path","exit","wall"],
["wall","wall","wall","wall","wall","wall","wall","wall"]
]
def DrawMap(Map,path):
for x in range(0,len(Map)):
for y in range(0,len(Map[x])):
if ((x,y) in path):
assert Map[x][y] in ("path","lett","exit")
print("-",end="")
elif (Map[x][y]=="wall"):
print("#",end="")
elif (Map[x][y]=="exit"):
print("e",end="")
elif (Map[x][y]=="lett"):
print("L",end="")
else:
print(' ',end="")
print()
print("nUnsolved:n")
DrawMap(GetMap(),[])
print("n")
print("Solved with DFS:")
print("path is ",len(DFS(1,1,GetMap()))," spots longn")
DrawMap(GetMap(),DFS(1,1,GetMap()))
print("n")
Комментарии:
1. Я вижу, что скрипт работает, поэтому я не уверен, в чем заключается ваш вопрос.
2. Я хотел бы получить список со всеми возможными решениями
3. Перепишите DFS так, чтобы он возвращал список всех путей, начинающихся с (x, y), которые ведут к выходу. Затем ваш рекурсивный вызов становится «двойным вложенным циклом for, в котором вы перебираете следующие точки и решения, которые они возвращают». Предупреждение. Перед возвратом вам нужно будет отменить Map[x,y]=»explored» и вернуть его к предыдущему значению перед возвратом.
Ответ №1:
принятие желаемого за действительное
Возникновение подобной проблемы может показаться ошеломляющим, но мой любимый прием в программировании заставляет сложность раствориться в воздухе. Принимая желаемое за действительное, мы пишем нашу программу так, как хотели бы, чтобы она могла быть, а затем воплощаем наши желания в жизнь —
# simple.py
from maze import maze
from cursor import cursor
def dfs(cursor, maze):
q = maze.get(cursor.y(), cursor.x())
if not q or q.is_wall() or q.is_step():
return
elif q.is_exit():
yield maze
else:
next_maze = maze.step(cursor.y(), cursor.x())
yield from dfs(cursor.up(), next_maze)
yield from dfs(cursor.down(), next_maze)
yield from dfs(cursor.right(), next_maze)
yield from dfs(cursor.left(), next_maze)
def solve(cursor, maze):
for x in dfs(cursor, maze):
return x
Все, что нам нужно для начала, — это лабиринт, m , и курсор, c —
# simple.py (continued)
# read maze from file
m = maze.from_file("./input")
# initialize cursor
c = cursor.from_ints(1, 1)
Мы можем найти первое решение, используя solve —
# simple.py (continued)
print(solve(c, m))
########
#--- #
###-#L #
# -## #
# #----#
# ####-#
# L e#
########
Или мы можем найти все решения, используя dfs —
# simple.py (continued)
for x in dfs(c, m):
print(x, end="nn")
(output below reformatted to save space)
######## ######## ######## ######## ######## ########
#--- # #--- # #----- # #----- # #------# #------#
###-#L # ###-#L # ### #--# ### #--# ### #L-# ### #L-#
# -## # #---## # # ##-# #---##-# # ##-# #---##-#
# #----# #-#L # # #L -# #-#----# # #L -# #-#----#
# ####-# #-#### # # ####-# #-#### # # ####-# #-#### #
# L e# #-----e# # L e# #-----e# # L e# #-----e#
######## ######## ######## ######## ######## ########
cursor
To make the program above work, we need to fulfill all of our wishes. We’ll start with the cursor module. A cursor is simply a pair of integers that gives us a convenient up , down , left , and right movements —
# cursor.py
def from_ints(y, x):
return (y, x)
def up(t):
(y, x) = t
return from_ints(y - 1, x)
def down(t):
(y, x) = t
return from_ints(y 1, x)
def left(t):
(y, x) = t
return from_ints(y, x - 1)
def right(t):
(y, x) = t
return from_ints(y, x 1)
def to_str(t):
(y, x) = t
return f"({y}, {x})"
Как вы можете видеть, мы работаем с обычными функциями. Python также обладает хорошими объектно-ориентированными функциями, и мы хотим предоставить такие удобства пользователям нашего модуля. Мы легко добавляем интерфейс ООП, оборачивая простые функции —
# cursor.py (continued)
class cursor:
def from_ints(y, x): return cursor(from_ints(y, x))
def __init__(self, t): self.t = t
def __iter__(self): yield from self.t
def __str__(self): return to_str(self.t)
def up(self): return cursor(up(self.t))
def down(self): return cursor(down(self.t))
def right(self): return cursor(right(self.t))
def left(self): return cursor(left(self.t))
Лабиринт
Теперь мы переходим к нашему maze модулю. Мы начнем с написания обычных функций для преобразования from_file в лабиринт и из лабиринта to_str —
# maze.py
from cell import cell
def from_file(filename):
with open(filename) as f:
return from_str(f.read())
def from_str(s):
return [ list(map(cell.from_str, row)) for row in s.split("n") ]
def to_str(t):
return "n".join("".join(map(str, row)) for row in t)
В качестве бонуса обратите внимание, что мы получили from_str бесплатно. Затем мы записываем функции в get ячейку или set ячейку, используя y x координаты и . Здесь мы также пишем step простую оболочку вокруг set , которая используется для обозначения того, что ячейка в лабиринте была исследована —
# maze.py (continued)
from arr_ext import update
def get(t, y, x):
try:
if x < 0 or y < 0:
return None
else:
return t[y][x]
except IndexError:
return None
def set(t, y, x, v):
return update
( t
, y
, lambda row: update(row, x, lambda _: v)
)
def step(t, y, x):
return set(t, y, x, cell.step())
Не бойтесь загадывать столько желаний, сколько захотите. Мы реализуем update , когда нам это нужно. И так же, как мы делали в предыдущем модуле, мы добавляем объектно-ориентированный интерфейс —
# maze.py (continued)
class maze:
def from_file(filename): return maze(from_file(filename))
def from_str(s): return maze(from_str(s))
def __init__(self, t): self.t = t
def __iter__(self): yield from self.t
def __str__(self): return to_str(self.t)
def get(self, y, x): return get(self.t, y, x)
def set(self, y, x, v): return maze(set(self.t, y, x, v))
def step(self, y, x): return maze(step(self.t, y, x))
ячейка
Когда мы писали модуль лабиринта, мы хотели cell модуль. Техника принятия желаемого за действительное должна быть в центре внимания сейчас: загадай желание, исполни его. Наш модуль Cell представляет ячейку в нашем лабиринте. Мы начинаем со способа преобразования from_str в ячейку и из ячейки to_str —
# cell.py
wall = 0
path = 1
exit = 2
lett = 3
step = 4
str_to_cell =
{ "#": wall, " ": path, "e": exit, "L": lett, "-": step }
cell_to_str =
{ v: k for (k, v) in str_to_cell.items() }
def from_str(s):
if s in str_to_cell:
return str_to_cell[s]
else:
raise RuntimeError(f"invalid cell character: {s}")
def to_str(t):
if t in cell_to_str:
return cell_to_str[t]
else:
raise RuntimeError(f"invalid cell component: {t}")
Дополнительно мы пишем is_* предикаты, чтобы определить, является ли ячейка a wall , a и т.д. path Это подчеркивает силу абстракции: мы можем изменить способ представления наших данных в одном модуле без необходимости изменять другие модули в нашей программе —
# cell.py (continued)
def is_wall(t): return t == wall
def is_path(t): return t == path
def is_exit(t): return t == exit
def is_lett(t): return t == lett
def is_step(t): return t == step
Добавьте объектно-ориентированный интерфейс. Опять же, это простая оболочка вокруг наших простых функций —
# cell.py (continued)
class cell:
def from_str(s): return cell(from_str(s))
def wall(): return cell(wall)
def path(): return cell(path)
def exit(): return cell(exit)
def lett(): return cell(lett)
def step(): return cell(step)
def __init__(self, t): self.t = t
def __str__(self): return to_str(self.t)
def is_wall(self): return is_wall(self.t)
def is_path(self): return is_path(self.t)
def is_exit(self): return is_exit(self.t)
def is_lett(self): return is_lett(self.t)
def is_step(self): return is_step(self.t)
arr_ext
Осталось выполнить только одно желание! Мы пишем универсальную update функцию в модуле расширения массива, arr_ext —
# arr_ext.py
def update(t, pos, f):
try:
return [ *t[:pos], f(t[pos]), *t[pos 1:]]
except IndexError:
return t
advanced
Our simple program solves the problem in a simplified way. What if we want to solve the maze and know the path for each solution? Let’s write an advanced program below —
# advanced.py
from maze import maze
from cursor import cursor
def dfs(cursor, maze, path=[]):
q = maze.get(*cursor)
if not q or q.is_wall() or q.is_step():
return
elif q.is_exit():
yield (maze, path)
else:
next_maze = maze.step(*cursor)
next_path = [*path, cursor]
yield from dfs(cursor.up(), next_maze, next_path)
yield from dfs(cursor.down(), next_maze, next_path)
yield from dfs(cursor.right(), next_maze, next_path)
yield from dfs(cursor.left(), next_maze, next_path)
def solve(cursor, maze):
for x in dfs(cursor, maze):
return x
Notice how the advanced solution is just a small adjustment of the simple module. Let’s see what the first solved maze looks like —
# advanced.py (continued)
print(solution(solve(c, m)))
########
#--- #
###-#L #
# -## #
# #----#
# ####-#
# L e#
########
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(4, 3)->(4, 4)->(4, 5)->(4, 6)->(5, 6)
Теперь давайте посмотрим все решенные лабиринты и пути —
# advanced.py (continued)
for x in dfs(c, m):
print(solution(x), end="nn")
########
#--- #
###-#L #
# -## #
# #----#
# ####-#
# L e#
########
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(4, 3)->(4, 4)->(4, 5)->(4, 6)->(5, 6)
########
#--- #
###-#L #
#---## #
#-#L #
#-#### #
#-----e#
########
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(3, 2)->(3, 1)->(4, 1)->(5, 1)->(6, 1)->(6, 2)->(6, 3)->(6, 4)->(6, 5)
########
#----- #
### #--#
# ##-#
# #L -#
# ####-#
# L e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(2, 5)->(2, 6)->(3, 6)->(4, 6)->(5, 6)
########
#----- #
### #--#
#---##-#
#-#----#
#-#### #
#-----e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(2, 5)->(2, 6)->(3, 6)->(4, 6)->(4, 5)->(4, 4)->(4, 3)->(3, 3)->(3, 2)->(3, 1)->(4, 1)->(5, 1)->(6, 1)->(6, 2)->(6, 3)->(6, 4)->(6, 5)
########
#------#
### #L-#
# ##-#
# #L -#
# ####-#
# L e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(1, 6)->(2, 6)->(3, 6)->(4, 6)->(5, 6)
########
#------#
### #L-#
#---##-#
#-#----#
#-#### #
#-----e#
########
(1, 1)->(1, 2)->(1, 3)->(1, 4)->(1, 5)->(1, 6)->(2, 6)->(3, 6)->(4, 6)->(4, 5)->(4, 4)->(4, 3)->(3, 3)->(3, 2)->(3, 1)->(4, 1)->(5, 1)->(6, 1)->(6, 2)->(6, 3)->(6, 4)->(6, 5)
Не забудьте выполнить свои пожелания! Мы видим, что происходит появление нового модуля, solution , но на этот раз мы просто оставим его в том же файле —
# advanced.py (continued)
def to_str(t):
(maze, path) = t
return str(maze) "n" "->".join(map(str, path))
class solution:
def __init__(self, t): self.t = t
def __str__(self): return to_str(self.t)
Комментарии:
1. чувак, ты классный, это сообщество потрясающее!
Ответ №2:
Вот так:
Обновлен DFS:
def DFS(x,y,Map):
if (Map[x][y]=="exit"):
return [[(x,y)]]
if ((Map[x][y]!="path") and (Map[x][y]!="lett")):
return []
stat = Map[x][y]
Map[x][y]="explored"
my_results = []
for i in [[x-1,y],[x 1,y],[x,y-1],[x,y 1]]:
results = DFS(i[0],i[1],Map)
for res in results:
if len(res)>0:
res.append((x,y))
my_results.append(res)
Map[x][y] = stat
return my_results
Обновленный вывод:
print("nUnsolved:n")
DrawMap(GetMap(),[])
print("n")
print("Solved with DFS:")
results = DFS(1,1,GetMap())
for result in results:
print("path is ",len(result)," spots longn")
DrawMap(GetMap(),result)
print("n")