

In [1]:

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

Depth First Search, Stack Based Implementation

The class deque from the module collections provides doubly linked lists that can be used as stacks.



In [2]:

    
from collections import deque

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. $$

The implementation of search works as follows:

Any states that are encountered during the search are placed on top of the stack Stack.
In order to record the information how a state has been added to the Stack, we have a dictionary Parent. For every state $s$ that is on Stack, $\texttt{Parent}[s]$ returns a state $p$ such that $s \in \texttt{next_states}(p)$, i.e. $p$ is the state that immediately precedes $s$ on the path that leads from start to $s$.
Initially, Stack only contains the state start.
As long as Stack is not empty, the state on top of Stack is replaced by all states that be reached in one step from state. However, in order to prevent depth first search to run in circles, only those states nsfrom the set next_states(state) are appended to Stack that have not been encountered previously. This is checked by testing whether ns is in the domain of Parent.
When the goal is reached, a path leading from start to goal is returned.



In [3]:

    
def search(start, goal, next_states):
    Stack  = deque([start])
    Parent = { start: start }
    while len(Stack) > 0:
        state = Stack.pop()
        for ns in next_states(state):
            if ns == goal:
                return path_to(state, Parent) + [goal]
            if ns not in Parent:
                Parent[ns] = state
                Stack.append(ns)

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



In [4]:

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

Solving the Sliding Puzzle



In [5]:

    
%run Sliding-Puzzle.ipynb

We need to import sys in order to increase the recursion limit.



In [6]:

    
import sys



In [7]:

    
sys.setrecursionlimit(10000)



In [8]:

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









    



8251
CPU times: user 259 ms, sys: 6.43 ms, total: 266 ms
Wall time: 265 ms



In [ ]: