python 中的 BFS 实现速度不够快

Question

我正在尝试加快我的 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']]

有没有我做错了什么？

Answer 1

您的 set_up(vehicle_dict,df_grid)、get_movelist(key, value, vehicle_dict, df_grid)、and/or 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 到底是个什么样的对象？我建议使用 set (not a list!). That may not work correctly if your boards are represented as pd.DataFrames though (which also seems kind of overcomplicated at first glance here without seeing how your other functions are implemented). A simple custom class to contain your data, with correctly implemented __eq__ 和 __hash__ 函数（集合需要）可能会更好。然后你可以有效地检查一些东西是否真的是新的：

if not child_df_grid in archive:

python 中的 BFS 实现速度不够快

BFS implementation in python not fast enough

python

algorithm

breadth-first-search