程序员经验分享-hwhale

如何最小化最短路径树的总成本

2023-12-30

我有一个具有正边权重的有向无环图。它具有单个源和一组目标（距离源最远的顶点）。我找到从源到每个目标的最短路径。其中一些路径重叠。我想要的是一个最短路径树，它可以最小化所有边上的权重总和。

例如，考虑其中两个目标。假设所有边的权重相等，如果它们在大部分长度上共享一条最短路径，那么这比两条几乎不重叠的最短路径要好（树中的边越少，总成本越低）。

另一个例子：两条路径在其长度的一小部分内不重叠，不重叠路径的成本较高，但长共享路径的成本较低（组合成本较低）。另一方面，两条路径在其大部分长度上都是不重叠的，非重叠路径的成本较低，但短共享路径的成本较高（而且组合成本较低）。有很多种组合。考虑到从源到目标的所有最短路径，我希望找到总体成本最低的解决方案。

换句话说，我想要最短的最短路径树。

这对任何人来说都敲响了警钟吗？谁能向我指出相关算法或类似应用程序？

Cheers!


这个问题 （斯坦纳树 http://portal.acm.org/citation.cfm?id=1414423) 是 NP 困难且最大 SNP 完全的，因此除非 P = NP，否则既不存在多项式时间算法，也不存在 PTAS（任意接近的近似）。

MST 可以给出比最佳权重任意差的权重，除非您知道图的某些特殊特征（例如图是平面的，或者至少权重服从三角不等式）。例如，如果您有 K_1,000,000,001，所有边权重均为 1，且只有一个目标，则最优解的权重为 1，MST 的权重为 1,000,000,000。

如果您假设目标之间的所有边以及源与每个目标之间的所有边都存在，您仍然可以通过任意因子进行超调。考虑上面的示例，但将目标和源之间的边权重更改为 2,000,000,000,000,000,000（仍与最佳值相差十亿倍）。

当然，您可以通过遍历图形来转换图形以“删除”时间 O(E) 左右的高边权重。加上目标和源集的 MST，得出的近似比率为 2。

存在更好的近似比率。 Robins 和 Zelikovsky 有一个多项式时间算法，其性能永远不会比最优算法差超过 54.94%：http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Chlebik 和 Chlebikova 表明，接近于 1.05% 是 NP 困难的：图上的斯坦纳树问题：不可近似性结果 http://portal.acm.org/citation.cfm?id=1414423（doi 10.1.1.4.1339）

如果你的图表是平面的，情况会更好。 Borradaile、Kenyon-Mathieu 和 Klein（基于 Erickson、Monma 和 Veinott）提出了一种快速算法，可以给出任意接近的近似值：平面图中 Steiner 树的 O(nlogn) 近似方案 http://portal.acm.org/citation.cfm?doid=1541885.1541892（DOI 10.1.1.133.4154）

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

graphtheory

shortestpath

如何最小化最短路径树的总成本 的相关文章

  • 从一个节点 A 到节点 B 的最大边权

    给定一个连通的无向图N节点 1 NN 1边缘 我们定义一个函数F a b where F a b 等于路径中的最大边权重a to b 我们如何找到总和F a b 对全部a b这样1 lt a b lt N 模 10 9 7 示例图 F a

  • 关于图形工具中嵌套块模型的基本问题

    非常简短地提出两到三个基本问题minimize nested blockmodel dl https graph tool skewed de static doc inference html graph tool inference m

  • 如何用Python检测有向图中的循环？

    我有一些输入 例如 A B C D D C C D 我想查找此edgeList表示的有向图中是否存在循环 我读到一个讨论 https www geeksforgeeks org detect cycle in a graph https w

  • 网络直径是什么意思？

    上图所示这个链接 http en wikipedia org wiki Vertex 28graph theory 29的 具有 6 个顶点和 7 个边的图 其中最左侧的 6 号顶点是叶顶点或下垂顶点 有直径4吗 对还是错 定义是 图的直径

  • 为什么使用 DFS 而不是 BFS 来查找图中的循环

    DFS 主要用于查找图中的循环 而不是 BFS 有什么理由吗 两者都可以查找节点是否已经存在 遍历树 图时访问过 深度优先搜索比广度优先搜索更节省内存 因为您可以更快地回溯 如果使用调用堆栈 实现起来也更容易 但这依赖于不会溢出堆栈的最长路

  • 3D 迷宫中的最短路径

    我正在尝试编写一个程序来使用递归查找 3D 迷宫中的最短路径 我能够编写找到穿过迷宫的随机路径的代码 但我想知道如何修改我的代码以找到最短路径 请注意 我想保留递归方法 有人可以提出解决方案吗 这是一个二维迷宫示例 s XXXX XX X

  • 未加权图的最短节点序列

    我想知道是否有一种算法可以通过从头节点到尾节点的图找到最短的节点序列 该图从头节点分支出来 并且是任意复杂的 并在尾节点处收敛 节点之间的所有连接都是未加权的 我正在考虑解决这个问题 从头节点和尾节点采取探索性步骤 直到图形两端的节点接触等

  • 检查 DI-Graph 中是否存在任何路径

    如果我有一个有向图 如何检查所有节点对 a b 是否创建路径 Example Input v1 v2 v5 v6 v2 v3 v3 v4 v4 v5 v0 v1 我需要检查该图中是否存在至少一条路径 而无需多次访问每个节点 我已经尝试过回溯

  • 如何在 Javascript 中说明多重图？ [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 这个问题正在寻找一种实用且简单的方法来使用 Javascript 绘制多重图 首先看this http

  • 从 A[a,b] 到 A[c,d] 的不同非循环路径的计数？

    我正在编写一个推箱子求解器 用于娱乐和练习 它使用一个简单的算法 类似于 BFS 但略有不同 现在我想估计它的运行时间 O 和 omega 但需要知道如何计算网络中从一个顶点到另一个顶点的非循环路径的计数 实际上我想要一个表达式来计算 m

  • 可以多次访问顶点的 TSP

    我正在寻求解决一个问题 其中我有一个加权有向图 并且必须从原点开始 至少访问所有顶点一次并以尽可能最短的路径返回原点 本质上 这将是 TSP 的一个经典示例 除了我DO NOT具有每个顶点只能被访问一次的约束 在我的例子中 除了原点之外的任

  • 寻找多条短路径的算法

    寻求一种能够产生 N 条短路径的算法 有没有人有算法的经验来寻找多条短路径在有向图中 我的应用程序用于语言 查找同义词链 但从逻辑上讲 这可能用于地理或社交网络 我想要明显不同的路径 而不仅仅是沿途交换几个节点 我真的很想知道是否有办法避免

  • 是否有用于平面度测试的在线算法？

    我知道平面度测试 http en wikipedia org wiki Planarity testing可以在 O v 相当于 O e 因为平面图有 O v 条边 时间内完成 我想知道是否可以在 O 1 摊销时间内在线完成 因为添加每个边

  • 如何在 O(n+m) 时间内找到有向图中的母顶点？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 有向图 G V E 中的母顶点是顶点 v 使得所有其他顶点 顶点 G 可以通过从 v 出发的有向路径到达 给出一个 O n m 算法来

  • Prolog 同构图

    这里尝试解决同构图问题 作业信息 判断2个无向图是否同构 没有孤立的顶点 顶点数小于30 图的边作为谓词给出 即 e 1 2 f 1 2 我正在尝试使用以下方法 对于每对边 即图 1 和图 2 中的每条边 Try to bind the v

  • 强连通分量有什么用？

    我发现了几种可以解释的算法how在有向图中找到强连通分量 但没有解释why你会想要这样做 强连通分量有哪些应用 您应该查看 Coursera 上 Tim Roughgarden 的算法简介课程 对于他所讨论的每一种算法 他都会解释其一些应用

  • 求矩阵 (n x n) 的最小总和，在每一行和每一列中只选择一个

    这是与动态规划相关的另一个算法问题 问题是这样的 找到给定矩阵的最小总和 以便在每一行和每一列中选择一个 例如 3 4 2 8 9 1 7 9 5 最小的一个 4 1 7 我认为解决方案是网络流量 最大流量 最小切割 但我认为它不应该那么难

  • 优化 WPF 中由单元格组成的网格以获得最短路径

    我目前正在尝试在 WPF 中制作一个由 Cell 对象组成的网格 我需要将单元格绑定到对象 该对象需要位于二维数组中 我需要它很大 可扩展 并改变单元格的颜色并将数据存储在对象中 我已经实现了 但是绘制网格似乎很慢 100x100 网格需要

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

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

  • AStar-名称解释

    我正在寻找 AStar A 算法为何被称为 AStar 的解释 所有类似的 最短路径问题 算法通常都以其开发者的名字命名 那么 AStar 代表什么 有称为 A1 和 A2 的算法 后来证明A2是最优的 实际上也是可能的最好算法 所以他给它

随机推荐

  • 如何定义自定义源集而不在 Gradle 中显式定义其路径？

    说明书上是这么写的 IE 那src sourceSet java是 给定源集的 Java 源 的默认路径 如何利用这个 假设我想创建源集demo 我可以写吗 sourceSets demo java srcDir src demo java

  • 如何使用 Firestore 获取当前登录用户的文档？ [复制]

    这个问题在这里已经有答案了 我的 Firestore 中有这个结构 我希望登录的用户能够获取所有图像 URL 以及与该用户 ID 关联的其他字段 例如名称 价格和描述 此信息将被加载到 recyclerView 中 这是项目模型 packa

  • 计算点向量的平均值

    我在 OpenCV 中有一个二维点的向量 std vector

  • 如何在 jquery ui 对话框中提交表单并显示其响应

    你好 我正在使用 jquery ui 对话框并尝试使用 ajax 提交表单并显示其响应 直到表单对话框和 ajax 请求其工作正常 但不知道如何在同一对话框中显示其响应 任何建议都会帮助我 假设您有以下标记 div style displa

  • 如何禁用漂亮照片？

    我现在如何启用prettyphoto 但问题是如何禁用 这里我启用了 PrettyPhoto document ready function a rel prettyPhoto prettyPhoto social tools false

  • Facebook 访问令牌无法扩展

    我正在使用 facebook android sdk 我刚刚从 github 下载了它 我了解访问令牌仅在非常有限的时间内有效 并且每次应用程序启动时都需要按照文档中的描述进行扩展 https developers facebook com

  • UIPickerView 辅助功能 VoiceOver 问题

    启用 VoiceOver 后 无论我们滑动到哪一行 UIPickerView 的画外音始终显示 Item 1 of TotalNumberOfItems 以编程方式 所有元素都会使用正确的选定索引进行更新 但 VoiceOver 始终显示

  • 如何从 C# 中的类访问表单方法和控件？

    我正在开发一个 C 程序 现在我有一个Form和几节课 我希望能够访问一些Form控件 例如TextBox 来自我的班级 当我尝试更改文本中的文本时TextBox从我的课堂上我收到以下错误 非静态字段 方法或属性 Project Form1

  • OpenCV 和像 Adob​​e Photoshop 一样的锐化遮罩

    我正在尝试像 Adob e Photoshop 中那样实现模糊遮罩 我在互联网上收集了很多信息 但我不确定我是否遗漏了一些东西 这是代码 void unsharpMask cv Mat img double amount double ra

  • 如何使用保存的 html 从 Gridstack 构建网格

    我一直在使用 Gridstack 动态创建网格 我使用以下函数来序列化网格及其数据 但我似乎不知道如何构建我的网格and它的内容来自它创建的 JSON 数组 我查过https github com troolee gridstack js

  • 在 Mapbox 中获取两点之间的路线？

    我最近在 React Native 上使用 Mapbox gl 而不是 Google 地图 我正在尝试添加一个功能 显示地图上从 A 点到 B 点的方向 OR use Mapbox 路线 API https docs mapbox com

  • EPPLUS 可清除一系列细胞的内容物

    我想使用 EPPLUS 清除一系列细胞 我尝试了下面的语法 但它给了我一个错误 你调用的对象是空的 使用 EPPLUS 清除细胞 A24 C36 内容物的正确方法是什么 ExcelPackage package new ExcelPacka

  • C# travis 的问题

    特拉维斯 西尔现在支持 C http docs travis ci com user languages csharp 测试版 尝试了 8 种不同的方法后 我找不到解决我的问题的方法 我有一个 ASP MVC 项目 travis 使用 mo

  • 如何使用 LIKE 运算符在 SQL Server 中进行此匹配？

    我正在尝试匹配价格字符串 例如 25 00 来查找相应的货币符号 例如 25 00 应与美元匹配 这已经很有效了 然而 当我输入 25 00 无货币符号 时 我在 CUP 上出现了不需要的匹配 我在 SQL Server 2012 中设置了

  • iOS 8 Today 小部件对齐问题

    这是我的故事板 我正在使用自动布局 而不是使用尺寸类别 When I ran it on iPhone 5s it works fine both portrait and landscape But when I ran it on iP

  • Office.js 使浏览器历史记录功能无效，破坏历史记录使用情况

    Office js 的官方版本可以在这里找到 https appsforoffice microsoft com lib 1 hosted office js 它包含以下代码行 window history replaceState nul

  • 当 Facebook 用户点击 FB Like 按钮时，我如何向他们发送电子邮件？

    用户点击我页面上的 Facebook Like 按钮后 我想自动向他们发送一封电子邮件 这可能吗 您不能强制用户连接您的应用程序并授予email单击 赞 按钮即可获得许可 不过你可以订阅edge create event http deve

  • 对列组应用函数

    我该如何使用apply或者一个相关的函数来创建一个新的数据框 其中包含一个非常大的数据框中每对列的行平均值的结果 我有一个可以输出的仪器n在大量样本上复制测量值 其中每个测量值都是一个向量 所有测量值都是相同长度的向量 我想计算每个样本的所

  • Angular - 如何查看过滤器结果数组以了解控制器的更改

    我有一个过滤器 可以通过 ng repeat 列表根据某些条件进行过滤 我如何查看由过滤服务创建的结果数组以了解控制器内部的更改 完整的问题和描述在这里角度工厂过滤器 无法将数据传递到过滤器 https stackoverflow com

  • 如何最小化最短路径树的总成本

    我有一个具有正边权重的有向无环图 它具有单个源和一组目标 距离源最远的顶点 我找到从源到每个目标的最短路径 其中一些路径重叠 我想要的是一个最短路径树 它可以最小化所有边上的权重总和 例如 考虑其中两个目标 假设所有边的权重相等 如果它们在

热门标签