- Refer to the 8-puzzle problem described below.
- Suppose we want to add some knowledge to your blind search design to speed it up.
- What knowledge/information/heuristics will you add? (I’m looking for a description of how you’ll use outside knowledge of the problem to guide the search here.)
- What kind of improvement do you expect to have with your heuristic? (Less states searched? Better solution found? Something else?)
- How much improvement do you expect to have? A lot? A little? Why?
Purpose
This assignment is intended to help you learn to solve a problem with Blind Search.
The Problem
The “8-puzzle” (or “15-puzzle”) is a “sliding tile” puzzle that you’ve probably seen one place or another. Here’s the Wikipedia article on it (https://en.wikipedia.org/wiki/15_puzzle).
Basically, you’re given a 3×3 (or 4×4) grid of tiles, with tiles holding the numbers 1-8 (or 1-15), and one cell empty.
Please find the attachment for the initial and final states
A “move” is to move a tile above, below, to the left, or to the right of the blank into the empty space (which makes space previously holding the tile now empty).
Action Items
- Suppose we want to develop an AI-based search system to solve the problem described above. Answer the following questions about the design of the solution:
- How will you represent a “state” in this system?
- How will you represent an action in this system? How does it generate a new state?
- What is the (worst-case) branching factor for your design?
- If we are using uninformed search to solve this, do you think Breadth-First Search or Depth-First Search will be better? Why? Is there anything you need to worry about?
- Submit your work by the due date.