标签: traveling-salesman

我知道那里有一些不同的旅行推销员项目,我和LKH玩了一下,但我想知道是否有人对任何其他人有任何建议？

我的项目是GPL,所以我需要一些与该许可兼容的东西.

是否有一种算法或一组算法可以让您找到距离任意起始节点最短的步行距离,以便每个节点都能在权重无向图中被访问？这不是旅行推销员,因为我不在乎是否多次访问一个节点.(如果你把它重新开始也没关系 - 只要它是访问所有节点所需的最后一个节点,walker就可以在一些遥远的节点结束.)它不是最小的生成树,因为它可能是A - > B - > C - > A - > D是访问A,B,C和D的(非唯一的)最短路径.我的直觉说这不是'这是一个NP问题,因为它没有限制使NP问题如此棘手.当然,我完全错了.

我阅读了几篇关于如何使用遗传算法和蚁群优化等解决TSP的文章和示例代码.但我发现的所有内容都不包括时间(窗口)约束,例如."我必须在上午12点之前到达客户x"并且假设是对称的.

有人可以指出我的一些示例代码或文章的方向,解释如何向TSP添加约束以及如何在代码中表示这些约束.

谢谢!

我用Python制作了一个用于旅行商问题的模因算法.但是,我遇到的所有测试数据(城市之间的距离列表)缺乏最佳解决方案的信息,所以我不知道我的算法得到的全局最优值有多接近.

有没有人知道在哪里可以找到一些已知的最佳解决方案的tsp测试数据(最好是矩阵形式,但一切都很好)？

我正在尝试为这个问题提出一个合理的算法:

假设你有一堆球.每个球至少有一种颜色,但也可以是多色的.每个球上都有一个数字.还有一堆盒子,每个盒子只有一种颜色.目标是最大化盒子中球的数字总和,唯一的规则是:

• 为了将球放在盒子里,它必须至少在盒子上有颜色
• 你只能在每个盒子里放一个球.

例如,您可以将蓝色和绿色球放入蓝色框或绿色框中,但不能放入红色框中.

我想出了一些在运行时间方面有很大帮助的优化.例如,您可以按点值的降序对球进行排序.然后,当你从最高数字到最低数字,如果球只有一种颜色,并且没有其他高点球包含那种颜色,你可以把它放在那个盒子里(从而从那个盒子中取出那个盒子和那个球)剩下的组合).

我只是好奇是有这种类型的问题的某种动态算法,或者它只是伪装的旅行推销员问题.如果我知道最多有X种颜色会有用吗？任何帮助是极大的赞赏.谢谢!

编辑 - 这是一个简单的例子:

球:

• 1个红球--5分
• 1个蓝球 - 3分
• 1个绿色/红色球 - 2分
• 1个绿色/蓝色球 - 4分
• 1个红色/蓝色球 - 1个点

盒:

• 1红色
• 1蓝色
• 1绿色

最优方案:

• 在红色框中的红球
• 在蓝色框中的蓝色球

• 绿色框中的绿色/蓝色球

  总价值:12分(5 + 3 + 4)

使用谷歌地图/地理位置/路线查找,旅行商问题的实际解决方案是什么？

我不需要最好的解决方案,5%以内就没问题了.

例如,我在英国有20个地点可以按任意顺序访问.这可能需要扩展到数百个位置.

我可以使用哪种算法,因为我可以查找距离(但不想查找数百个距离)？

我正在教自己如何编写涉及TSP的算法(Djikstra,Kruskal),我正在寻找一些启动建议.我正在使用C#和SQL.理想情况下,我希望能够在SQL中严格执行此操作但是我不确定这是否可行(我假设在50个顶点之后运行时会很糟糕).

所以我想问题是,我能做到这只是SQL,如果是这样,最好的方法是什么？如果没有,我必须让C#参与其中最好的方法吗？

编辑3:好的,所以我让我的代码工作,但如果我使用16个节点并且搜索深度大于11,我将面临巨大的内存消耗问题.

一个soemone检查代码并告诉我如何纠正内存泄漏？

这是完整的代码:

public void searchTSP(
    int depth,
    RouterPoint startpoint,
    bool isRound,
    IRouter<RouterPoint> router)
{
  #region TSP_startpointCheck
  if (!routepoints[0].Location.Equals(startpoint.Location))
  {
    int index = Array
      .FindIndex(routepoints, x => x.Location == startpoint.Location);

    if (index != -1 && index != 0) //it's somewhere in the array
    {
      RouterPoint temprp = routepoints[0];
      routepoints[0] = routepoints[index]; //put it to index 0
      routepoints[index] = temprp;
    }
    else //it's not in the array
    {
      //we add it...
      RouterPoint[] ta = new RouterPoint[routepoints.Length + 1];
      routepoints.CopyTo(ta, 0);
      ta[routepoints.Length] …

我在网上看到,人们可以将旅行商问题写成线性表达式,并使用CPLEX for java等软件进行计算.

我有1000个城镇,需要找一小段距离.我计划将这1000个城镇划分为约100个城镇的集群,并在这些单独的集群上执行一些线性规划算法.

我的问题是,我究竟如何将其表示为线性表达式.

所以我有100个城镇,我相信每个人都知道TSP是如何工作的.

我完全不知道如何编写满足TSP的线性约束,目标和变量.

有人可以向我解释这是如何完成的,或者给我一个清楚解释它的链接,因为我一直在研究很多,似乎找不到任何东西.

编辑:

我找到了一些额外的信息:

我们用数字0到n标记城市并定义矩阵:

这会为5个城镇产生以下矩阵吗？

限制是:

i)每个城市都来自其他城市

ii)从每个城市出发前往另一个城市

iii)该路线不会分成不同的岛屿.

同样,这对我来说是完全合理的,但我仍然无法将这些约束写为线性表达式.显然它是一个简单的矩阵.

谢谢你的帮助 !

作为高中毕业论文的一部分,我正在描述旅行推销员问题的启发式方法.我正在阅读这种案例研究(第8页),但我无法理解这些句子的含义:

所描述的NN的运行时间是Θ(N ^ 2).[...]特别是,我们保证NN(I)/ OPT(I)≤(0.5)(log_ {2} N + 1).

那部分对我来说很清楚.但是之后:

然而,没有实质上更好的保证是可能的,因为存在比率增长为Θ(logN)的情况.

有什么实例的含义是什么？

贪心算法也会发生同样的事情:

...但是Greedy最着名的例子只会使比率增长为(logN)/(3 log log N).

那些陈述的含义是什么？它是否与非欧几里德实例有关(我不这么认为,因为你只需要通读距离矩阵的列来解决它)？或者只是具有例如与起始节点相同距离的多个节点的实例,这些节点需要算法来拆分解决方案树或类似的东西？

编辑: 感谢@templatetypedef(您的答案仍将被接受为正确),这一切都是有道理的.但是,我想问一下是否有人知道这些特定图形的任何示例(甚至只是一个链接)(我与哪种算法无关).我不认为它太偏离主题,它宁愿添加对该主题有用的东西.