

In [ ]:

    
%%HTML
<style>
.container { width:100% !important }
</style>

Bidirectional Breadth First Search



In [ ]:

    
def search(start, goal, next_states):        
    FrontierA = { start }
    VisitedA  = set()           # set of nodes expanded starting from start
    ParentA   = { start: start}
    FrontierB = { goal }
    VisitedB  = set()           # set of nodes expanded starting from goal
    ParentB   = { goal: goal} 
    while len(FrontierA) > 0 and len(FrontierB) > 0:
        VisitedA  |= FrontierA
        VisitedB  |= FrontierB
        print(len(VisitedA) +len(VisitedB))
        NewFrontier = set()
        for s in FrontierA:
            for ns in next_states(s):
                if ns not in VisitedA:
                    NewFrontier |= { ns }
                    ParentA[ns]  = s
                    if ns in VisitedB:
                        return combinePaths(ns, ParentA, ParentB)
        FrontierA   = NewFrontier
        NewFrontier = set()
        for s in FrontierB:
            for ns in next_states(s):
                if ns not in VisitedB:
                    NewFrontier |= { ns }
                    ParentB[ns]  = s
                    if ns in VisitedA:
                        return combinePaths(ns, ParentA, ParentB)
        FrontierB = NewFrontier

Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.



In [ ]:

    
def path_to(state, Parent):
    p = Parent[state]
    if p == state:
        return [state]
    return path_to(p, Parent) + [state]

The function combinePath takes three parameters:

state is a state that has been reached in bidirectional BFS from both start and goal.
ParentA is the parent dictionary that has been build when searching from start. If $\texttt{ParentA}[s_1] = s_2$ holds, then either $s_1 = s2 = \texttt{start}$ or $s_1 \in \texttt{next_states}(s_2)$.
ParentB is the parent dictionary that has been build when searching from goal. If $\texttt{ParentB}[s_1] = s_2$ holds, then either $s_1 = s2 = \texttt{goal}$ or $s_1 \in \texttt{next_states}(s_2)$. The function returns a path from startto goal.



In [ ]:

    
def combinePaths(state, ParentA, ParentB):
        Path1 = path_to(state, ParentA)
        Path2 = path_to(state, ParentB)
        return Path1[:-1] + Path2[::-1] # Path2 is reversed



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

    
%%time
Path = search(start, goal, next_states)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]: