Section 2: Search Methods Consider the A* search problem shown here. The path co

Question

Section 2: Search Methods Consider the A* search problem shown here. The path cost g(x) is the actual distance from the start state S to an intermediate state, while the heuristic h(x) is the estimated distance from an intermediate state to the goal state G. Answer the given questions. [2 points each, total 10 points] Distance (S ? A) = 10 Distance (S -> B)-5 Distance (S ? C)-8 Distance (S > D)-7 Distance (S -> G)-25 Estimate (A -> G)-11 Estimate (B -> G)-14 Estimate (C- G)-12 Estimate (D -> G)-15 Estimate (G -> G)-0 [Obvious] 6. The function f(x) used to trace the path from start to goal in A* is a) f(x)=g(x)+h(x) b) fx)-g(x)-h(x) d) None of these

Explanation / Answer

Answer is as follows :

According to Chegg Guidelines we are allowed to solve only section 2 i.e.Search Methods , so please repsot others.

So answer of Section 2 is as follows :

6) We know that f(x) is calculated in A* by adding both functions i.e. g(x) and h(x)

So Correct option is A i.e. f(x) = g(x) + h(x)

7) For C

We have g(x) = 8, from S->C

and h(x) = 12, from C->G

So by adding both we get = 8+10 = 20.

So correct option is B

8) From given information we get that

f(x) for A = 10 + 11 = 21

f(x) for B = 5 + 14 = 19

f(x) for C = 8 + 12 = 20

f(x) for D = 7 + 15 = 22

So from above we get largest path is for State D

So correct option is D

10) The A* algorithm will move to next state that have smaller path than others. In this case the state B has smaller path from start state S as compare to others.

So correct option is B i.e. state B.

11) By underestimating heuristic function in A*, we get optimal solution of problem

So correct option is B

if there is any query please ask in comments...

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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