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

Iterative Deepening

The stack that is used in depth first search is implemented as a doubly linked list.


In [ ]:
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 procedure search tries to find a solution to the search problem by first trying to find a solution that has a length of $1$, then of length $2$, then of length $3$, etc. The search only stops when a solution is found.


In [ ]:
def search(start, goal, next_states):
    limit = 1
    while True:
        Path = depth_limited_search(start, goal, next_states, limit)
        if Path != None:
            return Path
        limit += 1

The function depth_limited_search tries to find a solution to the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle $$ that has a length of at most limit. The algorithm used is depth first search.


In [ ]:
def depth_limited_search(state, goal, next_states, limit):
    Stack = deque([[start]])
    while len(Stack) > 0:
        Path  = Stack.pop()
        state = Path[-1]
        if state == goal:
            return Path
        if len(Path) >= limit:  # A path that has a length of limit or more
            continue            # is discarded.
        for ns in next_states(state):
            if ns not in Path:
                Stack.append(Path + [ns])

Solving the Sliding Puzzle


In [ ]:
%run Sliding-Puzzle.ipynb

In [ ]:
%%time
Path = search(start, goal, next_states)
print(len(Path)-1)

In [ ]:
animation(Path)

In [ ]: