python - python中的BFS实现不够快

我试着加速我的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']]

我是不是天生就做错了什么？

最佳答案

您的set_up(vehicle_dict,df_grid)、get_movelist(key, value, vehicle_dict, df_grid)和/或move(node, copy.deepcopy(vehicle_dict), df_grid)是否修改传递给它们的df_grid如果不是的话，我很怀疑你做的那些深层次的复制是必要的你需要仔细检查以确定你自己，但我认为以下几行不需要所有这些深拷贝：
queue.append(copy.deepcopy(child_df_grid))
archive.append(copy.deepcopy(child_df_grid))
archive.append(copy.deepcopy(df_grid))
我认为您还可以将archive.append(copy.deepcopy(df_grid))移动到while循环之前，这样您就可以立即放弃不起作用的移动。
在使用前检查你是否见过一块木板

if not True in [child_df_grid.equals(x) for x in archive]:

也似乎效率低下。到底是什么样的对象？我建议使用archive（不是列表！）。如果您的板被表示为sets，则这可能无法正常工作（这里乍一看似乎有点过于复杂，而没有看到其他功能是如何实现的）。使用correctly implementedpd.DataFrame和__eq__函数（set所需）来包含数据的简单自定义类可能会更好然后，您可以使用以下工具有效地检查是否有真正的新功能：

if not child_df_grid in archive:

关于python - python中的BFS实现不够快，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48882588/