Can a given problem be split into a set of smaller problems?

As an example consider the one below taken from the blocks world

There are only two operations and each is indicated above. In simple terms only one block can be moved at a time and the movement of blocks allows blocks to be moved off towers of blocks onto the table or from the table or one tower to another tower of blocks.

The starting position is a state, known as the start state, and the final position is the goal state.

The problem solution is shown. It would appear that the problem splits conveniently into two, but unfortunately the two sub- problems are dependent on one another and this hinders the expected progress. Problems split into at least two categories those that can be split into independent subproblems and those where the solution of one subproblem affects the other.

In the 8 tile problem there are simple mechanisms for proceeding from initial states to goal states. There are eight interlocking tiles of uniform square shape on a square tray of side 3 and the initial state consists of the tiles placed in arbitrary position as shown. The object of the puzzle or problem is to rearrange the tiles into a given ordered position, the goal state. As there are only eight tiles on the tray the operations allowed are simply to move any tile adjacent to the blank spot into the blank spot thus vacating the place of that tile. As in general any spot on the tray has four neighbours the number of possible moves increases considerably and the number of intermediate states between the initial state or start state and the goal state can be huge. The merit of having an efficient searching procedure are manifest.

initial state goal state

2 7 5 - 8 7

3 6 4 4 5 6

1 - 8 3 2 1

The problem is also interesting as it illustrates the point that some moves can be irrelevant to the solution and others can be undone. For example from the initial state we could move 6 into the space and back again. Contrast this with a game like chess where one error can lose the game.

In summary there are three types of problem. Ones where solution steps can be ignored, others where solution steps can be successfully recovered from, and the last set where steps lead to fatal errors.

Solutions

Solutions can be good in different ways . They can be good in terms of time or storage or in difficulty of the algorithm. In fig 2.13 showing that Marcus is dead is easy in two ways but usually when one has proved the fact it is not necessary to try other methods. In the case of the travelling salesman problem finding the best path can lead to a massive amount of computation as the large variety of paths possible create numerous time and search problems. The solution of such problems is often only possible by using heuristics. In this type of problem a path is found of distance 8850 miles and another of 7750. It is clear that the second is better than the first but is it the best. Infinite time may be needed and usually heuristics are used to find a very good path in finite time. A solution which is acceptable.

The subject of heuristic search will be considered fully in the next lecture.

The design of search programs.

Each search process can be considered to be a tree traversal exercise. In the case of the water jug problem the appropriate tree is shown in fig 2.18. The object of the search is to find a path from an initial state to a goal state using a tree. The number of nodes generated might be immense and in practice many of the nodes would not be needed. The secret of a good search routine is to generate only those nodes that are likely to be useful. Rather than having an explicit tree the rules are used to to represent the tree implicitly and only to create nodes explicitly if they are actually to be of use.

The following issues arise when searching:

the tree can be searched forwards from the initial node to the goal state or backwards from the goal state to the initial state.

how to select applicable rules, it is critical to have an efficient procedure for matching rules against states.

how to represent each node of the search process this is the knowledge representation problem or the frame problem. In games an array suffices in other problems more complex data structures are needed.

Finally in terms of data structures considering the water jug as a typical problem do we use a graph or tree. See figures 2.18 and 2.19

The breadth first does take note of all nodes generated but depth first can be modified.

Check duplicate nodes

1 examine all nodes already generated to see if new node is present.

2 if it does exist add it to the graph.

3 if it does already exist then

a set the node that is being expanded to point to the already existing node corresponding to its successor rather than to the new one.

The new one can be thrown away.

b if the best or shortest path is being determined check to see if this path is better or worse than the old one.

if worse do nothing.

if better save the new path and work the change in length through the chain of successor nodes if necessary.Heuristic Search methods

So far it has been observed that indirect methods that are used to solve tough problems involve some method of searching. Two methods have been clearly indicated depth first and breadth first. Once these general methods are applied to specific problems it becomes clear that they can be classified as weak methods, because thought has to be given on how to handle the specific knowledge involved in the problem to avoid the problems of combiatorial explosion. The progress made in this direction is one of the successes of the subject.

The other methods are:

Generate and test

Algorithm

1 repeat

2 generate a possible solution which can either be a point in the problem space or a path from the initial state.

3 test to see if this possible solution is a real solution by comparing the state reached with the set of goal states.

4 until it is a real solution.

This method is basically a depth first search as complete solutions must be created before testing. It is often called the British Museum method as it is like looking for an exhibit at random. A heuristic is needed to sharpen up the search. Consider the problem of four 6-sided cubes, and each side of the cube is painted in one of four colours. The four cubes are placed next to one another and the problem lies in arranging them so that the four available colours are displayed whichever way the 4cubes are viewed. The problem can only be solved if there are at least four sides coloured in each colour and the number of options tested can be reduced using heuristics if the most popular colour is hidden by the adjacent cube.

Hill climbing

Here the generate and test method is augmented by an heuristic function which measures the closeness of the current state to the goal state.

1 Evaluate the initial state if it is goal stae quit otherwise current state is initial state.

2 repeat

3 select a new operator for this state and generate a new state.

4 evaluate the new state

a if it is closer to goal state than current state make it current state

b if it is no better ignore

5 until the current state is goal state or no new operators available.

In the case of the four cubes a suitable heuristic is the sum of the number of different colours on each of the four sides, and the goal state is 16 four on each side. The set of rules is simply choose a cube and rotate the cube through 90 degrees. The starting arrangement can either be specified or is at random.