Hi, This can be mathematically proved if the heuristic you use is less than or equal to the actual cost ( the straight line heuristic is a natural example ).
The proof is as follows : You will maintain a list of nodes with their costs. You will goal - test the least cost node. If it is not a goal then you will list all its nodes and rearrange the list by cost. Now suppose you find a goal G1 , we have to prove there could have not been any goal G2 which has a lower total cost. This is trivially true from our initial condition that we are underestimating goal costs. Actual cost (G2) < Actual cost (G1) => heuristic cost (G2) < Actual cost (G1) => G2 would have been expanded first. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
