我已经读到图中是否存在的问题是NP-完全的，而且由于在多项式时间内运行，所以不能修改它以求最短的哈密顿路径。(这逻辑有效吗？)考虑到这些规范，现在是否有可能修改Dijkstra的算法，以A和Z为端点寻找最短哈密顿路径？(多项式时间)
注意:我只关心从两个节点找到最短哈密顿路径。但有另一种算法可以用来解决这个问题，它是什么算法，它的时间复杂度是多少？(注:这个问题有“哈密顿循环”作为标签，即使我在寻找哈密顿</
浏览 16提问于2014-06-25得票数 2
回答已采纳
我想知道TSP的问题名称是什么，考虑到回到起点的方式，以及解决这个问题的算法是什么。我也研究了哈密顿路径问题，但似乎没有解决我定义的问题，而是发现是否存在哈密顿路径。
浏览 1提问于2011-07-18得票数 41
回答已采纳
1回答
我有一个很大的加权图，我想计算一条近似的最短哈密顿路径，它以最低的代价通过所有节点。我的图表真的很大，它不适合我的记忆。因此，我决定随机忽略一些边，并将其余边加载到内存中。我计算了每个的Shorest哈密顿路径，然后我连接了所有最短的哈密顿路径。它是TSP的一个很好的近似值吗？对于大型图，有没有人知道更好的TSP近似算法？
浏览 5提问于2013-11-11得票数 0
1回答
我实现了一个算法来找到一组点的alpha形状。α形状是一组点的凹壳，其形状取决于参数α，该参数决定了构成船体的点。
浏览 4提问于2015-05-01得票数 1
回答已采纳
3回答
Dijkstra算法能否找到从一个源顶点到所有其他顶点的所有最短路径，使得该路径访问一个无向对称图中的所有顶点一次且恰好一次？对称图有没有更快的算法？
浏览 1提问于2013-06-07得票数 4
回答已采纳
2回答
我需要找到一条最短的路径，它从X开始，在Y结束，经过G的所有顶点(以任何顺序)。这不是旅行商问题:我不需要访问每个顶点一次，我也不想回到第一个顶点。
浏览 0提问于2016-04-16得票数 6
2回答
这是为一个项目，其中我被要求实现启发式的旅行推销员优化问题和哈密顿路径或周期决策问题。我不需要关于实现本身的帮助，但对我要走的方向有一个问题。我已经有了一个基于遗传算法的TSP启发式算法:它假设一个完整的图，从一组随机解作为一个群体开始，并在几代人中改进群体。我还可以用它来解决哈密顿路径或循环问题吗？我只想检查是否有路径，而不是优化以获得最短路径。
现在，任何完整的图都会有一条哈密顿路径，因此TSP启发式算法必须扩展到任何图。如果两个城市之间没有路径，这可以通过将边设置
浏览 1提问于2009-06-04得票数 5
回答已采纳
1回答
邻接矩阵中的路径查找
、、、
给定一个邻接矩阵，你如何找到两个节点之间的最短路径，同时至少遍历每一点一次，并返回所需的移动次数？1] [0] 3 [0] [1] [0] [0] [1]从0到4的最短路径是
浏览 2提问于2013-04-07得票数 0
1回答
给定两个顶点s和t，并跨过k，我想找到它们之间的最短路径，即：
路径中的每一个k“步骤”，从第一个算起，都是一条简单的路径。意思是，最短的非简单路径，只能在每一步“跳”k个顶点(准确的k)，而每一个“跳跃”必须是一个简单的子路径。有替代算法吗？
浏览 2提问于2015-12-28得票数 1
1回答
问题:在包含每个节点的无向加权图中寻找最短圈。所有的重量都是正数。一个节点可以被访问不止一次，它将问题与哈密顿循环(TSP)区分开来。最短循环距离=6 (1 -> 2 -> 1 -> 3 -> 1 -> 4 -> 1)
编辑:我正在寻找一个算法，以找到最短的周期。
浏览 4提问于2022-08-12得票数 1
回答已采纳
1回答
是否可以使用Dijkstra's Algorithm计算从单个源到单个目标的N条最短路径，其中N是节点数？我知道Dijkstra从一个源输出到图中所有节点的最短路径，但当我正在读一篇研究论文时，作者提到了使用Dijkstra计算s和t之间的N条最短路径，这让我有点困惑。以下引用原文：利用基于SDN的SCADA系统:一个反窃听的案例研究-也发现了
Dijkstra的算法22用于计算N个阶段的最短路径(步骤5)。考虑N= 2，在第一阶段，Dijkstra算法确定了两个网络设备之间
浏览 0提问于2015-11-25得票数 2
回答已采纳
4回答
我正在研究寻找最小生成树(在加权图的情况下)和查找图是否有哈密顿路径(这取决于哈密顿圈的存在)的算法。我把一切都搞砸了。那么哈密顿路径和生成树之间有什么区别呢？两者都覆盖了图中的所有顶点。虽然我们可以有高效的算法来寻找生成树(可能是最小生成树)，但为什么我们就不能有寻找哈密顿回路的算法呢？我们可以一次增加和删除一条边，直到我们到达一个循环，也许我们可以找到哈密顿循环？？
浏览 1提问于2011-07-23得票数 14
这是我在图中找到哈密顿圈的算法：private int V, pathCount;privatepathCount - 1; i++) return true;}输入是一个非对称矩阵(节点之间的一些链
浏览 7提问于2015-11-13得票数 2
3回答
我有一系列的图形坐标，我需要找到通过它们的最短的单向路径。我没有预先确定的开始/结束，但每个点只能触摸一次，并且不需要返回到最佳原点。我希望得到的结果是img #2
基本上，我想要连接n个点的最短链条
浏览 0提问于2011-01-24得票数 5
2回答
在做一个项目的时候，我偶然发现了一个我无法解决的图形算法问题。问题如下：
您有一个有向加权图，并希望在访问指定节点(非常类似于)时，在开始节点和结束节点之间找到最短路径。
浏览 0提问于2013-10-04得票数 3
回答已采纳
2回答
最长简单路径
、、、、
因此，我理解在图中寻找最长的简单路径的问题是NP困难的，因为您可以通过将边权重设置为1并查看最长简单路径的长度是否等于边的数量来轻松地解决哈密顿电路问题。我的问题是:如果你得到一个图，找到最大边权重m，用m - w替换每个边权重w，并在上面运行标准的最短路径算法，你会得到什么样的路径？
浏览 0提问于2009-04-04得票数 9
回答已采纳
1回答
我很难构造一个小的无向图G，它的加权边超过了给定的算法，这意味着无论起始点是什么，算法都不会选择最优解。每个节点都连接到每个其他节点。给定一个起点，该算法迭代地选择图上最近的未使用点并访问它，直到它循环回起始点为止。该算法以每个点为起点，从所有输出循环中选择最短的哈密顿循环。在我的一生中，我一直无法解决这个问题，我绘制了无数的图表，并对它们进行了研究和求解，但至今仍未能找到算法无法找到最优解的图表。
这完全是理论性的，没有代码。
浏览 0提问于2016-02-11得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
