title: How to compute optimal paths for traveling salesman bitonic tour?
body: <p><strong>UPDATED</strong></p>
  
  <p>After more reading, the solution can be given with the following recurrence relation:</p>
  
  <pre><code>(a) When i = 1 and j = 2, l(i; j) = dist(pi; pj )
  (b) When i &lt; j - 1; l(i; j) = l(i; j - 1) + dist(pj-1; pj)
  (c) When i = j - 1 and j &gt; 2, min 1&lt;=k&lt;i (l(k; i) + dist(pk; pj ))
  </code></pre>
  
  <p>This is now starting to make sense, except for part C. How would I go about determining the minimum value k? I suppose it means you can iterate through all possible k values and just store the minimum result of ( l(k,i) + dist(pk,pj)?</p>
  
  <hr>
  
  <p>Yes, definitely a problem I was studying at school. We are studying bitonic tours for the traveling salesman problem.</p>
  
  <p>Anyway, say I have 5 vertices {0,1,2,3,4}. I know my first step is to sort these in order of increasing x-coordinates. From there, I am a bit confused on how this would be done with dynamic programming.</p>
  
  <p>I am reading that I should scan the list of sorted nodes, and maintain optimal paths for both parts (initial path and the return path). I am confused as to how I will calculate these optimal paths. For instance, how will I know if I should include a given node in the initial path or the return path, since it cannot be in both (except for the endpoints). Thinking back to Fibonacci in dynamic programming, you basically start with your base case and work your way forward. I guess what I am asking is how would I get started with the bitonic traveling salesman problem?</p>
  
  <p>For something like the Fibonacci numbers, a dynamic programming approached is quite clear. However, I don't know if I am just being dense or what but I am quite confused trying to wrap my head around this problem.</p>
  
  <p>Thanks for looking!</p>
  
  <p>NOTE: I am not looking for complete solutions, but at least some good tips to get my started. For example, if this were the Fibonacci problem, one could illustrate how the first few numbers are calculated. Please let me know how I can improve the question as well.</p>