Divide and Conquer

One of the most popular algorithmic devices for computer scientists has been divide and conquer. Use of this method has led to the fast searches and sorts that every beginning student encounters. For some problems, it is also a good method for quick and easy approximations. Our strategy will be to divide an instance of a problem into smaller and smaller pieces until we are able to solve the problem for the smaller pieces. Then, if all goes well, joining together these good solutions for portions of the problem should provide a reasonable approximation to the original problem instance.

Closed City Tours shall be our first example. First, we divide our cities into eastern and western regions so that each region contains the same number of cities. Then we shall divide these into northern and southern sections in the same manner. Thus instead of merely bisecting the city space as a mathematician might do, we quadrisect the space in a computer science manner. Each region now contains roughly a quarter of the cities present in the original problem. This means that instead of (n-1)! possible tours, we now need only consider (n/4 – 1)! tours for each region. Figure 1 contains an example of a city space that has been partitioned.

Figure 1 - Regional Closed City Tours

If a region is small enough so that we can find an optimum closed tour then we do so. Otherwise, we keep partitioning the regions until we can compute optimum tours.

In figure 1, shortest closed tours have been found for each quadrant. The last step is to make connections between quadrants, and omit one of the links in each regional tour. A possibility is shown in figure 2.

Figure 2 – Connecting the Regional Tours

In general, a problem instance is split into halves (or quarters) and then these smaller problems are solved optimally if possible. If the subproblems are still too large, they are divided again. After all of the subproblems have been solved, then they are combined to form a solution to the main problem.

Note that the resulting solution is not necessarily optimum, even though it was built from optimum subsolutions. It is tempting to attempt to apply the ‘Principle of Optimality’ from dynamic programming, but close examination reveals that it stated that optimum solutions are composed of optimum subsolutions, not the other way around.

The next application of the divide and conquer technique shall be the chromatic number problem, or graph coloring. First, we take a graph such as that on the left in figure 3 and divide it into the two subgraphs as shown on the right. In this case, the division was done so that as few edges as possible crossed the boundary. The reason for that is so that there will be as few conflicts as possible between the regions. Now the two subgraphs can be colored optimally with three colors. The colorings are then resolved with the pairs <a, e>, <b, d>, and <c, f> taking identical colors.

Figure 3 - A Partitioned Graph

Figure 4 contains a general algorithm for divide and conquer strategies.

Figure 4 – General Divide and Conquer Algorithm