

In [ ]:

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

Sphere Search



In [2]:

    
def search(start, goal, next_states):
    if goal == start:
        return [start]
    previous = basic_search(start, goal, next_states)
    if previous:
        return search(start, previous, next_states) + [goal]



In [1]:

    
def basic_search(start, goal, next_states):
    Frontier = { start }
    Visited  = set()
    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)
                    if ns == goal:
                        return s
        Visited  = Frontier
        Frontier = NewFrontier
        print(len(Visited))

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]

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 [ ]:

    
try:
    __file__
except NameError:
    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 the figures shown below, the nodes in the set Visited are colored blue, while the nodes in the set Frontier are colored red.



In [ ]:

    
try:
    __file__
except NameError:
    main(9)



In [ ]: