Homework Assignment #28

Objective

To solve a hard single-player puzzle by formulating the problem and designing an A* algorithm as the solution.

Exercises

Show all work neatly.

Question 1

Select a difficult single-player puzzle (e.g., Rubik's cube, …) which can be construed as an optimization problem. Then design an A* algorithm by taking the following steps:

  1. defining a state
  2. defining an initial state
  3. defining a state expansion strategy
  4. defining a goal state / solution test / criterion function
  5. defining a function $g(n)$ for the “cost so far”
  6. designing an admissible heuristic function $h(n)$ – an optimistic bound on the true “cost to go”
  7. Be sure to justify why your heuristic is admissible.
cs-312/hw28.txt · Last modified: 2015/03/30 21:53 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