title: A Constrained TSP: Find a minimum length tour which starts (and ends) at s and preserves the relative ordering of to sub set cities
body: <p>I am trying to solve a problem with Dynamic Problem. I am familiar with classical TSP, but here it is a constrained TSP where there are two sets of cities and the relative order of the cities has to be preserved. This is the tricky part.</p>
  
  <p>Given,<br>
  A starting city s<br>
  A sequence of n cities A=〈a_1,a_2,…,a_n 〉<br>
  Another sequence of n cities B=〈b_1,b_2,…,b_n 〉<br>
  A distance function D(x,y) which takes any pair of cities and returns the shortest distance between them.<br>
  Technically, we can say that L={s,a_1,a_2,…,a_n,b_1,…,b_n} and that D is a function<br></p>
  
  <p>Objective is to ind a minimum length tour of all 2n+1 cities starting at s (and ending at s) subject to the following constraints:<br>
      The relative order of the cities in A must be preserved.<br>
      And the relative order of cities in B must be preserved.<br>
  In other words:<br>
  For all i:1 ≤ i &lt; n, city a_i must be visited before cities a_(i+1),a_(i+2),…,a_n<br>
  And for all i:1 ≤ i &lt; n, city b_i must be visited before cities b_(i+1),b_(i+2),…,b_n<br></p>
  
  <p>Example:<br>
  A=〈a_1,a_2,a_3 〉<br>
  B=〈b_1,b_2,b_3 〉<br>
  Legal tours (return to s is implied):<br>
  s a_1  a_2  b_1  a_3  b_2  b_3<br>
  s b_1  a_1  a_2  b_2  b_3  a_3<br></p>
  
  <p>An Illegal tour:<br>
  s a_1  b_2  a_2  b_1  a_3  b_3 (b_2 visited before b_1).<br>
  <br></p>
  
  <p>I am having problem finding the subproblem in O(n^2) time. Can anybody please help me.</p>