Answers.Body: <p>I will give you a basic idea of an approach.</p>
  
  <p>The basic idea behind hill climbing algorithms is to find local neighbouring solutions to the current one and, eventually, replace the current one with one of these neighbouring solutions.</p>
  
  <p>So, you first need to model your problem in a way such that you can find neighbouring solutions to the current solution (as efficiently as possible). But what is a solution to a <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">TSP</a>? It is a sequence of nodes (or vertices), such that the first node is equal to the last one (given that the travelling salesman needs to return to its initial position), no other vertex is repeated, and all vertices of the graph are included. </p>
  
  <p>So, given a sequence of nodes <span class="math-container">$x_1, x_2, \dots, x_{n}, x_1$</span>, how can you create a neighbouring solution that is valid, that is, there is not repeated vertex (apart from the initial and the last one) and all vertices are included? </p>
  
  <p>Hint: recall that, in the case of TSP, we can assume that every node (or city) is connected to every other node.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-29T15:28:17.930Z
Answers.LastActivityDate: 2019-03-29T15:33:52.450Z
Answers.LastEditDate: 2019-03-29T15:33:52.450Z
Answers.UserDisplayName: nbro
Body: <p>How could we solve the TSP using a hill-climbing approach?</p>
  
Tags: <applications><optimization><search><hill-climbing><travelling-salesman-problem>
Title: How could we solve the TSP using a hill-climbing approach?
UserDisplayName: dua fatima
ThreadText: # How could we solve the TSP using a hill-climbing approach?
  
  (Asked by: username_0 on 2019-03-29)
  
  How could we solve the TSP using a hill-climbing approach?
  
  **Tags:** applications, optimization, search, hill-climbing, travelling-salesman-problem
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-03-29. Score: 1 | Accepted answer
  
  I will give you a basic idea of an approach.
  
  The basic idea behind hill climbing algorithms is to find local neighbouring solutions to the current one and, eventually, replace the current one with one of these neighbouring solutions.
  
  So, you first need to model your problem in a way such that you can find neighbouring solutions to the current solution (as efficiently as possible). But what is a solution to a [TSP](https://en.wikipedia.org/wiki/Travelling_salesman_problem)? It is a sequence of nodes (or vertices), such that the first node is equal to the last one (given that the travelling salesman needs to return to its initial position), no other vertex is repeated, and all vertices of the graph are included.
  
  So, given a sequence of nodes $x\_1, x\_2, \dots, x\_{n}, x\_1$, how can you create a neighbouring solution that is valid, that is, there is not repeated vertex (apart from the initial and the last one) and all vertices are included?
  
  Hint: recall that, in the case of TSP, we can assume that every node (or city) is connected to every other node.
  
  
  ---
  
  