你们中有人知道使用生成树数据结构的任何现实世界应用程序吗？
问问题
10384 次
1 回答
5
在网络中，我们经常使用最小生成树算法。所以问题就像这里所说的那样，给定一个带有加权边的图，找到一棵边的树，它具有满足这三个属性的最小总权重：连接、非循环和由 |V| 组成 - 1 条边。（事实上，三个条件中的任何两个都暗示了第三个条件。）
举个例子，
例如，如果您有一个带有很多交换机的大型局域网，那么找到最小生成树可能会很有用，这样只有最少数量的数据包需要通过网络中继，并且同一数据包的多个副本不会'不要通过不同的路径到达（请记住，任何两个节点仅通过生成树中的单个路径连接）。
其他现实世界的问题包括布置电网，据报道这是 Boruvka 算法的最初动机，它是最早的寻找最小生成树的算法之一。找到最小生成树比找到任何旧的生成树更好，这不足为奇。如果网络上的一棵生成树涉及采用最拥挤、最慢的路径，那么它可能并不理想！
除了计算机网络之外，还有许多其他应用程序，我列出了以下参考资料：
网络设计： - 电话、电气、液压、电视电缆、计算机、道路 标准应用是针对电话网络设计等问题。您的企业拥有多个办事处；您想租用电话线将它们连接起来；并且电话公司收取不同金额的费用来连接不同的城市对。您需要一组以最低总成本连接所有办公室的线路。它应该是一棵生成树，因为如果网络不是一棵树，您总是可以删除一些边并节省资金。
NP-hard 问题的近似算法： – 旅行商问题，Steiner 树 一个不太明显的应用是最小生成树可以用来近似解决旅行商问题。定义此问题的一种方便的正式方法是找到至少访问每个点一次的最短路径。
请注意，如果您的路径只访问所有点一次，则它是一种特殊的树。例如在上面的例子中，16 棵生成树中有 12 棵实际上是路径。如果您有一条路径多次访问某些顶点，您总是可以丢弃一些边来得到一棵树。所以总的来说，MST 权重小于 TSP 权重，因为它是对严格更大的集合的最小化。
另一方面，如果你在最小生成树周围画一条路径追踪，你会追踪每条边两次并访问所有点，因此 TSP 权重小于 MST 权重的两倍。因此，这次旅行是最佳的两倍之内。
间接应用： – 最大瓶颈路径 – 用于纠错的 LDPC 代码 – 使用 Renyi 熵进行图像配准 – 学习用于实时人脸验证的显着特征 – 减少蛋白质中氨基酸测序的数据存储 – 湍流中粒子相互作用的模型局部性- 用于以太网桥接的自动配置协议，以避免网络中的循环
聚类分析： k个聚类问题可以看作是找到一个MST并删除k-1个最昂贵的边。
您可以从此处和此处阅读详细信息，请在此处查看演示。
于 2014-02-09T16:14:18.037 回答