Bidirectional Depth-First Search

,

Pseudo-code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BDS(node N0, int cut_off_depth):
    cur_limit = 0
    while cur_limit < cut_off_depth:
        if DFS_dir({N0}, G, deeper, cur_limit):
            return success
        else:
            store all states at depth cur_limit in H
        
        if DFS_dir(G, H, prev, cur_limit):
            return success
        
        // avoid skipping case that total depth from N0 to G is odd
        if DFS_dir(G, H, prev, cur_limit + 1):
            return success
        
        cur_limit += 1
    return failure

Explanation

Why search from G to H?

If G (the goal state) can reach H (the set of states at depth cur_limit from N0), then there exists a path from N0 to G through H. This is because H contains all states that are exactly cur_limit steps away from N0, and if G can reach any of these states, it implies that there is a valid path from N0 to G.

Why cur_limit + 1?

If G can reach H with a depth limit of cur_limit, the total depth L from N0 to G is 2 * cur_limit, which is even. However, this doesn’t account for cases where the total depth L is odd. By also checking with a depth limit of cur_limit + 1, we can capture scenarios where the path from N0 to G has an odd length, specifically 2 * cur_limit + 1. This ensures that we do not miss any potential paths due to the parity of the total depth.

References