> 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
Yes, we finish with G=25, but we still have G=35 first. This is all right, since I understand now that a consistent heuristic (as the one in my example graph) only guarantees when a node is EXPANDED, the optimal path to it has already been found. So supposed we have another node after G, we when next expand G, we would already have G = 25. The statement about consistent heuristic in the book (Russll & Norvig): ...to ensure that the optimal path to any repeated state is always the first one followed. made me thought that we should always have G=25 first whenever we have a consistent heuristic, this is just my misrepresentation. thanks for your reply. wenduan. > > Wladimir Araujo Tavares > Federal University of Ceará > > > > > > > On Fri, May 13, 2011 at 6:14 PM, xuwenduan <[email protected]> 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 <[email protected]> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
