BFS implementation in python not fast enough

Question

I'm trying to speed up my BFS algorithm, that solves rush hour games. I feed the algorithm a parent board, and I'm wondering whether the implementation of my BFS algorithm or the building blocks used in my code that I call from the algorithm should change.

This is the BFS algorithm at the moment:

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))

The start grid, for example, looks like this:

 start_grid = [['.', '.', 'T', 'F', 'F', 'E'],
         ['.', '.', 'T', '.', '.', 'E'],
         ['.', '.', 'T', 'R', 'R', 'E'],
         ['.', '.', '.', 'C', '.', '.'],
         ['A', 'B', 'B', 'C', '.', '.'],
         ['A', '.', '.', 'C', 'H', 'H']]

Is there something I'm doing inherently wrong here?

Dennis Soemers · Accepted Answer · 2018-02-20 11:54:03Z

1

Do your set_up(vehicle_dict,df_grid), get_movelist(key, value, vehicle_dict, df_grid), and/or move(node, copy.deepcopy(vehicle_dict), df_grid) modify the df_grid passed into them? If not, I highly doubt many of those deep copies you're doing are necessary. You'll want to carefully check to make sure yourself, but I think the following lines dont need all those deep copies:

queue.append(copy.deepcopy(child_df_grid))
archive.append(copy.deepcopy(child_df_grid))
archive.append(copy.deepcopy(df_grid))

I think you can also move archive.append(copy.deepcopy(df_grid)) to before the while loop, so that you can immediately discard moves that do nothing.

Checking whether you've seen a board before using

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

also seems inefficient. What kind of object is archive anyway? I'd recommend using a 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__ and __hash__ functions (required for set) would probably be better. Then you can efficiently check if something is truly new using:

if not child_df_grid in archive:

answered Feb 20, 2018 at 11:54

Dennis Soemers

8,5882 gold badges40 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

R A Over a year ago

Archive is just a list, I'm going to try the set alternative.

R A Over a year ago

It's true that saving the boards as data frames is excessive. I wasn't aware of the extra computing time that a pd.dataframe could give

R A Over a year ago

Although, hashing a dict isn't possible either. I'm not sure if this will increase my computing time, for I'm working with dict and pd.dataframes

Dennis Soemers Over a year ago

Yeah hashing is problematic there, which is why I suggested building your own custom class to hold your data. I dont think it needs to be fancy, just a class wrapped around a simple matrix/nested lists, with a few supporting functions (like __eq__ and __hash__ and anything else you may find useful)

Collectives™ on Stack Overflow

BFS implementation in python not fast enough

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related