我正在尝试加快BFS算法的速度,它可以解决尖峰时刻的游戏。我为算法提供了一个父电路板,我想知道我的BFS算法的实现或我从算法调用的代码中使用的构建块是否应该更改。
这是目前的BFS算法:
def start_bfs(start_grid):
vehicle_dict = dict()
queue = deque()
queue.append(pd.DataFrame(start_grid))
while queue:
vehicle_dict.clear()
df_grid = queue.pop()
vehicle_dict = set_up(vehicle_dict,df_grid)
for key, value in vehicle_dict.iteritems():
check_adjecent(key, value, vehicle_dict)
movelist, object_location, direction = get_movelist(key, value, vehicle_dict, df_grid)
if not movelist:
continue
while movelist:
node = movelist.pop(0)
new_vehicle_dict = move(node, copy.deepcopy(vehicle_dict), df_grid)
child_df_grid = create_board(new_vehicle_dict)
if not True in [child_df_grid.equals(x) for x in archive]:
check_goal(node[1], new_vehicle_dict, archive, df_grid, child_df_grid)
queue.append(copy.deepcopy(child_df_grid))
archive.append(copy.deepcopy(child_df_grid))
archive.append(copy.deepcopy(df_grid))
例如,起始网格如下所示:
start_grid = [['.', '.', 'T', 'F', 'F', 'E'],
['.', '.', 'T', '.', '.', 'E'],
['.', '.', 'T', 'R', 'R', 'E'],
['.', '.', '.', 'C', '.', '.'],
['A', 'B', 'B', 'C', '.', '.'],
['A', '.', '.', 'C', 'H', 'H']]
这里有没有什么我天生就做错的事?
