Hi All, A* search with consistent heuristics is supposed to ensure that an optimal path to a repeated state is always the first path generated, but consider the following example:
/---4--->A(h=15)--30-->\ S(h=18) G (h=0) \ ---5--->B(h=17)--20-->/ where S and G are the start and goal nodes respectively, in this case G is a repeated state which is also the goal state, but carry out A* on the above graph, we get: Expand S: get children A (f = 4 + 15 = 19) and B (f = 5 + 17 = 22), and A has a smaller f value, we next expand A Expand A: get child G (f = 34 + 0 = 34) at this point we obviously have a sub-optimal path to G with cost 34 > the optimal cost of 5 + 20 = 25? Is this just a special case where the goal is also a repeated state or am I missing something here? Thanks in advance. e. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.