旅行推销员问题，使用动态编程？ [英] travelling salesman problem, using dynamic programming?

问题描述

这是使用动态编程的TSP的pseucode，我的问题是我不知道如何实现D [n] [v - {v1}的子集]，或者我不知道如何实现循环真实代码：

Here is the pseucode for TSP using dynamic programming, my problem is i don't know how to implement D[n][subset of v - {v1}], or i don't know how to implement the loops in real code:

void travel (int n,
            const number W [] [],
            index P [] [],
            number & minlength)
{
   index i, j, k;
   number D [1 .. n] [subset of V - {v1}];

   for (i = 2; i <= n; i++)
          D [i] [⊘] = W[i] [1];

   for (k = 1; k <= n - 2; k++)
      for (all subsets A ⊆ V - {v1} containing k vertices)
           for (i such that i ≠ 1 and vi is not in A)
           {
               D [i] [A] = minimum (W [i] [j] + D [j] [A - {vj}]);
               j: [vj ∊ A
               P[i] [A] = value of j that gave the minimum;
          }
     D [1] [V - {v1}] = minimum (W[1] [j] + D[j] [V - {v1, vj}]);
     2 ≤ j ≤ n
     P[1] [V - {v1}] = value of j that gave the minimum;
     minlength = D[1] [V - {v1}];
}

推荐答案

如果您不知道如何制作循环，则意味着您对编程没有任何意义。反过来，即使提问也不会使你不合格。为什么？因为任何人都可以在手册中阅读如何在C ++中编写循环。你甚至都没试过。如果你不这样做，那么你可以从答案中学习如何做到这一点令人怀疑。但是谁想浪费时间？



所以，请坐下来学习这个主题，至少可以提出合格的问题。



http://www.cplusplus.com/doc/tutorial/control [ ^ ]，

http://www.cplusplus.com/forum/beginner/120231 [ ^ ]。



等等on ...



很抱歉没有为您编写代码示例;我故意这样做：真正帮助你学习东西。回答你的这些问题往往是学习的有效障碍;我不想要它。

-SA

If you don't know how to make loops, it means that you no nothing about programming. In turn, it makes you not qualified even for asking questions. Why? Because anyone can read in a manual how to program loops in C++. You did not even try. If you did not do that, it makes doubtful that you can learn how to do it from the answer. But who wants to waste time?

So, please sit down and learn the subject at least to the point where you can ask qualified questions.

http://www.cplusplus.com/doc/tutorial/control[^],
http://www.cplusplus.com/forum/beginner/120231[^].

And so on…

Sorry for not writing a code sample for you; I did it on purpose: to really help you to learn things. Answering such "questions" as yours is often works as an effective block for learning; I don't want it.

—SA

这篇关于旅行推销员问题，使用动态编程？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！