# Algorithm : Visiting all stations in minimum time with additional constraints

I was given this question and not sure how to solve this. This is a DP minimization problem ?

Problem :

There are N stations in a certain region, numbered 1 through N. It takes di,j minutes to travel from Station i to Station j (1 \leq i, j \leq N)\$. Note that di,j=dj,i may not hold.

You are now at Station 1. From here, you have to visit all the stations exactly once. We assume that you have already visited Station 1. However, due to your schedule, there are M restrictions that must be satisfied. The format of each restriction is as follows:

Station si must be visited before Station ti. (1≤i≤M) Find the minimum time required to visit all the stations. Note that the last station to visit can be any of the stations.

Constraints 1≤N≤14 0≤di,j≤108 (1≤i,j≤N) di,i=0 (1≤i≤N) 0≤M≤N(N−1)⁄2 1≤si,ti≤N (1≤i≤M) si≠ti (1≤i≤M) There exists a path visiting all the stations under the given restrictions. Input Input is given from Standard Input in the following format:

N d1,1 … d1,N : dN,1 … dN,N M s1 t1 : sM tM Output Print the minimum time required to visit all the stations.

Sample Input 1
Copy
4
0 2 3 4
1 0 3 4
1 2 0 4
1 2 3 0
3
1 2
2 3
3 4
Sample Output 1
Copy
9
Due to the restrictions, we can only travel as follows: Station 1 → Station 2 → Station 3 → Station 4.
Thus, the answer is 2+3+4=9 and we should print 9.

Sample Input 2
Copy
3
0 1 20
1 0 20
10 20 0
0
Sample Output 2
Copy
21
Sample Input 3
Copy
1
0
0
Sample Output 3
Copy
0
Sample Input 4
Copy
14
0 28448202 94752369 6965437 42744902 7560126 75090662 8843627 69061140 64249326 57690728 42986477 48404113 88716403
73013281 0 37847212 34428188 25009906 3614271 82144791 23149022 94211619 56083883 547750 35036479 37794350 85146222
6400137 79121726 0 32137663 86550075 54343753 78531432 1169605 56872598 61793842 30013621 61824448 76242267 78181546
44000464 19945953 92672933 0 8488951 29783495 42361540 61448706 5092013 39670396 92639393 26910058 56878215 83406982
42411559 55713387 40842605 80915875 0 90870302 16746891 41698332 92400406 79586785 76734482 54938846 14817854 44262797
25618079 82961670 3220380 37882710 77238264 0 30285694 94010597 3313434 25248938 6148456 57383107 80041226 52974537
45702192 36993407 35034648 13099849 97787850 79254364 0 44172314 73023554 53984059 83657376 26813141 8449228 85695371
89466424 82640627 2816597 1216033 21988152 90828105 83428522 0 216303 46837120 30499660 38938821 68789759 30497390
14240720 49216529 36512207 64082795 92391305 70382708 28258331 4979511 0 884770 66017741 51457552 4005017 50751247
15122265 49804986 83078215 87707425 56873145 88791801 34219986 77073154 82798626 0 7386614 49058658 3482690 55300190
96344094 77929649 15796809 35347942 46688706 15359332 64653788 87407203 42689175 98416950 0 83290181 47967318 90377000
27375431 9920337 23971212 20418378 68812572 23746130 78728346 72070698 1939257 87280009 11983259 0 37799770 16442015
85303335 55565703 5694284 91866847 29725710 98189375 17777160 81031919 59126600 83771749 67762666 68788386 0 75480673
54861272 25070911 78287445 76137950 81268769 83585267 49252003 71439588 98965870 54719898 78225858 25335948 85354514 0
7
12 7
1 7
8 5
11 3
14 6
4 13
8 9


Update: Cannot find the reference to the original problem but assumes this is from AtCoder.

• Please add a reference to the original problem in the question. Why is it important? 1) Credit should be attributed. 2) A reference is apt to motivate people. 3) A reference may save readers who look for related materials lots of time. 4) This reason is skipped for the moment. – Apass.Jack Jan 29 at 1:58
• @Apass.Jack sorry, I cant find the original problem since this was given to me by a work colleague. he assumed its from AtCoder. – Aishak Jan 29 at 2:03
• Unfortunately, atcoder.com does not enable users to search for problems. (Or just unregistered users?). So I could not verify whether this problem comes from atcoder.com or not. I just checked it does not belong to an ongoing contest on atcoder.com. – Apass.Jack Jan 29 at 10:00
• Please use a more descriptive title; this one fits on any number of questions. – Raphael Jan 29 at 17:59
• What have you tried and where did you get stuck? This is not a problem-solving platform. – Raphael Jan 29 at 17:59

## 1 Answer

Considering the "you have to visit all stations minimizing time", this is a Travelling salesman problem (see https://en.wikipedia.org/wiki/Travelling_salesman_problem).

The additional constraints on sequencing correspond to scheduler optimization.

I think the full problem is called "Sequential Ordering Problem". It is NP complete as both of its components. To answer your question, I think dynamic programming is not adapted to this type of problem. Indeed dynamic problem allows to decide recursively multiple choices like "yes" or "no". For instance have a look at the Knapsack problem (https://en.wikipedia.org/wiki/Knapsack_problem) which can be nicely solved with DP.

EDIT (credit to j_random_hacker for this solution): In fact the Held-Karp algorithm (https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm) is a DP solution for TSP problems. It builds iteratively optimal subsequences for all subsets testing all combinations. Among these combinations, just do not consider the ones that do not respect precedence constrains.

For N stations, it has a $$O(2^N N^2)$$ cost instead of the brute force solution having $$O(N!)$$. This at the price of a significant space cost $$O(2^N N)$$. Every independant precedence constrain reduces by a factor 2 the number of combinations to evaluate.

• It looks like asymmetric TSP with some extra constraints to me too, but TSP (and possibly this problem too) can be solved using DP on sets of visited vertices: en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm. The algorithm is exponential-time in the number of vertices, but this is still better than factorial time, which is needed by the usual recursive enumeration algorithm. (Mind you its space complexity is much worse, and that's often the limiting factor.) – j_random_hacker Jan 29 at 10:29
• Quite interesting indeed. I will have a deeper look to it and possibly edit my answer, thanks. – Vince Jan 29 at 12:38
• You're welcome :) – j_random_hacker Jan 29 at 14:43