程序员经验分享-hwhale

以最小总距离连接所有点的算法

2023-11-26

我有一组点和适用于每对点的距离函数。我想将所有点连接在一起，总距离最小。你知道我可以使用的现有算法吗？

每个点都可以链接到几个点，所以这不是通常的“推销员行程”问题:)

Thanks !


你想要的是一个最小生成树.

生成一个最常见的两种算法是：

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

Algorithm

以最小总距离连接所有点的算法 的相关文章

  • 如何动态查找连接组件

    使用不相交集数据结构可以很容易地得到图的连通分量 而且 它只是支持增量连接组件 http www boost org doc libs 1 46 1 libs graph doc incremental components html 然而

  • 基于时间的算法评分

    我们希望创建一种评分算法 在更短的时间内获得更高的分数 在更长的时间内获得更少的分数 需要注意的是 没有实际范围 因此时间范围可以从 100 毫秒到长达 10 分钟或更长时间 点范围为 0 到 50 谢谢你的帮助 你可以简单地把它变成一个线

  • 如何从二叉搜索树中均匀随机地返回节点？

    给定一个 BST 可能平衡也可能不平衡 如何能够均匀地随机返回 任何 节点 一个限制是您不能使用外部索引数据结构 您必须以每个节点都有平等被访问的机会的方式遍历树 这个问题让我困惑了好一阵子 如果我们确实可以使用外部哈希表 指针 我们可以对

  • 搜索/排序算法 - 是否有类似 GoF 的列表？

    我是一名自学成才的开发人员 坦率地说 我不太擅长找出在任何特定情况下使用哪种搜索或排序算法 我只是想知道是否有设计模式 esque 列出了以太坊中可用的常见算法 供我添加书签 就像是 算法名称 带有别名 如果有的话 它解决的问题 大O成本

  • 在关键服务器上对字符串进行内存受限的外部排序，并合并和计算重复项（数十亿个文件名）

    我们的服务器生成如下文件 c521c143 2a23 42ef 89d1 557915e2323a sign xml在其日志文件夹中 第一部分是GUID 第二部分是名称模板 我想计算具有同名模板的文件的数量 例如 我们有 c521c143

  • 用 Java 创建迷宫求解算法

    我被分配了用 Java 创建迷宫求解器的任务 这是任务 Write an application that finds a path through a maze The maze should be read from a file A

  • C 中的菱形数组排序

    我有以下 C 语言作业 我基本上需要一种方法而不是解决方案 我们有一个 13 x 13 的数组 在数组中 我们有一个需要考虑的菱形形状 该菱形之外的所有内容都初始化为 1 不重要 下面的 5 x 5 数组示例 x x 1 x x x 2 2

  • 如何求解：T(n) = T(n - 1) + n

    我已经解决了以下问题 T n T n 1 n O n 2 现在 当我解决这个问题时 我发现界限非常松散 我是否做错了什么 或者只是这样 您还需要一个递归关系的基本情况 T 1 c T n T n 1 n 为了解决这个问题 您可以首先猜测一个

  • 线性代数如何在算法中使用？

    我的几个同行都提到 学习算法时 线性代数 非常重要 我研究了各种算法并学习了一些线性代数课程 但我没有看到其中的联系 那么线性代数如何应用在算法中呢 例如 图的连接矩阵可以带来哪些有趣的事情 三个具体例子 线性代数是现代 3D 图形的基础

  • 寻找距离原点最近的 100 颗恒星的算法

    首先让我提出正确的问题 问 有一个文件包含超过一百万个点 x y 每个点代表一颗星星 a b 处有一颗行星地球 现在 任务是构建一种算法 返回距离地球最近的 100 颗恒星 您的算法的时间和空间复杂度是多少 这个问题在各种采访中被问过很多次

  • 我需要一个支持高效随机访问和 O(k) 插入和删除的容器

    我再次尝试问同样的问题question https stackoverflow com questions 3808708 delete parts of a dynamic array and grow other 但我最终提出了一个不同

  • 点集子集的最小周长凸包

    给定平面上的 n 个点 没有 3 个共线 给定数字 k 找到 k 个点的子集 使得 k 个点的凸包在 k 个点的子集的任何凸包中具有最小周长 我可以想到一个简单的方法 运行时间为 O n k k log k 找到大小为 k 的每个子集的凸包

  • 寻找将集合映射到整数的双射函数

    对于任意两个序列 a b 其中 a a1 a2 an 且 b b1 b2 bn 0a b具有相同的元素 而不关心它们的顺序 例如 如果 a 1 1 2 3 b 2 1 3 1 c 3 2 1 3 则 f a f b f a f b 我知道有

  • 时间复杂度和运行时间有什么区别？

    时间复杂度和运行时间有什么区别 它们是一样的吗 运行时间是指程序运行所需的时间 时间复杂度是对输入大小趋于无穷大时运行时间渐进行为的描述 您可以说运行时间 是 O n 2 或其他什么 因为这是描述复杂性类和大 O 表示法的惯用方式 事实上

  • 在 C++ 中通过引用传递 std 算法谓词

    我正在尝试从 a 中删除元素std list并保留已删除元素的一些统计信息 为此 我使用列表中的remove if 函数 并且我有一个谓词 我想使用这个谓词来收集统计数据 这是谓词的代码 class TestPredicate privat

  • Karasuba算法递归过多

    我正在尝试用 c 实现 Karasuba 乘法算法 但现在我只是想让它在 python 中工作 这是我的代码 def mult x y b m if max x y lt b return x y bm pow b m x0 x bm x1

  • 关于在字典中查找所有有效单词的算法问题

    给定一个字典 只是一个字符串列表 您收到来自外部来源的未知数量的信件 给定字母串 您将如何列出您可以通过这些字母的任意组合组成的所有有效单词 来自字典 因此 如果您收到 applead 你应该找到apple bad pad lead等 我知

  • 分而治之策略来确定列表中是否有超过 1/3 的相同元素

    我正在使用分治算法来确定列表中是否有超过 1 3 的元素相同 例如 1 2 3 4 不 所有元素都是唯一的 1 1 2 4 5 是的 其中 2 个是相同的 没有排序 是否有分而治之的策略 我陷入了如何划分的困境 def is valid i

  • C# 中的 strstr() 等效项

    我有两个byte 我想找到第二个的第一次出现byte 在第一个byte 或其中的一个范围 我不想使用字符串来提高效率 翻译第一个byte to a string会效率低下 基本上我相信就是这样strstr 在 C 中做 最好的方法是什么 这

  • 如何有效地找到距给定点最远的点（从一组点中）？

    我正在寻找一种算法或数据结构来解决以下问题 给你一组点 S 然后你会得到另一个点形式的 Q 查询 对于每个查询 找到集合中距离给定点最远的点 集合中最多有 10 5 个点和 10 5 个查询 所有点的坐标都在 0 到 10 5 范围内 我想

随机推荐

  • 访问联系人并获取电子邮件地址

    我有一个用于访问联系人的代码片段 当用户单击该按钮时 联系人列表将打开 用户可以从联系人中选择一个人 并且该人的电子邮件地址应写在编辑文本上 我可以收到用户选择的人发来的电子邮件 但我无法将其设置为编辑文本 static String em

  • 如何替换标准 DataAnnotations 错误消息

    我正在使用 System ComponontModel DataAnnotations 来验证我的模型对象 如何替换消息标准属性 Required 和 StringLength 生成的而不向每个属性提供 ErrorMessage 属性或对它

  • 如何在 Rails 中的 LOWER("users"."username") 上创建索引（使用 postgres）

    我的系统中发生了顺序扫描UsersController create action SELECT AS one FROM users WHERE LOWER users username LOWER AND users id LIMIT E

  • loadFromRemoteSourcesenabled="true" // XAML 设计器 // VS 11 beta 和 2012 RC

    我经常被这种情况刺痛 当然总是在最糟糕的时刻 当我编辑 xaml 文件时 收到此错误 System NotSupportedException An attempt was made to load an assembly from a n

  • TRY/CATCH 不适用于 SQL Server 代理错误？

    I use sp start job开始工作 工作 test2 只有一步 select getdate waitfor delay 00 00 10 The TRY CATCH code begin try EXEC msdb dbo sp

  • 使用 SQL 视图还是 SQL 查询？

    我正在开发一个从 MS SQL 服务器获取数据的应用程序 2005 在命令文本中 我可以传递这样的 sql 查询 string query SELECT T1 f1 T1 f2 T2 f3 FROM table1 T1 join table

  • 写入字符串时出现分段错误[重复]

    这个问题在这里已经有答案了 我正在尝试编写一个就地反向函数 并且几乎完全遵循在线代码 但运行以下程序会引发总线错误 我是否向reverse 传递了错误类型的参数 void reverse char str char end str char

  • 如何在Android应用程序中播放直播？

    我想申请板球直播 我想知道以下事情 从哪里可以找到播放板球直播的链接 这些是什么类型的链接 有没有播放器可以播放这种类型的视频 目前 我已经实现了网页 但我正在寻找其他替代方案 下面是我的代码 link1 RelativeLayout fi

  • 暂时禁用关闭按钮

    我需要禁用just暂时关闭按钮 应允许最小化和最大化 我尝试过的每个解决方案都会禁用all按钮或只是永久禁用关闭按钮 有没有办法暂时做到 去的方法永久禁用关闭按钮是设置CS NOCLOSE style对于窗体的窗口类 要从 WinForms

  • EF Code First 迁移在 Azure Web 角色上抛出 StackOverflowException

    在 Azure Web 角色 WS 2012 R2 中执行 EF 6 1 2 代码优先迁移时会出现此问题 即使我将连接字符串指向 Azure Sql 数据库 相同的迁移也可以在本地正常运行 StackOverflowException 是由

  • 整数除法与下限商的比较：为什么会出现这个令人惊讶的结果？

    The 今天 Python 的 整数除 运算符让我感到惊讶 gt gt gt math floor 11 1 1 10 0 gt gt gt 11 1 1 9 0 The 文档读作 x 和 y 的 地板 商 那么 为什么 math floo

  • 需要 JavaScript 原型解释

    我通常在我的项目中以这种方式创建我的类 对象文字 var objectName global variables a somevalue func1 function func2 function 如果我必须将其转换为原型格式 我该怎么做

  • SwiftUI 控制台显示 CVDisplayLink 相关消息？

    当我运行我正在开发的基于 MacOS 的 SwiftUI 应用程序时 我在控制台上收到大量输出 例如 2021 12 08 12 40 14 439565 0000 SpDriveApp 6801 159299 0x7fe6e7830820

  • HTML如何在网页中插入动态日期

    我有一个静态网页 没有任何动态变化 然而 客户希望将日期插入到页面内的文本中 该日期将始终是当前日期加上一天 我怎么做 使用 JavaScript 并在加载时插入日期 看一下这里的工作示例 http jsfiddle net xGDvp 这

  • 被 FoldLeft 错误困惑（在 Eclipse 和 REPL 中）

    其背景非常简单 我的假设基于 Odersky 的书 Programming in Scala 2nd Edition 第 8 5 节描述了 占位符语法 我有一个 List List Boolean 即矩形位图 我试图在其中计算值 true

  • 什么是自动覆盖索引？

    使用时EXPLAIN QUERY PLAN在 SQLite 3 中 它有时会给我输出 例如 SEARCH TABLE staff AS s USING AUTOMATIC COVERING INDEX is freelancer AND s

  • 如何将图像和录制文件保存在临时目录中？

    我想将从我的应用程序中拍摄的相机照片和视频录制存储在临时目录中的单独文件夹中一段时间 当任务完成时 他们将保存到数据库中 如何将从相机和视频录制文件中拍摄的图片保存在临时目录中的单独文件夹中 您正在寻找这个来访问缓存文件夹来存储临时文件 N

  • R：ggfortify：“自动绘图不支持 prcomp 类型的对象”

    我正在尝试使用 ggfortify 来可视化我使用 prcomp 所做的 PCA 结果 示例代码 iris pca lt iris c 1 2 3 4 autoplot prcomp iris pca 错误 自动绘图不支持 prcomp 类

  • JPA Hibernate n+1 问题（Lazy 和 Eager Diff）

    我试图理解 n 1 问题 从而找到正确的解决方案 我有两个实体 公司 Entity Table name company public class Company implements Serializable private static

  • 以最小总距离连接所有点的算法

    我有一组点和适用于每对点的距离函数 我想将所有点连接在一起 总距离最小 你知道我可以使用的现有算法吗 每个点都可以链接到几个点 所以这不是通常的 推销员行程 问题 Thanks 你想要的是一个最小生成树 生成一个最常见的两种算法是 Prim

热门标签