<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 A$^$-IDA$^$ Search
Step1:  The function search takes four arguments to solve a search problem
Step2:  Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.
Step3:  Let's draw the start state and animate the solution that has been found.
<ASSISTANT_TASK:>
Python Code:
import heapq
Explanation: A$^$-IDA$^$ Search
End of explanation
def search(start, goal, next_states, heuristic, size):
    Parent    = { start: start }
    PrioQueue = [ (heuristic(start, goal), [start]) ]
    while len(Parent) < size and PrioQueue:
        _, Path = heapq.heappop(PrioQueue)
        state   = Path[-1]
        if state == goal:
            return Path
        for ns in next_states(state):
            if ns not in Parent:
                prio = heuristic(ns, goal) + len(Path)
                Parent[ns] = state
                heapq.heappush(PrioQueue, (prio, Path + [ns]))
    Path = id_search(goal, start, next_states, heuristic, Parent)
    return path_to(Path[-1], Parent) + Path[::-1][1:]
def id_search(goal, start, next_states, heuristic, Parent):
    limit = heuristic(start, goal)
    while True:
        print(f'limit = {limit}')
        Path = dl_search([goal], start, next_states, limit, heuristic, Parent)
        if isinstance(Path, list):
            return Path
        limit = Path
def dl_search(Path, start, next_states, limit, heuristic, Parent):
    state = Path[-1]
    total = len(Path) - 1 + heuristic(state, start)
    if total > limit:
        return total
    if state in Parent:
        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, Parent
                              )
            if isinstance(result, list):
                return result
            smallest = min(smallest, result)
    return smallest
Explanation: 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, 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.
End of explanation
def path_to(state, Parent):
    p = Parent[state]
    if p == state:
        return [state]
    return path_to(p, Parent) + [state]
Explanation: Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.
End of explanation
%run Sliding-Puzzle.ipynb
%load_ext memory_profiler
%%time
Path = search(start, goal, next_states, manhattan, 1000)
print(len(Path)-1)
animation(Path)
%%time
Path = search(start2, goal2, next_states, manhattan, 10000)
print(len(Path)-1)
animation(Path)
Explanation: Let's draw the start state and animate the solution that has been found.
End of explanation
<END_TASK>