I have an answer for my own question: I think I've misunderstood the statement in the book, which says:
...to ensure that the optimal path to any repeated state is always the first one followed. in the above example, we haven't actually started to follow (expand) G yet, so the statement about consistency is still valid. wenduan On May 13, 7:56 pm, eric <xuwend...@gmail.com> wrote: > 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.
