In [ ]:
%%HTML
<style>
.container { width:100% }
</style>
The function search
takes four 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.heuristic
is a function that takes two states as arguments.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
uses iterative deepening to compute a solution of the given search problem.
In [ ]:
def search(start, goal, next_states, heuristic):
limit = heuristic(start, goal)
while True:
print(f'Trying to find a solution of length {limit}.')
Path = dl_search([start], goal, next_states, limit, heuristic)
if isinstance(Path, list):
return Path
limit = Path
The function dl_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
. It uses heuristic
to cut short a search that would be unsuccessful. If it can not find a solution that satisfies the given limit
, it returns a number that is a lower bound for the
length of the solution. This lower bound will always be greater than limit and can be used in the next attempt to search for a solution.
In [ ]:
def dl_search(Path, goal, next_states, limit, heuristic):
state = Path[-1]
distance = len(Path) - 1
total = distance + heuristic(state, goal)
if total > limit:
return total
if state == goal:
return Path
smallest = float("Inf") # infinity
for ns in next_states(state):
if ns not in Path:
Solution = dl_search(Path + [ns], goal, next_states, limit, heuristic)
if isinstance(Solution, list):
return Solution
smallest = min(smallest, Solution)
return smallest
In [ ]:
%run Sliding-Puzzle.ipynb
In [ ]:
%%time
Path = search(start, goal, next_states, manhattan)
print(len(Path)-1)
In [ ]:
animation(Path)
In [ ]:
%%time
Path = search(start2, goal2, next_states, manhattan)
print(len(Path)-1)
In [ ]:
animation(Path)
In [ ]: