0
$\begingroup$

We have a directed graph $G=(V,A)$ with $V=\{1,2,...,n\}$ where for each $(i,j)$ the distance $l(i,j)\in A$ is known. We want to find a pyramidal tour that has minimal length and that includes all points exactly once. A tour is pyramidal if it is of the form: $(n\rightarrow 1 \rightarrow n)$ such that all points in $n\rightarrow 1 $ are decreasing and all points in $1\rightarrow n$ are increasing (example: $(6,5,4,2,1,3,6)$.
I want to find a solution to this problem using Dynamic Programming where $f(i,j)$ is the length of the shortest pyramidal path $(i\rightarrow 1 \rightarrow j)$.
My solution is the following:

$f(i,j)=\begin{Bmatrix} min_{1\leq k<i}(f(k,1)+l(i,k)),\text{when } j=1 \\ min_{1\leq r<j}(f(1,r)+l(r,i)),\text{when } i=1 \\ min_{\begin{matrix} 1\leq k<i \\1\leq r<j,\end{matrix} }(f(k,r)+l(i,k)+l(r,j),\text{when } j>1, i>1 \end{Bmatrix}$

Assuming that $f(1,1)=0$ we find the shortest possible tour by compution $f(n,n)$ is this correct?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Can you provide more details regarding $l$? E.g. is it symmetrical, does it respect the triangle inequality, is it additive, etc. $\endgroup$ – orlp Mar 29 '17 at 15:39
  • $\begingroup$ I have no information about the distance only that it is known $\endgroup$ – Anabella Woud Mar 29 '17 at 16:07
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W.♦ Mar 29 '17 at 17:21
  • $\begingroup$ To check whether your answer is correct, try proving that it is correct. Also useful: implement it, generate a million random test cases, and see if it gives the right answer for each one (by comparing its output to a reference algorithm that is known to be correct -- e.g., one that works by brute force). Have you tried either of those? $\endgroup$ – D.W.♦ Mar 29 '17 at 17:22

Your Answer

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

Browse other questions tagged or ask your own question.