python - Why is my program running an infinite loop? Python
问题描述
I am trying to create a maze solver in python using the Breadth-first search. The algorith is supposed to replace the shortest path from S to E (start to end) with 1's. However, my program is running an infinite loop and the only while loop I have is at the end, so I think the problem is there. I can't figure out what is causing it.
import queue
def maze_3():
maze3 = [
'00000S000000000000000000000000000000000000000000000000000000000',
'00000 000000000 ',
'00000 000000000 000000000000000000 000000000000000 00000000',
'000000 00000000 000000 00000',
' 00000000 000000000000 000000000000000000 000000',
'00000000 000000000000000000000000000000 0000 000000',
'000000 000 000000000 000 000000 0000',
'000000 000 000000000 00000000 000000 00',
'00 000 0 0000000000 000 000 0000 00 00 00000 000',
'000000 000000 000000000 000 0000 00000',
'0000000000000000 0000000 0000000 000 00000000000',
'000000 000 0000000 0000 00000000000000 00000000',
'0000000000000000E 0000000',
]
return maze3
def finished_maze(maze, solution=''):
global starting_point
for i, position in enumerate(maze[0]):
if position == 'S':
starting_point = i
j = starting_point
k = 0
position = set()
for move in solution:
if move == 'Up':
k -= 1
elif move == 'Down':
k += 1
elif move == 'Left':
j -= 1
elif move == 'Right':
j += 1
for k, row in enumerate(maze):
for j, column in enumerate(row):
if (k, j) in position:
print('1', end='')
else:
print(column, end='')
print()
def is_valid(maze, moves):
a = True
for l, position in enumerate(maze[0]):
if position == 'S':
starting_point = l
j = starting_point
k = 0
for move in moves:
if move == 'Up':
k -= 1
elif move == 'Down':
k += 1
elif move == 'Left':
j -= 1
elif move == 'Right':
j += 1
if not ((j >= 0 and j < len(maze[0])) and (k >= 0 and k < len(maze[0]))):
return not a
elif maze[k][j] == '0':
return not a
return a
def find_solution(maze, moves):
a = True
for i, position in enumerate(maze[0]):
if position == 'S':
starting_point = i
j = starting_point
k = 0
for move in moves:
if move == 'Up':
k -= 1
elif move == 'Down':
k += 1
elif move == 'Left':
j -= 1
elif move == 'Right':
j += 1
if maze[k][j] == 'E':
print(finished_maze(maze, moves))
return a
return not a
space = queue.Queue()
space.put('')
put = ''
maze = maze_3()
while not find_solution(maze, put):
put = space.get()
for i in ['Up', 'Down', 'Left', 'Right']:
location = put + i
if is_valid(maze, location):
space.put(location)
解决方案
This line of code doesn't do what you are expecting it to do:
for move in moves:
It splits it so it gives you every single letter separately.
D
o
w
n
D
o
w
n
It should be like this: (add import re
to the start of your file)
for move in re.findall('[A-Z][^A-Z]*', moves):
It gives the following:
Right
Down
Down
Up
Up
Down
Down
Up
Down
Down
Down
Up
Left
Down
Down
Up
Right
Other than that, your program works, but really slowly because you are not checking if you already visited a node.
Extra part on visited list
If you define maze like so:
def maze_3():
maze3 = [
'00000S000000000000000000000000000000000000000000000000000000000',
'00000 000000000 ',
'00000 000000000 000000000000000000 000000000000000 00000000',
'000000E 00000000 000000 00000', # here we add an E
' 00000000 000000000000 000000000000000000 000000',
'00000000 000000000000000000000000000000 0000 000000',
'000000 000 000000000 000 000000 0000',
'000000 000 000000000 00000000 000000 00',
'00 000 0 0000000000 000 000 0000 00 00 00000 000',
'000000 000000 000000000 000 0000 00000',
'0000000000000000 0000000 0000000 000 00000000000',
'000000 000 0000000 0000 00000000000000 00000000',
'0000000000000000E 0000000',
]
return maze3
It gives the following solution, which is correct:
Down
Down
Right
Down
But if we print all the paths it checked, we can see this:
Up
Down
Left
Right
DownUp
...
The last line says it returns to the location it already visited. If you take a better look at BFS, you will see that it keeps a list of visited nodes. If you add it, it will speed up your code as you will not be checking nodes that you have already visited.
推荐阅读
- symfony - Symfony 403 以正确的角色抛出
- ember.js - 如何将错误消息从 Ember js 中的不同控制器传递到路由
- php - 将 FileRun 迁移到其他子域后主机名错误
- android - 为什么存储库发送到 ViewModel 的构造函数?
- php - Laravel 5.5 解析错误:使用 php 7.0 发送邮件时出现语法错误
- javascript - 根据复选框状态在搜索按钮上发出值,AngualrJS
- python - 隐藏层的训练不会提高准确性
- c++ - 如何分析哪部分代码创建了线程?
- python - 如何在可变数组中使用 SQLAlchemy 进行搜索
- css - Ionic 中的圆角警报