Problem 5 [15 points]. Consider an informed, best-first search algorithm in whic

Question

Problem 5 [15 points]. Consider an informed, best-first search algorithm in which the evaluation function is (n) (2-w)g(n)+wh(n), 0w2. For what values of w is this algorithm guaranteed to be optimal when h is admissible (consider the case of TREE-SEARCH)? What kind of search does this perform when w-07 when w = 1? When w 2? In your proof. you may assume that if the heuristic in a standard A" search is inadmissible, then optimality cannol be guaranteed. Note that f(n) here doos not always dircctly correspond to the evaluation function in a standard A scarch. en ui

Explanation / Answer

f(n) = (2 – w)g(n) + wh(n)

g(n): a path cost to n from a start state

h(n): a heuristic estimate of cost from n to a goal state

Heuristic path algorithm If h(n) is admissible, the algorithm is guaranteed to be optimal

f(n)= (2-w) [g(n) +w/(2-w) h(n)]

which behaves exactly like A* search with a heuristic

                        f(n)= g(n)+w/(2-w) h(n)

to be optimal we require

                        w/(2-w)<=1

                        w<=1

For w = 0: f(n) = 2g(n) -> Uniform-cost search

For w = 1: f(n) = g(n) + h(n) -> A* search

For w = 2: f(n) = 2h(n) -> Greedy best search

Breadth-first search is a special case of uniform-cost search

When all step costs are equal , g(n) is just a multiple of depth n. Thus, breadth-first search and uniform-cost search would behave the same in this case

f(n) = g(n) = 1*(depth of n)

BFS, DFS and uniform-cost search are special cases of best-first search

BFS: f(n) = depth(n)

DFS: f(n) = -depth(n)

UCS: f(n) = g(n)

Uniform-cost search is special case of A* search

A* search: f(n) = g(n) + h(n)

Uniform-cost search: f(n) = g(n)

Thus, for h(n) = 0, uniform cost search will produce the same result as A* search

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.