There are $n$ points on a map, $p_1,..p_n$. There are two officers located initially at $(0,0)$ coordinate. They want to patrol all of these points with a minimum traveling (each officer separately patrol a point). The point $p_i$ must be visited before $p_j$ if $i< j$

I can write a backtracking algorithm to check all possible paths to cover $n$ points by two officers. However, the time complexity of that program is $O(2^n)$.

I wonder if I can write it using a dynamic programming. I can't distinguish the subproblems and common ones.

Source: Assignment of Advanced Algorithms, Fall 2018, Tehran University

  • 2
    $\begingroup$ Your problem looks like very interesting. If it comes from an online programming contest or course, could you please add a URL in the question? If it comes from a book or a paper, a reference. Besides paying proper attribute to the original source, all that information also motivates and helps people answer your question faster and better. $\endgroup$ – Apass.Jack Oct 25 '18 at 10:33
  • 1
    $\begingroup$ @Apass.Jack Thanks, that is a question of an assignment, I didn't find it on the web. I added source. Is it okay now? $\endgroup$ – Ahmad Oct 25 '18 at 10:48
  • $\begingroup$ Note that to calculate the best assignment for points $1, \ldots, i$ with a particular officer visiting point $p_i$, you only need the best assignments for points $1, \ldots, i-1$ with each officer visiting point $p_{i-1}$. $\endgroup$ – Reinstate Monica Oct 25 '18 at 14:06
  • $\begingroup$ I notice you added a source, then edited your question to delete the source. I'm wondering why you did that. $\endgroup$ – D.W. Oct 26 '18 at 19:07
  • $\begingroup$ We get asked a lot about how to use dynamic programming to solve problems, so we have written some generic resources on that: cs.stackexchange.com/tags/dynamic-programming/info. I suggest you study that material, then try to apply the approach listed there to your particular problem, and revise the question to show what progress you've made following that. $\endgroup$ – D.W. Oct 26 '18 at 19:08

Since this question is a part of homework assignment, for which you have demonstrated substantial amount of work and progress (or non-progress), I will give an explicit and strong direction below. See if you can complete the rest.

Dynamic programming is about combining optimal solutions to overlapping subproblems. What are the subproblems here? Let us construct the subproblems as simply as possible but whose solutions are strong enough to deduce the solutions of a large subproblem. In this particular homework assignment, the subproblems can be $t(i,j)$, the minimal traveling distance for one officer to reach point $p_i$ and the other officer reaches point $p_j$. I will let you figure out the following.

  • Suppose you have got the value of $t(i,j)$ for every possible $i$ and $j$. Can you deduce the answer to the original problem easily?
  • Build the hallmark and the most essential content of dynamic programming, the recurrence relation of the wanted quantities of subproblem here, i.e., the recurrence relation of $t(i,j)$. Can you compute the value of $t(i,j)$ at a "larger" subproblem from its values at "smaller" subproblems?

Just in case you didn't know or you forgot, you only need to solve each smaller problem once by recording its answer somewhere when you have computed its answer for the first time. When it is time you need the answer to the same smaller problem again, you will just retrieve it from your records.

Per questioner's request, I am writing the base case and the recurrence relation for $t(i,j)$ as defined above. Let $d(i,j)$ be the distance between $p_i$ and $p_j$. Without loss of generality, we will assume either $0=i=j$ or $i<j$ since once started patrolling, two officers will reach different points.

$$t(i,j) = \begin{cases} 0 &\text { when } 0=i=j \\ t(i,j-1) + d(j-1,j) &\text { when } 0\le i<j-1 \\ \min \{ t(k,j-1) + d(k,j)\mid 0\le k<j-1 \} &\text { when } 0\le i=j-1 \\ \end{cases}$$

How can one find the recurrence relation above? It is sort of like thinking backwards from the ending. Suppose two officers are at $p_i$ and $p_j$ respectively where $i<j$. What happened just before? One of the officers was at $p_{j-1}$ and one of the officers just traveled from some points to $p_j$. There are two cases, which correspond to the recurrence relations above respectively.

  • Those two officers are the same officer. That means the location of the other officer, $p_i$ is different from $p_{j-1}$.
  • Those two officers are different. The officer at $p_{j-1}$ stayed at the same point and the other officer traveled from $p_k$ for some $k\neq j-1$ to $p_j$. That is, the former officer must be at $p_i$, that is, $p_i=p_{j-1}$.

The above base case and recurrence relations can be implemented immediately as a recursive algorithm. Since the recurrence relations here are simple enough, it should be easy to convert the recursive algorithm to an iterative procedure.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Oct 26 '18 at 19:09
  • $\begingroup$ Thank you again for your guides and answer. However, as I checked your solution, it doesn't work (at least the way I implemented it). I myself updated my answer to explain why the formula I reached works. I hope you check my new explanation. $\endgroup$ – Ahmad Oct 29 '18 at 16:16
  • $\begingroup$ My answer should be correct. I believe there is a bug in your implementation of my recurrence relation. Note that $t(i,j)$ is not defined for $i=j$ in my notation. $\endgroup$ – Apass.Jack Nov 20 '18 at 2:09
  • $\begingroup$ Where the optimal answer is stored? in which i and j? $\endgroup$ – Ahmad Nov 20 '18 at 12:49
  • $\begingroup$ To reach point $j$, select the minimum among $t(i,j)$ for all $i$. $\endgroup$ – Apass.Jack Nov 20 '18 at 12:56

Let $m(i,i)$ be the optimal solution when two officers cover $i$ points and one of them is at the point $i$.

Let $m(i,j) \mid 0\le j < i $ be a solution (not optimal) when two officers cover $i$ points and one of them is at the point $i$ and the other officer is at the point $j$. Let $d(i,j)$ be the distance between $p_i$ and $p_j$.

$$m(i,j) = \begin{cases} 0 &\text { when } i=0 \\ m(i-1,j) + d(i-1,i) &\text { when } 0\le j < i \\ \min \{ m(i-1,k) + d(k,i)\mid 0\le k<i \} &\text { when } i = j \\ \end{cases}$$

When $i \neq j$, to have a solution (not optimal) for $m(i,j)$ we just need to have a solution for $m(i-1,j)$ to cover $i-1$ points, and we then move the officer at $i-1$ to the point $i$ to cover this point.

When $i = j$, to have an optimal solution for $i$ points, we look for the minimum cost to reach from a solution with $i -1$ points to an optimal solution with $i$ points by moving an officer from the point $k$ ($0 \leq k < i$) to the point $i$.

  • $\begingroup$ I am rather disappointed that you did not answer my question in the chat. After I have spend so much time and made a correct answer, you accepted your own answer... $\endgroup$ – Apass.Jack Nov 20 '18 at 2:07
  • $\begingroup$ Anyway, I just upvoted your answer. (I had upvoted your question.) $\endgroup$ – Apass.Jack Nov 20 '18 at 3:18
  • $\begingroup$ @Apass.Jack Sorry! I didn't get notified about your message in the chat! Thank you for the up vote! I appreciate your time. I think you shouldn't be worried about these virtual points, the main thing for the answerer is that they help another person and they may learn something new in between. My criteria to vote something up or accept an answer is the validity and usefulness of the answer for the future reader. I may review your answer, but with the formula you presented, I didn't get an answer! Note that I vote your answer up! Do you think my own solution is equivalent to yours? $\endgroup$ – Ahmad Nov 20 '18 at 12:44

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.