Consider the following problem.

You are given the maze figure below and asked to find a way to the exit with a minimum number of decisions to make (a decision is required whenever there is at least one available direction to go). At the right of the maze figure we have pointed out these critical positions and given them numbers. Also the circles coloured in cyan are the start (1) and the finish (10).

On the basis of this diagram we will draw a graph with the following rules :

• the vertices are the critical positions

• there is an edge from X to Y if we can go from X to Y by making exactly one decision

It is easy to see now that the minimum length path is 1, 3, 14, 15, 10 with 4 decisions to make (the number of edges connecting the vertices). This is because we have an overview of the maze, we know every detail about it in advance. But what if we do not ? We would never be aware of the consequences of our current decision until we make it. What would be our strategy then ?

1 2 3

Next