In [ ]:
%%HTML
<style>
.container { width:100% }
</style>
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,goal
is the goal state, andnext_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])
In [ ]:
%run Sliding-Puzzle.ipynb
In [ ]:
%%time
Path = search(start, goal, next_states)
print(len(Path)-1)
In [ ]:
animation(Path)
In [ ]: