IDA*

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...
Read More