Homework Assignment #27

Exercises

Design an A* algorithm for the 8-puzzle in the 5 questions posed below. Assume the start state and goal state for the puzzle as shown here:

15Puzzle.png

(Image Credit: Russell & Norvig)

Question 1

Specify your state.

Question 2

Describe your state expansion strategy.

Question 3

Describe your path cost function $g(n)$.

Question 4

Describe your admissible heuristic function $h(n)$. Together $g(n)$ and $h(n)$ constitute your evaluation function (like a bound function). How do you know that $h(n)$ constitutes a lower bound on future cost and is therefore admissible?

Question 5

Describe your solution (goal) test.

Resources

Here is an online version of the game: http://mypuzzle.org/sliding

And here is an animated solution that may help you better understand the game: http://www.youtube.com/watch?v=p8fhSIUNXMU

cs-312/hw27.txt · Last modified: 2015/03/27 14:44 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0