Re: cse471 hw2

[Subbarao Kambhampati <rao@asu.edu>]

I think you are forgetting g

f(n)=g(n) + h(n)

In the case of uniform cost search as well as non-uniform cost search

h(n) = 0
g(n) = g(parent(n)) + Cost(parent(n),n))

g(root) = 0

When all edges have unifrom (unit) cost

  Cost(parent(n),n) = 1
Thus g(n) = depth(n)

When edges have non-uniform cost, you just plug the correct value of
cost(parent(n),n) into the equation for every pair of nodes n, parent(n)

Hope this helps.

Rao


At 02:34 PM 9/23/2001 -0700, you wrote:
>I have a question about A* search algorithm.
>
>If you have a tree with a uniform path cost, meaning that all nodes have the
>same path cost, and your heuristic is h=0 so the queue will not be
>prioritized by the shortest path to the goal node...... then is this the same
>as doing BFS?
>
>
>But what if you have a tree with an non-uniform path cost, meaning that each
>node
>has a different path cost, and your heuristic is h=0.....how is this different
>from the previous algorithm?
>
>
>-snehal