4.10We gave two simple heuristics for the 8-puzzle:: Manhattan distanceand mispl

Question

4.10We gave two simple heuristics for the 8-puzzle:: Manhattan distanceand misplaced tiles. Several heuristics in the literature purport to improve onthis-see, for example, Nilsson (1971), Mostow and Prieditis (1989), and Hansson et al. (1992).Test these claims by implementing the heuristics and comparing the perform;znce of theresulting algorithms. 1.Recurssive best first search 2.best first search 3.greedy best first search 4.A* 4.10We gave two simple heuristics for the 8-puzzle:: Manhattan distanceand misplaced tiles. Several heuristics in the literature purport to improve onthis-see, for example, Nilsson (1971), Mostow and Prieditis (1989), and Hansson et al. (1992).Test these claims by implementing the heuristics and comparing the perform;znce of theresulting algorithms. 1.Recurssive best first search 2.best first search 3.greedy best first search 4.A*

Explanation / Answer

h1 = the number of misplaced tiles

h1(s)=8

h2 = the sum of the distances of the tiles from their goalpositions (manhattan distance).

h2(s)=3+1+2+2+2+3+3+2=18

f(n) for each node is an estimate of "desirability" and Expandmost desirable unexpanded node

Greedy Best-First Search:

It cannot complete because it can get stuck in loops,

It takes time O(b^m), but a good heuristic can give dramaticimprovement

Space complexity O(b^m), keeps all nodes in memory

A*:

No other optimal algorithm is guaranteed to expand few nodeslike this

Complete, optimal and optimally efficient

Time complexity is bad, space complexity is worse

Recursive best-first search (RBFS):

It tries to mimic best-first in linear space

Keeps track of the f-value of the best alternative path from anyancestor of the current node

If current node exceeds that limit, it unwinds back to thealternate path

I hope it will helps you!!!!!!!

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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