Answers.Body: <p>First we have to specify the problem:</p>
  
  <ol>
  <li><strong>Initial State</strong>: The map all colored randomly.</li>
  <li><strong>Successor Function</strong> (Transition Model): Change the color of a region.</li>
  <li><strong>Goal Test</strong>: The map all colored such that two adjacent regions do not share a color.</li>
  <li><strong>Cost Function</strong>: Assigns 1 to change the color of a region.</li>
  </ol>
  
  <p>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".</p>
  
  <p>As we choose "Hill Climbing" we have to specify one more function (the objective function):</p>
  
  <ol start="5">
  <li><strong>Heuristic Function</strong>: Returns the number of adjacent regions that share the same color.</li>
  </ol>
  
  <p>Now that we have the problem formulated, we apply the "Hill Climbing" algorithm to try to minimize the heuristic function.</p>
  
  <p>As @Philippe Oliver said, you could have several problems using just "Hill Climbing" like:</p>
  
  <ul>
  <li>Local minimums.</li>
  <li>Flat local minimums.</li>
  </ul>
  
  <p><a href="https://i.sstatic.net/FRVYk.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FRVYk.png" alt="From &quot;Artificial Intelligence: A Modern Approach (3rd Edition)&quot;"></a></p>
  
  <p>You can have more information on: <em>Artificial Intelligence: A Modern Approach (3rd Edition) by Stuart Russell and Peter Norvig</em>.</p>
  
  <p>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).</p>
  
  <p>References: </p>
  
  <ul>
  <li><code>Artificial Intelligence: A Modern Approach (3rd Edition) by Stuart Russell and Peter Norvig, chapter 4.1 (Local Search Algorithms and Optimization Problems).</code></li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-22T14:58:21.453Z
Answers.LastActivityDate: 2018-02-22T14:58:21.453Z
Answers.UserDisplayName: brunomaso1
Answers.Body: <p>First of all you need an initial solution. You will then improve this solution with hill climbing.</p>
  
  <p>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).</p>
  
  <p>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.</p>
  
  <p>Note that hill climbing is not perfect and that you may not find a feasible solution in the end.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-02-20T04:21:00.017Z
Answers.LastActivityDate: 2018-02-20T04:21:00.017Z
Answers.UserDisplayName: Philippe Olivier
Body: <p>I have a map. I need to colour it with <span class="math-container">$k$</span> colours, such that two adjacent regions do not share a colour. </p>
  
  <p>How can I formulate the map colouring problem as a hill climbing search problem?</p>
  
Tags: <search><hill-climbing>
Title: How can I formulate the map colouring problem as a hill climbing search problem?
UserDisplayName: jrk
ThreadText: # How can I formulate the map colouring problem as a hill climbing search problem?
  
  (Asked by: username_0 on 2018-02-20)
  
  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?
  
  **Tags:** search, hill-climbing
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2018-02-20. Score: 3 | Accepted answer
  
  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 by username_1 on 2018-02-22. Score: 3
  
  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 @username_2 Oliver said, you could have several problems using just "Hill Climbing" like:
  
  * Local minimums.
  * Flat local minimums.
  
  [![From "Artificial Intelligence: A Modern Approach (3rd Edition)"](https://i.sstatic.net/FRVYk.png)](https://i.sstatic.net/FRVYk.png)
  
  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).`
  
  
  ---
  
  