图中的最小代价循环路径——TSP的一种变体
例如，我们有一个由顶点（城市）和边（道路）组成的图，每个边（道路）都有一个特定的成本，找到至少一次访问所有城市的最小成本。Cost是所遍历边的边成本之和。“至少有一次”这个角色吸引了我。在TSP中，根据Wiki，我们只能访问一次节点。考虑图，在TSP中，循环路径为A-B-E-D-C-A成本-140（或A-C-D-E-B-A成本-140）。其中，根据我的问题描述，我们可以访问每个顶点至少一次，这样我们就可以得到循环路径a-C-D-C-E-B-a cost-63
共有2个答案
假设您允许多次访问一个顶点，这有效地将您的不完整图转换为完整图（所有顶点连接），这就是TSP所要求的。在一般情况下解决您的问题与解决度量TSP完全相同。好消息是这是一个经过大量研究的主题。坏消息是您无法回避TSP——因为您的问题与TSP的一种形式相同。
正如其他人所指出的，通过计算每对顶点之间的最短代价并在缺失的地方添加这些边，可以完成图形。您还需要替换任何已发现间接路径成本较低的现有直边，以便有一个度量TSP。您可以使用新的合成边存储其实际路径（通过中间顶点），以便恢复这些路径以获得最终答案，或者在收到TSP的结果时根据需要重新计算这些路径。
现在您可以将其作为TSP来解决。然而，在一般情况下，以最佳方式求解TSP过于昂贵，因此您可能需要使用近似解算法。有各种各样的算法（例如Christofides算法、Lin-Kernighan启发式）可用，它们在保证的最优性水平和算法的性能之间做出不同的权衡。
如果您实际上不关心完成循环，只需要访问所有顶点的最小路径，从任何顶点开始和结束，这是一个有点不同的问题。为此，请在此处阅读我的答案：https://stackoverflow.com/a/33601043/5237297
对于每对节点，可以应用最短路径算法并计算最短距离。这将是每对的新成本矩阵。
现在它被简化为旅行推销员问题。
然后可以应用TSP求解技术。
-
给出了一个有向无环图G=(V，E)，如果需要，可以假定它是拓扑有序的。G中的边有两种类型的成本--名义成本w(e)和尖峰成本p(e)。 目标是找到从节点s到节点t的最短路径，使以下代价最小:sum_e(w(e))+max_e(p(e))，其中和和最大值在路径的所有边上取值。 标准动态规划方法表明，该问题在O(e^2)时间内是可解的。有没有更高效的办法解决？理想情况下，一个O(E*polylog(E
-
我在这里要问的问题以前在堆栈溢出中已经被问过了。但我无法正确理解Skiminok发布的解决方案。 这是链接。 我尝试了上面链接上发布的解决方案，并给出了两个示例测试用例，但我无法得到正确的答案。 对于测试用例 1：： N=3 和 K=2 5 4 7 DAG将会是: 注：我构建上述DAG时考虑到： 设pi和pj是两个不同的问题。然后，我们将从pi到pj绘制一条有向边，当且仅当pj可以在pi之后的同一
-
例如，给定以下矩阵： 其中对于每个元组，第一个数字是食物，第二个数字是水。我需要从右下角到左上角，我只能向上或向左移动。
-
我正试图为以下情况想出一个算法：我想在一个无向图上运行一个最小代价算法。边有一个与之相关的代价，顶点有两个与之相关的代价。这就是它变得有点棘手的地方。我必须选择与顶点相关的2个成本中的一个。如果我选择cost1，顶点将属于类型1，如果我选择cost2，顶点将属于类型2。只有当顶点具有不同的类型时，它们才能被认为是由一条边连接的。大多数时候，为顶点选择成本最低的顶点是合乎逻辑的，但是根据与它相关联的
-
我想在有向（无环）图中找到最长的路径。假设我知道起始节点-汇。路径应该从这一点开始。我在想我可以将边的权重设置为-1。有很多方法可以找到所有最短的路径，但你必须通过终点。有没有可能得到最短的路径（无论最终节点如何）？ 假设我想为节点 nr 1（汇）找到最长路径。所以这个算法给了我1-2-3-4-5-6。