'Why does inconsistent hueristic cause expansion of repeated nodes in A*?
I am aware that we need to follow the triangle inequality for consistent heuristic I.e,
h(n)< c(n,a,n')+ h(n')
My understanding of why it might cause repeated nodes to be expanded is that , suppose we discover a shortest path from node 'n' to goal node , and suppose we discover another path to node 'n' that covers the same node , but has a shorter straight line distance to goal, then we will have to traverse the same node twice (atleast), first to reach the node n and then to reach the same node again to follow the shortest path . So this is why the same node may be visited again . Is it right or is there some flaw in my understanding?
Thank you!
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|