哪种方法在TSP问题中产生较短的旅程:最近邻居或遗传算法？
最近邻居法（KNN）和遗传算法（GA）都可以用于解决TSP问题，但它们在产生较短旅程方面具有不同的优缺点。
最近邻居法（KNN）是一种基于实例的学习方法，它通过计算待预测点与已知数据点之间的距离，找出距离最近的K个邻居，并根据这些邻居的标签值来预测待预测点的类别。KNN算法在处理TSP问题时，可以快速地找到距离最近的邻居，但需要大量的计算资源和存储空间，并且对于邻居数量K的选择、距离度量方法等因素的选择都会对算法的效果产生影。
相关·内容
在过去的几天里，我注意到一些 演示了使用遗传算法的TS解决方案。
在TSP问题中，哪种方法会产生较短的行程:最近邻法还是遗传算法？
浏览 1提问于2008-12-10得票数 4
回答已采纳
1回答
我正在使用R中的TSP包处理一个旅行推销员问题，但试图达到预定的起点和终点。想知道有没有人知道设置终点的方法。我知道TSP本质上是开放的，因此预设端点可能是不可能的。在这种情况下，我对另一种产生类似结果的最近邻方法持开放态度(通过设置起点和终点的多变
浏览 0提问于2016-03-18得票数 5
3回答
我正在做一项小型学术作业，用遗传算法(GA)解决旅行推销员问题(TSP)。对于气体的基本知识，我有点搞不懂你会遵循什么样的方法将不同类型的突变应用于TSP。假设我们的路由被表示为路由，变异率用变量m_rate表示。只要没有遇到数组的末尾，我就会继续将相同的内容应用于其余的每一个城市或索引。这方法正确吗？一旦应用了第一个突变，我应该停止还是退出循环
浏览 8提问于2012-09-13得票数 2
4回答
我正在尝试解决遗传算法在我的排列上的交叉问题。假设我有两个20个整数的排列。我想把它们交叉以得到两个孩子。双亲内部有相同的整数，但顺序不同。134 12 750 42 113 530 112 5 23415 60 152 601 999 442 221 50 30 969 134 21
就这样吧-我怎么才能得到这两个人的孩子呢
浏览 3提问于2013-01-20得票数 12
回答已采纳
我需要帮助定义旅行推销员问题的变异运算符。random_interval ( min_gene_index, max_gene_index );因此，当交换被执行时，路线上的两个城市被交换我不想让它成为主循环中的一次表演。我是否可以改进我的实现，或者是否还有其他更好的选择？
浏览 0提问于2015-03-06得票数 4
回答已采纳
2回答
如果用动态规划方法求解旅行商问题，它能给出比贪婪方法更好的可行解吗？
我知道，在最优解方面，贪婪算法被用来求解TSP，但是当顶点数(即城市)非常大时，它变得更加复杂，并且需要指数时间。那么，到底哪种方法会更好呢？
浏览 2提问于2019-02-05得票数 1
给定一个具有n个顶点的加权无向图，我面临着找到一条连接直线上每个顶点的权重最小的路径的问题。起初，我认为这是寻找最小生成树的问题，但事实并非如此。在生成树的情况下，在一个顶点上可能有分支，或者度数可能大于2。我需要找到的是一条线性路径，即除了末端顶点之外的所有顶点的阶数恰好为2。起始顶点和结束顶点可以是n个顶点中的任何一个。我的是贪婪的<
浏览 0提问于2012-02-01得票数 3
3回答
我正在使用遗传算法(GA)来优化旅行商问题(TSP)。我的问题是如何计算一个人的适合度。显然，具有较短路径的解决方案更合适，但在不知道最短可能路径和最长可能路径是什么的情况下，我如何准确地分配适合度值，以确定我的解决方案在该范围内的位置？
浏览 2提问于2012-08-01得票数 4
回答已采纳
我很确定我的问题肯定已经被调查过了，但我缺少帮助我搜索文献的行话。我正在写一个遗传算法来解决一类旅行商问题(TSP)。像标准的TSP一样，我的变体没有方向的概念。在标准的TSP中，由于需要形成一条返回起始城市的线路，因此对于任何最优解，都应该有两条相等的最优路线，即该线路周围的两条相反
浏览 0提问于2015-12-15得票数 1
2回答
我必须在kd-tree中实现对10维数据的k近邻搜索。
但问题是，我的算法在k=1上非常快，但在k>1 (k=2,5,10,20,100)上却慢了2000倍。这对于kd树来说是正常的吗，还是我做了一些错误的事情？
浏览 0提问于2010-01-10得票数 9
回答已采纳
3回答
我需要一个算法，让机器人探索一个有障碍物的n*n网格(如果你愿意，可以是一个迷宫)。目标是探索所有没有障碍物的方块，并避开有障碍物的方块。诀窍在于，障碍物迫使机器人改变其路径，导致它错过了障碍物后面可能出现的自由方块。我可以懒惰地递增/递减机器人的x/y坐标，使机器人在没有障碍物的情况下沿四个方向中的任何一个方向移动，并且机器人可以穿过预先看到的路径(如果需要)，以便到达其他自由方块。当所有空闲的
浏览 1提问于2012-07-19得票数 0
回答已采纳
1回答
扩展对象/特征像素区域
、、、
在初始分割(基于阈值)之后，通常使用哪种方法来评估剩余的“边界”像素？
我考虑了基于标准偏离阈值的分类，但我不知道这是否是图像分析中常见的做法。这是一种区域增长方法，但是基于这个问题的答案( )，使用区域增长算法是不明智的。有人建议imdilate。这种方法似乎是任意的，在增强图像以达到审美目的或提高可见度时是有用的。对于我<
浏览 3提问于2016-01-24得票数 0
这个问题已经被以类似的方式问了几次，但我找到的现有答案中没有一个对我有实际帮助。对于我必须解决的特定问题，我需要一个非常快速的解决方案。据我所知，我的问题与所有对最短路径问题</em
浏览 0提问于2013-11-26得票数 2
我正在学习模拟退火算法，并且有一些关于如何修改示例算法来解决0-1背包问题的问题。我在CP上找到了这个很棒的代码：
我非常确定我现在理解了这一切是如何工作的(除了整个Bolzman条件，就我而言是黑魔法，尽管我理解如何逃脱局部最优，显然这就是它的作用)。我想重新设计这个来解决一个0-1背包问题。基本上，我将5000个对象中的一个放入10个麻袋中，并需要优化以获得最少的未使用空间。
浏览 0提问于2010-08-02得票数 4
回答已采纳
我们有一个开源的C++/Qt应用程序，我们最近也开始打包和分发为一个快照(管理工艺)。这是一次颠簸的旅程。在许多其他问题中，一些用户在从snap运行应用程序时(包括在启动期间)报告了崩溃(SIGSEGV)，但是我们不知道如何在这些情况下产生合理的回溯。如果可能，我们希望避免添加代码或库，以便在快照中打印回退跟踪。
如何使用GDB?运行和调试snap应用程序
浏览 0提问于2020-06-20得票数 0
回答已采纳
2回答
我想找到一种启发式或算法来解决类似旅行销售人员的问题，但有一些关键的区别：-I希望至少遍历每个顶点一次，而不是一次。-There是图中的死胡同，我们必须从图中回溯。这张图应该是这样的：目前，我正在沿着一条随机的路线前进，将我的历史保存在一个堆栈中，直到到达一个没有连接到任何未旅行的顶点
浏览 5提问于2014-05-28得票数 0
回答已采纳
3回答
求解多背包问题的改进遗传算法
、、、、
最近，我一直在改进传统的遗传算法来解决多背包问题。因此，我改进的遗传算法比传统的遗传算法工作得更好。我测试过了。(我使用了OR-Library ()的公开可用来测试气体。)有谁知道其他改进的遗传算法。我想与其他改进的遗传算法进行比较。实际上我在网上搜索过了。但是找不到比较好的算法。
浏览 2提问于2010-06-02得票数 1
事实上，我们曾提出过这个问题，但据我所知，并没有提供适当的答案。
我了解如何实现k-d树，以及最近邻搜索的工作原理。然而，即使在环顾四周之后，我也找不到一种有效的方法来使用k树来非常有效地搜索k个最近的邻居。我只能想到找到最近的邻居并删除它，并再次重复这个过程k-1次，然后将所有删除的节点插入到树中。但这似乎是多余的</
浏览 1提问于2016-04-13得票数 4
回答已采纳
请随意重新命名这个问题..。我有一个数字'n‘自动吸尘器在地板上有一个数字'k’的污点。为了以最有效的方式清洁地板，把吸尘器分配到脏点的最佳方法是什么？详细信息：
记
浏览 4提问于2011-10-28得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
