专栏首页arxiv.org翻译专栏用少终端解决斯坦纳树问题(CS AI)
原创

用少终端解决斯坦纳树问题(CS AI)

斯坦纳树问题是网络设计、路由和超大规模集成电路设计中众所周知的问题。给定一个图、边成本和一组专用顶点(终端),斯坦纳树问题要求输出一个以最小成本连接所有终端的子图。一种通过动态规划来解决斯坦纳树问题的现有算法是迪克斯特拉-斯坦纳算法。该算法基于终端的子集,通过系统地搜索较小的实例,并为这些较小的实例组合斯坦纳树,来构建整个实例的斯坦纳树。该搜索严重依赖于引导启发式函数来修剪搜索空间。然而,为了确保正确性,该算法只允许有限的启发式函数,即满足所谓一致性条件的函数。

在本文中,我们改进了Dijkstra-Steiner算法,并建立了一个重访算法,称为DS∑。DS∫算法允许任意的下限,因为启发式放松了启发式函数的先前条件。值得注意的是,我们现在可以使用基于线性规划的下限。此外,我们在一个条件下捕获启发式函数的新要求,我们称之为可容许性。我们证明了当使用可容许的启发式函数时,可容许性确实弱于一致性,并证明了DS∫算法的正确性。我们实现了DS∫并将其与现代预处理相结合,产生了一个开源求解器(DS∫Solve)。最后,我们在标准基准上比较它的性能,并观察竞争行为。

原文题目:Solving the Steiner Tree Problem with few Terminals

原文:The Steiner tree problem is a well-known problem in network design,routing, and VLSI design. Given a graph, edge costs, and a set ofdedicated vertices (terminals), the Steiner tree problem asks to output asub-graph that connects all terminals at minimum cost. A state-of-the?art algorithm to solve the Steiner tree problem by means of dynamicprogramming is the Dijkstra-Steiner algorithm. The algorithm builds a Steiner tree of the entire instance by systematically searching for smaller instances, based on subsets of the terminals, and combining Steiner trees for these smaller instances. The search heavily relies on a guiding heuristic function in order to prune the search space. However, to ensure correctness, this algorithm allows only for limited heuristic functions, namely, those that satisfy a so-called consistency condition.

In this paper, we enhance the Dijkstra-Steiner algorithm and es?tablish a revisited algorithm, called DS∗. The DS∗ algorithm allows for arbitrary lower bounds as heuristics relaxing the previous condition on the heuristic function. Notably, we can now use linear program?ming based lower bounds. Further, we capture new requirements for a heuristic function in a condition, which we call admissibility. We show that admissibility is indeed weaker than consistency and establish correctness of the DS∗ algorithm when using an admissible heuristic function. We implement DS∗ and combine it with modern preprocessing, resulting in an open-source solver (DS∗Solve). Finally, we compare its performance on standard benchmarks and observe a competitive behavior.

原文作者:Fichte Johannes K.1, Hecher Markus,Schidler Andr

原文链接:https://arxiv.org/abs/2011.04593

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 有状态世界中的性能预测(CS ML)

    部署的监督机器学习模型做出预测,与世界互动并影响世界。佩尔多莫等人(2020)将这种现象称为施为性预测,他们在无状态环境中对此进行了研究。我们将他们的结果推广到...

    识檐
  • 图的多智能体分散信念传播(CS AI)

    我们考虑交互式部分可观测马尔可夫决策过程问题,其中代理位于通信网络的节点。具体来说,我们假设所有消息都有特定的消息类型。此外,每个代理根据交互的信念状态、在本地...

    识檐
  • 星际转移轨道设计的差分进化优化工具(CS AI)

    星际转移轨道设计中极其敏感和高度非线性的搜索空间给全局优化带来了巨大挑战。作为代表,目前已知的由欧洲航天局(ESA)设计的全球轨道优化问题(GTOP)的最佳解是...

    识檐
  • TRTC横竖屏切换2,重力感应

    如前篇文章《TRTC横竖屏切换》介绍,TRTCSDK提供了三个api,支持手动调整横竖屏切换,组合起来有4X4X4=64种变化,满足所有横竖屏切换需求。

    腾讯云-chaoli
  • 【2019年8月版本】OCP 071认证考试最新版本的考试原题-第9题

    Which three statements are true about views in an Orade batabase?

    用户5892232
  • 飘窗效果

    Spaceack
  • IP网络技术笔记

    IP地址在计算机中是由4字节及32位二进制数组成。通常将其用4个十进制数表示,每个十进制数由小数点分开以表示不同字节数的大小。因为每个十进制数是由一字节及8位二...

    用户5935416
  • Python-SSH日志分析

    由于最近找到了款新游戏,叫 星际拓荒,于是加新功能的计划被稍微延长了那么几天,导致写这段文字的时候已经是凌晨1:45了,不得不说啊这游戏是真好玩 当废人真爽

    Elapse
  • Linux基础(网络配置)

    Ubuntu是一个依赖于网络的系统,没有网何止我们活不了,他也活不下去。那在虚拟机里的Ubuntu要是连不上网了,该怎么办呢?

    用户2617681
  • Linux下fsck.ext4:Unable to resolve问题记录

    在(or type control -D to continue):后面输入root密码后回车

    試毅-思伟

扫码关注云+社区

领取腾讯云代金券