)
| [Japanese version] | [English version] |
| [Temporary Mirror Page (Fast!)] | [Original Page (Newer?!)] |
Map coloring problem is a constraint satisfaction problem (CSP) to color the areas in a map using predefined number of colors so that the neighboring areas are in different colors. Graph vertex coloring problem is a CSP to color the vertices of a graph using predefined number of colors so that the vertices that are connected by an edge are in different colors. Most of the CSPs belong to a class of problems that are called NP-hard problems, for which no efficient method is known. Map or graph coloring problem is one of them. A map can be converted to an equivalent graph, so these two problems can be solved using the same method. A problem of coloring a map on a plane is used as an example because it is suited for demonstration. All plain maps are proved to be colorable using four colors. This is a well known fact.
The program below searches for a solution of the USA mainland map coloring. If you used this program in its initial state, you can track the process by your eye in some extent. If you change the option value, which is ``medium speed (20 rps)'' in its initial state, to ``full speed,'' the computation will be done as quick as possible. (20 rps means that the rule is applied 20 times per second (rps = reductions per second). However, the real rps is less than 20.) You can start the computation again using the ``restart'' button. You probably find a different solution each time and the computation time is also different each time, because random numbers are used.
If you change the option, which is set to ``variable catalyst rule'' initially, then you can change the production rule. The ``single catalyst rule'' sees relatively small number of data (i.e., the rule is local), so the number of reactions (the number of rule applications) becomes larger. On the contrary, The ``variable catalyst rule'' sees relatively large number of data (i.e, the rule is non-local), so the number of reactions becomes smaller. You can find the detailed explanation in reference [1], and it is explained briefly in the computation method page. If the most local rule, the ``no catalyst rule,'' is used, the computation does not terminate. (If this rule is used in combination with the option ``full speed,'' then it will become difficult to stop the computation, so this combination is inhibited.)
To find a solution using non-local rule, a method similar to simulated annealing (SA) is necessary. A method called the frustration accumulation method (FAM), which is similar to SA but only uses local information (reference [1] or [2]) is used in the above program. If you select the option ``frustration OFF,'' then you will find the program fails to find a solution (fails to terminate or terminates without finding a solution) in high probability. (However, the probability to fail is still low in the case of the N queens problem.) If a solution has been found when the computation process terminates, an equation, ``MOD = 1,'' is displayed. If the value is less than 1, then the process has terminated without finding a solution.
If you are interested in the method of coloring using CCM, see
the page of computation method.
(Java programs are also used in the method page for explanation
)
The coordinates of the map in the above program were hand-inputted by Yuzuru Sato, who was a student in the University of Tokyo, in 1992. I thank him.
See the section of references in the home page to see notes.