How can I formulate the map colouring problem as a hill climbing search problem?

Question

I have a map. I need to colour it with $k$ colours, such that two adjacent regions do not share a colour.

How can I formulate the map colouring problem as a hill climbing search problem?

Answer 1

First of all you need an initial solution. You will then improve this solution with hill climbing.

For your initial solution, you can color the map randomly using the K colors. This will most likely result in conflicts (adjacent regions of the same color).

Then the hill climbing part: Find a region which has conflicts and swap its color for another color, making sure that the new color does not incur more conflicts than the old one. With each iteration your solution should slowly improve.

Note that hill climbing is not perfect and that you may not find a feasible solution in the end.

Answer 2

First we have to specify the problem:

1. Initial State: The map all colored randomly.
2. Successor Function (Transition Model): Change the color of a region.
3. Goal Test: The map all colored such that two adjacent regions do not share a color.
4. Cost Function: Assigns 1 to change the color of a region.

Now that we have the specification of the problem, we have to choose the search algorithm to solve the problem. In this case "Hill Climbing".

As we choose "Hill Climbing" we have to specify one more function (the objective function):

5. Heuristic Function: Returns the number of adjacent regions that share the same color.

Now that we have the problem formulated, we apply the "Hill Climbing" algorithm to try to minimize the heuristic function.

As @Philippe Oliver said, you could have several problems using just "Hill Climbing" like:

• Local minimums.
• Flat local minimums.

You can have more information on: Artificial Intelligence: A Modern Approach (3rd Edition) by Stuart Russell and Peter Norvig.

You can have several approaches to this problem, I show you just one. Another can be specifying the problem incrementally (change the "Initial State" for a map with no regions colored, and then the "Successors" are specified by painting a region in a way that two adjacent regions do not share a color).

References:

• Artificial Intelligence: A Modern Approach (3rd Edition) by Stuart Russell and Peter Norvig, chapter 4.1 (Local Search Algorithms and Optimization Problems).