

In [ ]:

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

Breadth First Search

The function search takes three arguments to solve a search problem:

start is the start state of the search problem,
goalis the goal state, and
next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states. For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step. If successful, search returns a path from start to goal that is a solution of the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$



In [ ]:

    
def search(start, goal, next_states):
    Frontier = { start }
    Visited  = set()
    Parent   = { start: start }
    while len(Frontier) > 0:
        NewFrontier = set()
        for s in Frontier:
            for ns in next_states(s):
                if ns not in Visited and ns not in Frontier:
                    NewFrontier.add(ns)
                    Parent[ns] = s
                    if ns == goal:
                        return path_to(goal, Parent)
        Visited |= Frontier
        Frontier = 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.get(state)
    if p == state:
        return [state]
    return path_to(p, Parent) + [state]

Display Code

Below, we ensure that we only import graphviz if this notebook is not loaded from another notebook. This works by checking that the variable file is not set.



In [ ]:

    
import graphviz as gv

The function $\texttt{toDot}(\texttt{source}, \texttt{Edges}, \texttt{Fringe}, \texttt{Visited})$ takes a graph that is represented by its Edges, a set of nodes Fringe, and set Visited of nodes that have already been visited.



In [ ]:

    
def toDot(source, goal, Edges, Frontier, Visited, Parent=None):
    V = set()
    for x, L in Edges.items():
        V.add(x)
        for y in L:
            V.add(y)
    dot = gv.Digraph(node_attr={'shape': 'record', 'style': 'rounded'})
    dot.attr(rankdir='LR', size='8,5')
    for x in V:
        if x == source:
            dot.node(str(x), color='blue', shape='doublecircle')
        elif x in Frontier and x == goal:
            dot.node(str(x), label=str(x), color='magenta')
        elif x in Frontier:
            dot.node(str(x), label=str(x), color='red')
        elif x in Visited:
            dot.node(str(x), label=str(x), color='blue')
        else:
            dot.node(str(x), label=str(x))
    if Parent:        
        Path = path_to(goal, Parent)
    for u in V:
        if Edges.get(u):
            for v in Edges[u]:
                if Parent and v in Path and Parent[v] == u:
                    dot.edge(str(u), str(v), color='brown', style='bold')                    
                else:
                    dot.edge(str(u), str(v))
    return dot

Testing



In [ ]:

    
def next_states_test(node):
    x, y = node
    return { (x+1, y), (x, y+1) }



In [ ]:

    
def create_edges(n):
    Edges = {}
    for row in range(n):
        for col in range(n):
            if (row, col) != (n-1, n-1):
                Edges[(row, col)] = list(next_states_test((row, col)))
    for k in range(n-1):
        Edges[(k, n-1)] = [(k+1, n-1)]
        Edges[(n-1, k)] = [(n-1, k+1)]
    return Edges



In [ ]:

    
def search_show(start, goal, next_states, Edges):
    Visited  = set()
    Frontier = { start }
    Parent   = { start: start }
    while len(Frontier) > 0:
        display(toDot(start, goal, Edges, Frontier, Visited))
        NewFrontier = set()
        Visited    |= Frontier
        for s in Frontier:
            for ns in next_states(s):
                if not (ns in Visited):
                    NewFrontier.add(ns)
                    Parent[ns] = s
                    if ns == goal:
                        display(toDot(start, goal, Edges, NewFrontier, Visited, Parent))
                        return 
        Frontier = NewFrontier



In [ ]:

    
def main(n):
    Edges = create_edges(n)
    search_show((0,0), (n-1,n-1), next_states_test, Edges)



In [ ]:

    
main(9)

Saving the Infidels



In [ ]:

    
%run Missionaries.ipynb



In [ ]:

    
start = (3, 3, 1)
goal  = (0, 0, 0)



In [ ]:

    
dot_graph(createRelation(start))



In [ ]:

    
%%time
Path  = search(start, goal, nextStates)
printPath(Path)

Solving the Sliding Puzzle

The magic command %run can be used to import the code of another notebook.



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

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



In [ ]:

    
animation(Path)