Home | | **Artificial Intelligence** | | **Computational Intelligence** | | **Artificial Intelligence** | Real-Time A*

Real-time A* is a variation of A*.

**Real-Time A***

Real-time
A* is a variation of A*.

Search
continues on the basis of choosing paths that have minimum values of f(node) =
g(node) + h(node). However, g(node) is the distance of the node from the current
node, rather than from the root node.

Hence,
the algorithm will backtrack if the cost of doing so plus the estimated cost of
solving the problem from the new node is less than the estimated cost of
solving the problem from the current node.

Implementing
real-time A* means maintaining a hash table of previously visited states with
their h(node) values.

**Iterative-Deepening A* (IDA*)**

By
combining iterative-deepening with A*, we produce an algorithm that is optimal
and complete (like A*) and that has the low memory requirements of depth-first
search.

IDA* is a
form of iterative-deepening search where successive iterations impose a greater
limit on f(node) rather than on the depth of a node.

IDA*
performs well in problems where the heuristic value f (node) has relatively few
possible values.

For
example, using the Manhattan distance as a heuristic in solving the
eight-queens problem, the value of f (node) can only have values 1, 2, 3, or 4.

In this
case, the IDA* algorithm only needs to run through a maximum of four
iterations, and it has a time complexity not dissimilar from that of A*, but
with a significantly improved space complexity because it is effectively
running depth-first search.

In cases
such as the traveling salesman problem where the value of f (node) is different
for every state, the IDA* method has to expand 1 + 2 + 3 + . . . + n nodes = O(n2)
where A* would expand n nodes.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.