title: Solving Travelling Salesman with Tabu Search
body: <p>I'm trying to understand the <em>Tabu Search</em> by using it with <em>Hill Climbing algorithm</em>, to solve the <em>travelling salesman problem</em>. </p>
  
  <p>I understand the 'pure' <em>Hill Climbing Algorithm</em>, but how Tabu Search changes this algorithm is not very clear to me.</p>
  
  <p><em><strong>Hill Climbing Demonstration:</em></strong></p>
  
  <p>Let us say, we are given 6 cities <strong>A,B,C,D,E,F</strong>, and we randomly pick an initial state: <strong><em>(A,B,C,D,E,F)</em></strong> with travelling cost of 120.</p>
  
  <p>Then I'm going to select a set of neighboring states (by swapping 1st element with 2nd, 3rd, 4th and so on), and calculate the travelling cost of each:</p>
  
  <pre><code>(B,A,C,D,E,F) = 110   /* &lt;120; mark as optimal */
  (C,B,A,D,E,F) = 127
  (D,B,C,A,E,F) = 145
  (E,B,C,D,A,F) = 102   /* &lt;110; mark as optimal */
  (F,B,C,D,E,A) = 80    /* &lt;102; mark as optimal */
  </code></pre>
  
  <p>Now we have found a local optimum: (F,B,C,D,E,A). </p>
  
  <p><em><strong>How does Tabu Search alter the above algorithm?</em></strong> If you could demonstrate one or two iterations, I would be very much thankful.</p>