1
$\begingroup$

I am struggling with the following dynamic programming problem:

Given a complete $N$ vertex digraph and a list of vertices $List$, find a way for two players who start at vertices 1 and 2 respectively to visit each vertex from $List$ (order matters, i.e. $List_{i + 1}$ should be the vertex visited after $List_i$). Some vertices may appear in $List$ more than once (multiset). It is sufficient for a vertex to be visited by only one of players (i.e. one of them can visit all vertices while the other would remain at his starting position) If one player makes a move, the other stands still (can't make moves in parallel). If the current vertex to be visited is $List_i$, players must move to it directly, i.e. take either $(List_{i - 1}, List_i)$ edge (since the previous move guarantees one of player is in $List_{i - 1}$) or $(List_j, List_i)$, for some $j < i$ ($List_j$ is the position other player stopped at during some previous move). This means the path with $L$ vertices in it consists of exactly $L$ edges. The weight/cost of the path should be minimal. Weight of edge $(i, i)$ is always $0$, all weights are non-negative integers, no multi-edges or loops are allowed. Output the cost of such a path.

This is actually a problem from a Russian online judge. The original problem has three players (starting at $1, 2, 3$) in it and also asks to output what player did visit $List_i$, but I reduced the problem for the case of two players which should just make things easier for perception. I think according to the rules I should provide the link for the source problem even if this is a Russian language only website, so here it is http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3379 . If someone really needs it, the stated constraints (that shouldn't matter since we are talking about a simplified version of a problem) for the original problem are $(3 \leq N \leq 200)$ and the number of vertices to be visited is at most $1000$ (I swapped denoting letters), no memory/time limits are given.

The problem has a 2D dynamic programming tag.

My thoughts would be to denote $dp_{i, j}$ as a shortest path that visits vertices from $List_i$ to $List_j$, i.e. $(List_i, List_{i + 1}, ...,List_{j - 1}, List_j)$. The answer is would be stored in $dp_{1, L}$, provided that indexing goes from $1$ and $L$ stands for the length of the $List$. The problem is that I don't have a clear idea how to compute this dp-table. I thought of doing someting like $dp_{i, j} = \min_{k \in i..j}\{ dp_{i,k - 1} + cost(k - 1, List_k) + cost(List_k, k + 1) + dp_{k+1,j}\}$. Naturally, I'd at first compute all paths of length 2, then 3 and so on. The thing is, I don't understand how to deal with the main 'problem' of this problem, determining when the move is made by player 1 or 2. I thought there would probably have to be different costs of paths for different players, but they actually use the same graph, so all that matters is the position player $x$ ended up at. Filling the DP-table would actually have to consider two cases, the one described above which is guaranteed to exist as in path $dp_{i,k - 1}$ we know that one of players ended up in vertex $k - 1$. The case where the other player goes from 'some previous' vertex should be taken into consideration as well, $\min\{ dp_{i,k - 1} + cost(j, List_k) + cost(List_k, k + 1) + dp_{k+1,j}\}$ , where $j$ stands for 'some previous' vertex. While writing this, I also realized that I'd probably need a little hint how to remember the player that visited vertex $List_i$ which is needed for the original problem.

Could you provide me some help please?

$\endgroup$
  • 1
    $\begingroup$ Try thinking of it this way - one table entry should encode all the information about the current state of the game. This includes both how many vertices from $ List $ have been visited and where the players ended up afterwards. With this information you can fill the table by considering all subsequent moves of players. $\endgroup$ – cardobard_box Oct 14 '17 at 17:34
1
$\begingroup$

Here is the naive dynamic programming algorithm, which can probably be improved upon: For every $1 \leq i, j \leq |List|$, compute the minimal weight of a path in which Player 1 is at $List_i$, Player 2 is at $List_j$, and the players have covered all vertices up to $List_{\max(i,j)}$. This should run in $O(|List|^3)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.