程序员经验分享-hwhale

不考虑回到起点的旅行商问题（TSP）的问题名称是什么？

2023-12-20

我想知道 TSP 的问题名称是什么，不考虑返回起点的方式，以及解决这个问题的算法是什么。

我研究了最短路径问题，但这不是我想要的，问题只是从 2 个指定点找到最短路径。但我要寻找的是我们给出n个点并且只输入1个起点的问题。然后，找到经过所有点一次的最短路径。 （终点可以是任意点。）

我还研究了哈密顿路径问题，但似乎不是解决我定义的问题，而是查找是否存在哈密顿路径。


我在中找到了我的问题的答案这本书 https://rads.stackoverflow.com/amzn/click/com/0471904139。这与在计算机和其他数字系统的设计中反复出现的计算机布线问题相同。目的是最小化电线总长度。所以，它确实是最小长度哈密顿路径。

书中建议创建一个虚拟点，其与其他点的距离均为 0。因此，问题变成了 (n+1) 个城市对称 TSP。求解后，只需删除虚拟点，然后求解最小长度哈密顿路径，就可以得到TSP路径，而无需返回起点。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

graphalgorithm

travelingsalesman

nphard

不考虑回到起点的旅行商问题（TSP）的问题名称是什么？ 的相关文章

  • 编程 Pearls - 随机选择算法

    Programming Pearls 第一版第 120 页介绍了从 N 个整数总体中选择 M 个等概率随机元素的算法 InitToEmpty Size 0 While Size lt M do T RandInt 1 N if not Me

  • 使用C标准数学库精确计算标准正态分布的CDF

    标准 C 数学库不提供计算标准正态分布 CDF 的函数 normcdf 然而 它确实提供了密切相关的函数 误差函数 erf 和互补误差函数 erfc 计算 CDF 的最快方法通常是通过误差函数 使用预定义常量 M SQRT1 2 来表示 d

  • 找到一系列间隔的最有效分组

    我有一个应用程序 其中有一系列不重叠的固定宽度间隔 每个间隔都有一个给定的键 每个间隔具有相同的宽度 并且可以存在连续的间隔 本质上 我想以最小化单独间隔的数量的方式对间隔和键进行分组 这可以通过合并具有相同键的连续间隔或查找匹配间隔并将它

  • 解释一下从 N 个给定集合中的每一个中给出第 K 个最大数字的示例？

    今天我尝试解决一个Facebook 编程挑战赛 https facebook interviewstreet com recruit challenges 我遇到的挑战是 酒吧问题 可以找到here https github com alo

  • 如何求小于给定数的最大2次方

    我需要找到小于给定数字的最大 2 次幂 我陷入困境 找不到任何解决方案 Code public class MathPow public int largestPowerOf2 int n int res 2 while res lt n

  • 无需构建树即可预测霍夫曼压缩比

    我有一个二进制文件 我知道其中每个符号出现的次数 如果我要使用霍夫曼算法压缩它 我需要预测压缩文件的长度 我只对假设的输出长度感兴趣 而不对单个符号的代码感兴趣 因此构建霍夫曼树似乎是多余的 作为一个例子 我需要得到类似的东西 包含 4 个

  • 从三点求圆心的算法是什么？

    我在圆的圆周上有三个点 pt A A x A y pt B B x B y pt C C x C y 如何计算圆心 在Processing Java 中实现它 我找到了答案并实施了一个可行的解决方案 pt circleCenter pt A

  • 0-1背包算法

    以下 0 1 背包问题是否可解 浮动 正值和 浮动 权重 可以是正数或负数 背包的 浮动 容量 gt 0 我平均有 这是一个相对简单的二进制程序 我建议用蛮力进行修剪 如果任何时候你超过了允许的重量 你不需要尝试其他物品的组合 你可以丢弃整

  • 生成所有多集大小为 n 的分区的算法

    我一直在试图找出一种方法来生成多重集的所有不同的大小为 n 的分区 但到目前为止却空手而归 首先让我展示一下我想要实现的目标 假设我们有一个输入向量uint32 t std vector

  • 使用多级解决方案计算二维网格中的最近邻

    我有一个问题 在 x y 大小的网格中 我提供了一个点 并且我需要找到最近的邻居 在实践中 我试图在 pygame 中找到距离光标最近的点 该点跨越颜色距离阈值 计算如下 sqrt rgb1 0 rgb2 0 2 rgb1 1 rgb2 1

  • 绘制多边形

    我正在使用 Google Maps API V3 根据路径绘制多边形 该路径是随机未排序坐标点 LatLng 的数组 这会产生以下形状 Polylines intersect Problem 由于多边形的形状取决于路径中点的顺序 因此如何对

  • 子序列和

    给定一个整数数组 例如 1 2 3 1 查找是否存在总和为0并返回它 例如 1 2 3 or 2 3 1 检查每个子序列是O n 2 这效率太低了 有改进的想法吗 创建一个新数组 其中每个元素等于前一个元素加上该元素的总和 Input 1

  • 找到一条穿过任意节点序列的最短路径？

    In 这个先前的问题 https stackoverflow com questions 7314333 find shortest path from vertex u to v passing through a vertex wOP询

  • 迭代任意大小的子集

    我可以迭代大小为 1 的子集 for int a 0 a lt size a 或大小为 2 的子集 for int a1 0 a1 lt size a1 for int a2 a1 1 a2 lt size a2 or 3 for int

  • 大数据使用什么数据结构

    我有一个包含一百万行的 Excel 工作表 每行有 100 列 每行代表一个具有 100 个属性的类的实例 列值是这些属性的值 哪种数据结构最适合在这里使用来存储数百万个数据实例 Thanks 这实际上取决于您需要如何访问这些数据以及您想要

  • 举例解释bpe（字节对编码）？

    有人可以帮忙解释一下背后的基本概念吗BPE模型 除了这张纸 https arxiv org abs 1508 07909 目前还没有那么多解释 到目前为止我所知道的是 它通过将罕见和未知的单词编码为子词单元序列来实现开放词汇表上的 NMT

  • 解开 Knuth 的结：如何重构意大利面条式代码？

    这个问题的灵感来自如何将流程图转化为实施 https stackoverflow com questions 36647765它询问如何通过算法消除goto代码中的语句 这answer https stackoverflow com a 3

  • 照片马赛克算法。如何在给定基本图像和瓷砖列表的情况下创建马赛克照片？

    Hy 我要做的是创建一个程序 使用 C 或 C 它将 24 位 像素位图和图像集合作为输入 我必须创建一个马赛克图像 类似于使用库的输入图像给定的图像 创建与输入类似的马赛克照片 到目前为止 我可以访问输入的图像像素及其颜色 但我有点卡住了

  • 需要解释搜索最小大和的算法

    我正在解决 Codility 问题作为练习 但无法回答其中一个问题 我在互联网上找到了答案 但我不明白这个算法是如何工作的 有人可以引导我逐步完成它吗 这是问题 You are given integers K M and a non em

  • 归并排序中的递归：两次递归调用

    private void mergesort int low int high line 1 if low lt high line 2 int middle low high 2 line 3 mergesort low middle l

随机推荐

热门标签