# IDA*

X

Description:
IDA* is a variant of the A* search algorithm which uses iterative deepening to keep the memory usage lower than in A*. It is an informed search based on the idea of the uninformed iterative deepening depth-first search.

The main difference to IDS is that it uses the f-costs (g + h) as the next limit and not just an iterated depth.

Pseudo code: <small>(see working Python code example below)</small>

<source lang="python">def IDA_star():
```cost_limit = heuristics
```

```while True:
(solution, cost_limit) = DFS(0, rootNode, cost_limit, )
if solution != None: return (solution, cost_limit)
if cost_limit == ∞: return None
```

1. returns (solution-sequence or None, new cost limit)
def DFS(start_cost, node, cost_limit, path_so_far):
```minimum_cost = start_cost + heuristics
if minimum_cost > cost_limit: return (None, minimum_cost)
if node in goalNodes: return (path_so_far, cost_limit)
```

```next_cost_limit = ∞
for succNode in successors:
newStartCost = start_cost + edgeCosts
(solution, new_cost_limit) = DFS(newStartCost, succNode, cost_limit, path_so_far + )
if solution != None: return (solution, new_cost_limit)
next_cost_limit = min(next_cost_limit, new_cost_limit)
```

```return (None, next_cost_limit)
```
</source>

The difference to A* can be seen from this pseudo code: it doesn't remember the current shortest path and costs for all visited nodes like in A* (that is why space-complexity is linear in A* to all visited nodes until it finds the...

No feeds found

All