如何使用协和求解TSP？
协和求解TSP（Traveling Salesman Problem）是一种解决旅行商问题的方法。旅行商问题是指在给定一系列城市和每对城市之间的距离的情况下，找到一条最短路径，使得旅行商可以从一个城市出发，经过每个城市恰好一次，最后回到出发城市。
协和求解TSP是一种基于协同优化的方法，它通过将问题分解为多个子问题，并通过协同合作来求解整个问题。具体步骤如下：
- 初始化：随机生成一组初始解，即一条路径，可以使用贪心算法或随机算法生成。
- 子问题划分：将初始解划分为多个子问题，每个子问题包含一部分城市。
- 子问题求解：对每个子问题应用一种求解TSP的算法，例如动态规划、遗传算法、模拟退火算法等，以求得每个子问题的最优解。
- 协同合作：将每个子问题的最优解进行合并，形成一个新的解，并更新当前的最优解。
- 终止条件判断：判断是否满足终止条件，例如达到最大迭代次数或找到了更优的解。
- 迭代优化：如果不满足终止条件，回到第2步，继续划分子问题并求解，直到满足终止条件为止。
协和求解TSP的优势在于能够通过协同合作来寻找全局最优解，避免陷入局部最优解。它可以通过并行计算来加速求解过程，并且具有较好的可扩展性。
协和求解TSP在实际应用中可以用于优化旅行路线规划、物流配送、芯片布线等问题。在腾讯云中，可以使用腾讯云的弹性MapReduce服务（EMR）来进行并行计算和分布式处理，以加速协和求解TSP的过程。
更多关于协和求解TSP的信息和腾讯云相关产品介绍，请参考以下链接：
相关·内容
1回答
我需要得到TSP的精确解(不是启发式的)，所以我想用协和程序来解决TSP问题，但我不能介绍数据。协和接口只允许我引入随机节点并解决这个问题，但我想给它我的数据。我尝试创建了一个具有以下结构的.txt：node1 node2 dist12(etc)45.601403, 8.878341
浏览 13提问于2017-12-28得票数 3
回答已采纳
3回答
协和式飞机的困境
、、、
协和TSP求解器可以解决欧几里德旅行推销员问题的实例，精确且比人们预期的要快得多。例如，协和飞机能够精确地解决85,900点实例问题，其部分如下所示：然而，有些TSP实例花费的时间太长，即使对协和式飞机也是如此。例如，没有人能够解决这个基于蒙娜丽莎的10万点实例。协和是可供下载作为源代码或可执行文件。默认情况下，它使用内置的线性规划( LP )求解器QSopt，但也可以使用更好的LP求解器(如
浏览 0提问于2019-02-01得票数 17
2回答
该算法在需要的时候向问题添加子回路约束，并用新的约束再次求解问题。这是一个迭代的过程。我只想知道这是不是处理大型TSP实例的最快方法？有没有人对最快的TSP解决方法有什么建议？
谢谢。
浏览 1提问于2014-08-27得票数 0
1回答
不含三角形不等式的TSP求解器
、、、、
我对解决(小)网格图的TSP很感兴趣。任何类型的库都可以，但这似乎比预期的要难。我尝试了几个我在那里找到的求解器(包括协和)，但当三角形不等式不成立时，它们似乎都有问题。例如，我希望求解器为下面的图(具有单位边权重)输出巡视图(0，1，2，1，4，3)：| |在这个特殊的例子中，我告诉协和，边(2，4)的权重为1000，协和立即产生了代价为1004Edit2:事实上，这似乎不是TSP。我要找的是访问所有顶点的最短封闭走法。
浏览 1提问于2012-02-28得票数 1
回答已采纳
3回答
多路径旅行商优化
、、
我试图用不完全图来求解多路径旅行推销员的变型.更确切地说：
我正计划用协和/复印机来解决这个问题。我看到了许多类似的TSP和多TSP的解决方案，但都不符合我的要求。
我的问题:我应该如何<
浏览 1提问于2019-10-10得票数 0
我试图用协和来解决TSP的一些不对称的例子。虽然官方网站说协和确实解决了这种情况，但我看到有人说没有(，)。EDGE_WEIGHT_SECTION 2 |999| 2 | 2 2 | 2 | 2 |999 协和式飞机给了我不管我在第一行放了多少数字，协和号都不会选择第三个城市(指数2，数值3)。-编辑--
事实上，ATSP问题的例子并不来自官方网站。我不确
浏览 1提问于2015-10-07得票数 2
回答已采纳
这是对基本TSP的修改，使得所有节点都具有颜色属性，并且最优路径不能连续接触相同颜色的四个以上的节点。这将在不超过100个节点的连接图中运行。我正在尝试使用协和来运行它。有人知道如何将颜色约束添加到协和运行中吗？
谢谢
浏览 3提问于2015-04-29得票数 0
1回答
如何构建和运行协和TSP求解器
、、、、
我正在用C++编写一个代码，它应该使用一个名为Concorde的库来解决一个众所周知的问题，即旅行商问题。此库可从获得
我首先运行.通过这种方式，concorde被配置为运行并使用IBM Cplex作为确切的求解器。我使用Code::Blocks作为集成开发环境，在构建选项中，我在Link libraries下添加了库(concorde.a)，并在代码中包含了头文件。但是，当我尝试编译我的代码时，它给出了一个错误，指示它找不到我调用的、在concorde.h文件中定义的协和函数的实现。
浏览 0提问于2013-12-13得票数 0
1回答
尝试使用TSP包接口来使用协和算法来解决著名的TSP问题会导致状态127。我将协和可执行文件的路径放在concorde_path()中。在运行solve_TSP函数时，会遇到以下错误solve_TSP(USCA312, method = "concorde", control = list(clo =-Vexe = C:/Use
浏览 2提问于2017-12-07得票数 0
2回答
TSP最优巡游
、、、
我写了一个细菌进化算法来解决TSP问题。我选择XQF131实例()来测试我的算法。这个问题是用协和算法解决的，最优路径是564。但我计算了显示的最优线路长度，它是567,2029。()使用我的算法，我找到了更好的解决方案566,4142。我的问题是:协和算法是如何工作的?它计算最优解或近似值？
谢谢你的回答！
浏览 2提问于2015-04-28得票数 4
1回答
我一直在尝试在Cygwin上安装Concorde的TSP求解器，但我遇到了一些困难:我在官方网站上下载了Qsopt，"Cygwin“部分中的两个文件，并将它们放在/home/qs中。然后，我下载了协和文件，对其进行了压缩和压缩，得到了/home/协和文件。我进入这个文件夹并输入"./configure --with-qsopt=/home/qs“。(我用的是automake 1.15)gcc -fPIC -
浏览 5提问于2018-01-16得票数 0
2回答
将路点添加到A*图搜索
、、、、
我能够使用A*计算起点和终点之间的最佳路线。现在，我正在通过将A*应用于我的点的所有排列中的对来包括我的起点和终点之间的路点。我想从点1到点4。另外，我想通过点2和3。
浏览 5提问于2010-06-19得票数 5
我知道在整数优化问题中，我们可以使用差分求解器(cp-sat-cp).In routing problem (tsp或其他)如何使用差分求解问题。我发现这个函数(SolveModelWithSat)也许可以通过ortools文档使用不同的求解器，但我不知道如何使用它。
浏览 35提问于2020-09-30得票数 1
回答已采纳
2回答
我已经安装了TSP包并且可以正常工作。我从协和(TSP/Waterloo)网站下载了所有文件。我尝试了不同的版本。甚至解压了所有的文件。在Windows下运行R/Rstudio
感谢
浏览 2提问于2018-07-18得票数 2
我需要在我的rails应用程序中解决tsp问题。我想用google或者-tools来解决这个tsp问题。文档讲述了如何在c++、c#、java和python中使用or-tools。在python中使用or-tools求解tsp的代码运行良好。但是我需要在我的rails应用中使用ruby中的or-tools。我该怎么做呢？
浏览 0提问于2018-05-03得票数 0
我试图使用以下格式在文件中使用concorde TSP解决程序：COMMENT : NadaDIMENSION : 20concorde myFile.tsp209 17
浏览 2提问于2014-12-04得票数 1
回答已采纳
我正在使用谷歌的来寻找旅行推销员问题的解决方案。当我在一组点上运行程序时，所有东西都按预期工作。gflags.DEFINE_integer('tsp_size', len(points), 'Size of Traveling同样，当只指定一个集合时，它也能工作，但是在运行第二个集合时，我会得到错误：gflags.Dup
浏览 0提问于2015-06-28得票数 1
我试图解决一个经典的旅行推销员问题(TSP)。我使用的是默认TSP包装程序代码。我希望禁止一些弧，因为在节点10和节点12之间可能没有路径。在这种情况下，我将值设置为一个很大的数字，比如10^6，但求解器仍然使用该弧线。我验证了这个特定的例子有一个可行的解决方案，也就是说，当我两次运行相同的代码或者将求解器的时间从30到60的时候，求解者找到了一个不使用这个弧线的解决方案。我的问题是:是否有一种方法可以指定无法使用的硬约束，而不是将弧
浏览 7提问于2022-03-08得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
