Search code examples
algorithmdata-structuresa-star

There is a loop in the node of close list of A* algorithm

I am learning A* algorithm and try to implement it. However, I found there are two conditions in which the final path will be possibly failed to be backtracked from the target node:

  1. a child-node has two or more parent-node;
  2. Especially, there will be a loop structure in the path (meaning for a node P, some of its parent nodes will be simultaneously its child nodes). These two possible errors came to my mind after reading the pseudocode of A*. I hope to try to understand why these two errors can be avoided but failed. Additionally, there is very little mention of these two possible conditions in the resources I have been able to find. Therefore, can any body help me to prove that why these two conditions will not happen? Or, how to prevent the algorithm from this two conditions? Many thanks!
Solution

  • a child-node has two or more parent-node

    If a node is reached by a second path, it doesn't add another parent -- instead, it evaluates which of those paths is least "costly" and makes the parent be that path.

    So, you won't ever have two paths. The least costly path back is always the parent.

    there will be a loop structure in the path

    As soon as a node has been explored (once) in the current path, it is removed from the set of potential nodes to explore in the current path. Thus, there's no way to "loop back" because to the algorithm, already-explored nodes don't exist anymore as potential options.