问题标签 [traveling-salesman]

I'm trying to calculate all bitonic paths for a given set of points.

Given N points.

My guess is there are O(n!) possible paths.

Reasoning

You have n points you can choose from your starting location. From there you have n-1 points, then n-2 points...which seems to equal n!.

Is this reasoning correct?

我正在开发一个应用程序，在该应用程序中我必须面对旅行推销员问题。我做了自己的尝试，但我得到的时间真的很糟糕。我正在搜索一些优化解决方案，但我没有得到任何明确的信息。

开始优化此过程或算法的任何提示？我目前的算法是基本的回溯算法。

我的图表满足 TSP 图表中的所有典型条件（无方向、等距、圆锥）...

谢谢

我有兴趣解决（小）网格图的 TSP。任何类型的图书馆都可以为我做，但这似乎比预期的要难。我尝试了几个在那里发现的求解器（包括协和式），但是当三角不等式不成立时，它们似乎都有问题。

例如，我希望求解器为下面的图（具有单位边权重）输出游览 (0, 1, 2, 1, 4, 3)：

在这种特殊情况下，我告诉协和边 (2, 4) 的权重为 1000，协和迅速生成成本为 1004 的游览 (0, 1, 2, 4, 3)。这显然不是我想要的。

理想情况下，Java 中会有一些简单的（可能是蛮力的）实现，但任何可行的方法实际上都可以。谁能给我指出一些代码，或者我真的必须自己去实现它吗？

编辑：另外，重要的是我得到一个精确的解决方案，而不是一些近似值。

Edit2：确实，这似乎不是 TSP。我试图找到的是访问所有顶点的最短封闭步行。

我一直在寻找是否可以在没有起点和终点的情况下在谷歌地图上创建路线，只有航点。我正在尝试显示/计算用户必须以正确的经济顺序访问的点的完整路线，但我不知道其中哪一个应该是第一个和最后一个。

谷歌地图是否允许这样的功能，或者我必须随机取两个点并让它们开始和结束？

我正在尝试为旅行商问题（TSP）编写遗传算法。对于选择，我正在实施轮盘赌选择：http ://www.edc.ncl.ac.uk/highlight/rhjanuary2007g02.php/

它基本上意味着选择交配的概率与适应度函数的值成正比。
TSP 最常见的适应度函数是路线的长度。但是，路线“越短”越好。

我如何编写一个描述路径短小的适应度函数？
或者如何将每条路线的真实长度转换为概率？

是否有任何论文讨论如何使用并行动态规划解决旅行推销员问题？

I'm trying to come up with a reasonable algorithm for this problem:

Let's say you have a bunch of balls. Each ball has at least one color, but can also be multicolored. Each ball has a weight and a value associated with it. There are also a bunch of boxes which are each only one color. Each box has a maximum number of balls it can hold. The goal is to maximize the sum of the value in the boxes while staying under some total weight, W, and the only rule is:

In order to place a ball in a box, it has to at least have the box's color on it

(For example, you can put a blue and green ball into a blue box or a green box, but not into a red box.)

I've dome some research and this seems similar to the knapsack problem and also similar to being solvable by the Hungarian algorithm, but I can't quite seem to reduce it to either problem.

I'm just curious is there's some kind of dynamic programming algorithm for this type of problem to make it solvable in polynomial time, or if it's just the traveling salesman problem in disguise. Would it help if I knew there were at most X colors? Any help is greatly appreciated. I could also formalize the problem a bit with variable names if it would help. Thanks!

Here's a simple example:

Maximum weight: 5

Balls:

1 red ball - (value = 5, weight = 1)

1 blue ball - (value = 3, weight = 1)

1 green/red/blue ball - (value = 2, weight = 4)

1 green/blue ball - (value = 4, weight = 1)

1 red/blue ball - (value = 1, weight = 1)

Boxes:

1 red (holds 1 ball)

1 blue (holds 2 balls)

1 green (holds 1 ball)

Optimal Solution:

red ball in red box

blue ball and red/blue ball in blue box

green/blue ball in green box

Total value: 13 (5 + 3 + 1 + 4)

Total weight: 4 (1 + 1 + 1 + 1)

Note: even though the green/red/blue ball was more valuable than the red/blue ball, it's weight would have put us over the limit.

Edit:

One clarifying point: balls with the same color combination will not necessarily have the same weights and values. For example, you could have a red ball with value 3 and weight 1 and another red ball with value 2 and weight 5.

Edit 2:

We can assume integer weights and values if it helps us come up with a dynamic programming algorithm.

BIG版后的问题：

我需要使用遗传算法建立一个排名，我有这样的数据：

现在，让我们解释a,b,c,d为足球队的名称，并且P(x>y)是x获胜的概率y。我们想要建立团队排名，我们缺乏一些观察P(a>d)，P(a>c)由于缺乏 a vs d 和 a vs c 之间的匹配而丢失。目标是找到最能描述这四支球队联赛现状的球队名称排序。

如果我们只有 4 个团队而不是简单的解决方案，首先我们计算4!=24四个团队的所有排序的概率，同时忽略我们拥有的缺失值：

P(abcd)=P(a>b)P(b>c)P(c>d)P(b>d)

P(abdc)=P(a>b)P(b>c)(1-P(c>d))P(b>d)

...

P(dcba)=(1-P(a>b))(1-P(b>c))(1-P(c>d))(1-P(b>d))

我们选择概率最高的排名。我不想使用任何其他健身功能。

我的问题 ：

由于 n 元素的排列数量n!对于大 n （我的 n 约为 40）不可能计算所有排序的概率。我想使用遗传算法来解决这个问题。

变异算子是两个（或更多）排名元素位置的简单切换。

但是如何使两个排序交叉？

可以P(abcd)解释为不对称 TSP 问题中路径“abcd”的成本函数，但从 x 到 y 的旅行成本与从 y 到 x 的旅行成本不同，P(x>y)=1-P(y<x)？TSP问题的交叉算子有很多，但我想我必须设计自己的交叉算子，因为我的问题与TSP略有不同。您对概念分析的解决方案或框架有什么想法吗？

在概念和实现级别上，最简单的方法是使用交叉运算符，它可以在两个解决方案之间交换子排序：

CrossOver(ABcD,AcDB) = AcBD

对于元素的随机子集（在本例中为大写字母的“a，b，d”），我们将第一个子排序 - 元素“a，b，d”的序列复制并粘贴到第二个排序。

版本：不对称 TSP 可以变成对称 TSP，但有禁止的子排序，这使得 GA 方法不适合。

我正在研究一种相当于旅行商问题的路径规划算法。我不知道我可能有多少个节点，所以我愿意牺牲准确性来换取速度。我的问题可以建模为一个完全连接的图，节点之间的转换成本不仅仅与节点之间的距离有关。我想将我的搜索空间限制为位于 delaunay 三角剖分上的连接（我读过的研究指出，TSP 解决方案中 95-100% 的连接位于 delaunay 三角剖分上）但由于我的图表无法表达作为 2D 甚至 3D 几何，我不能直接在我的表示中使用它。

注意：由于旅行不会在它开始的同一个地方结束，而且只要我仍然访问所有点，每个点都可以多次访问，这不是真正的 TSP 变体，而是我之所以这样说是因为缺乏对问题的更好定义。

所以..

假设我要去一次有 n 个兴趣点的徒步旅行。这些点都由远足径相连。我有一张地图，显示所有路径及其距离，给我一个有向图。

我的问题是如何估计从 A 点开始并访问所有 n 个兴趣点的旅行，同时在除我开始的点之外的任何地方结束旅行，并且我希望旅行尽可能短。

由于徒步旅行的性质，我认为这很遗憾不是一个对称问题（或者我可以将我的不对称图转换为对称图吗？），因为从高海拔到低海拔显然比相反的方式更容易。

此外，我相信它必须是一种适用于非度量图的算法，其中不满足三角形不等式，因为从 a 到 b 到 c 可能比走一条从 a 到 c 的漫长而奇怪的道路更快直接地。我确实考虑过三角不等式是否仍然成立，因为对于我访问每个点的次数没有限制，只要我访问所有这些点，这意味着我总是会选择从 a 到 c 的两条不同路径中最短的一条，因此永远不会走上漫长而怪异的道路。

我相信我的问题比 TSP 容易，所以那些算法不适合这个问题。我考虑过使用最小生成树，但我很难说服自己它们可以应用于非度量非对称有向图。

我真正想要的是一些关于如何提出近似算法的指示，该算法将在所有 n 点中找到接近最优的路径