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.
