

In [ ]:

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

A$^$-IDA$^$ Search

The module Set implements sets as AVL trees. The API provided by Set offers the following functions and methods:

Set() creates an empty set.
S.isEmpty() checks whether the set Sis empty.
S.member(x) checks whether x is an element of the set S.
S.insert(x) inserts x into the set S. This does not return a new set but rather modifies the set S.
S.delete(x) deletes x from the set S. This does not return a new set but rather modifies the set S.
S.pop() returns the smallest element of the set S. Furthermore, this element is removed from S. Since sets are implemented as ordered binary trees, the elements of a set need to be comparable, i.e. if x and y are inserted into a set, then the expression x < y must return a Boolean value and < has to define linear order.

The module Set can be used to implement a priority queue that supports the removal of elements.



In [ ]:

    
import Set

The function search takes four 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.
heuristic is a function that takes two states as arguments. It returns an estimate of the length of the shortest path between these states.
size is the maximum number states that A$^*$ search is allowed to explore.

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 function search implements A$^*$-IDA$^*$ search. The main idea of A$^*$-IDA$^*$ is to run an $\mathrm{A}^*$ search from the node start until memory is more or less exhausted. Then, we start $\mathrm{IDA}^*$ from the node goal node and search towards the node start until we find any of the nodes discovered by the $\mathrm{A}^*$ search that had been started from the node start node.



In [ ]:

    
def search(start, goal, next_states, heuristic, size):
    Parent   = { start:start }
    Distance = { start: 0 }           
    estGoal  = heuristic(start, goal)
    Estimate = { start: estGoal }
    Frontier = Set.Set()
    Frontier.insert( (estGoal, start) )
    while len(Distance) < size and not Frontier.isEmpty():
        estimate, state = Frontier.pop()
        if state == goal:
            return path_to(state, Parent)
        stateDist = Distance[state]
        for ns in next_states(state):
            oldEstimate = Estimate.get(ns, None)
            newEstimate = stateDist + 1 + heuristic(ns, goal)
            if oldEstimate == None or newEstimate < oldEstimate:
                Distance[ns] = stateDist + 1
                Estimate[ns] = newEstimate
                Parent[ns]   = state
                Frontier.insert( (newEstimate, ns) )
                if oldEstimate != None:
                    Frontier.delete( (oldEstimate, ns) )
    Path = id_search(goal, start, next_states, heuristic, Distance)
    return path_to(Path[-1], Parent) + Path[::-1][1:]



In [ ]:

    
def id_search(goal, start, next_states, heuristic, Distance):
    limit = 0
    while True:
        print(f'limit = {limit}')
        Path = dl_search([goal], start, next_states, limit, heuristic, Distance)
        if isinstance(Path, list):
            return Path
        limit = Path



In [ ]:

    
def dl_search(Path, start, next_states, limit, heuristic, Distance):
    state = Path[-1]
    total = len(Path) - 1 + heuristic(state, start)
    if total > limit:
        return total
    if state in Distance:
        return Path
    smallest = float('Inf')
    for ns in next_states(state):
        if ns not in Path:
            result = dl_search( Path + [ns], start, next_states, 
                                limit, heuristic, Distance
                              )
            if isinstance(result, list):
                return result
            smallest = min(smallest, result)
    return smallest

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]

Lets draw the start state and animate the solution that has been found.



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

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



In [ ]:

    
animation(Path)



In [ ]:

    
%%time
Path = search(start2, goal2, next_states, manhattan, 3000)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]:

A$^*$-IDA$^*$ Search

A$^$-IDA$^$ Search