Algorithms For Dummies

Representing the problem as a space

A problem space is an environment in which a search for a solution takes place.  

A set of states and the operators used to change those states represent the prob-

lem space. For example, consider a tile game that has eight tiles in a 3-x-3 frame. 

Each tile shows one part of a picture, and the tiles start in some random order so 

that the picture is scrambled. The goal is to move one tile at a time to place all the 

tiles in the right order and reveal the picture. You can see an example of this sort 

of puzzle at 

http://mypuzzle.org/sliding

.

The combination of the start state, the randomized tiles, and the goal state — the 

tiles in a particular order — is the problem instance. You could represent the puzzle 

graphically  using  a  problem space graph.  Each  node  of  the  problem  space  graph 

presents  a  state  (the  eight  tiles  in  a  particular  position).  The  edges  represent 

operations, such as to move tile number eight up. When you move tile eight up, 

the picture changes — it moves to another state.

Winning the game by moving from the start state to the goal state isn’t the only 

consideration. To solve the game efficiently, you need to perform the task in the 

least number of moves possible, which means using the smallest number of opera-

tors. The minimum number of moves used to solve the puzzle is the problem depth.

---

34

 

   

  PART 1