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?
Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.Sign up to join this community
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.
First we have to specify the problem:
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):
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:
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).
Artificial Intelligence: A Modern Approach (3rd Edition) by Stuart Russell and Peter Norvig, chapter 4.1 (Local Search Algorithms and Optimization Problems).