小编Pav*_*vel的帖子

我想在 Python 中使用动态编程算法解决 TSP 问题。问题是：

• 输入：表示为点列表的城市。例如，[(1,2), (0.3, 4.5), (9, 3)...]。城市之间的距离定义为欧几里得距离。
• 输出：此实例的旅行推销员旅行的最低成本，四舍五入到最接近的整数。

伪代码是：

Let A = 2-D array, indexed by subsets of {1, 2, ,3, ..., n} that contains 1 and destinations j belongs to {1, 2, 3,...n}
1. Base case:
2.          if S = {0}, then A[S, 1] = 0;
3.          else, A[S, 1] = Infinity.
4.for m = 2, 3, ..., n:   // m = subproblem size
5.    for each subset of {1, 2,...,n} of size m that contains …