Dear Eric, Initially, we just at the border node S (18).
After expanding the node S, the border is with A (19), B (22). Node A is the smallest of the border. After expanding A, the border is with B (22), G (34) Node B is the smallest of the border. After expanding B, the border is with G (25) Node G is the smallest of the border. You finish the algorithm when the node G is the smallest of the border not when he enters the boundary Wladimir Araujo Tavares *Federal University of Ceará * On Fri, May 13, 2011 at 6:14 PM, xuwenduan <xuwend...@gmail.com> wrote: > 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. > > -- 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.
