谁能提供这两种算法的一些应用程序，它们可以用于哪些应用程序和哪些应用程序？
问问题
40767 次
6 回答
20
首先研究了最小生成树，以寻找以最小化布线总成本的方式布置电网的方法。在最小生成树中，所有节点（房屋）都将通过电线以最低成本和冗余的方式连接到电源（切断任何电线必然会将电网分成两部分）。
从那以后，这个问题得到了充分的研究，并且经常被用作更复杂算法中的子程序。寻找旅行商问题的近似解的Christofides 算法在关键步骤中使用了它，一些寻找施泰纳树的算法也是如此。
最小生成树也被用于生成迷宫。Kruskal 和 Prim 的算法都以这种方式使用，通常会创建高质量的迷宫。
如果您对最小生成树问题、其应用和算法的完整历史感兴趣，这里有一篇真正优秀的论文，涵盖了所有这些。我强烈建议阅读一下！
希望这可以帮助！
于 2011-09-06T17:18:46.370 回答
4
引用维基百科：
一个例子是一家有线电视公司为一个新社区铺设电缆。如果限制仅沿某些路径埋设电缆，则将有一个图表表示哪些点由这些路径连接。其中一些路径可能更昂贵，因为它们更长，或者需要将电缆埋得更深；这些路径将由权重较大的边表示。该图的生成树将是那些没有环但仍连接到每个房屋的路径的子集。可能有几个生成树。最小生成树将是总成本最低的树。
于 2011-09-06T13:20:27.797 回答
1
首先，您必须了解 Prim 算法和 Kruskal 算法对于在图中查找最小生成树很有用。我能想到的最小生成树的实际应用之一是以最少的成本连接同一家公司的不同办公室。
于 2011-09-06T13:27:10.557 回答
1
Prims 和 Kruskal 算法都用于寻找最小生成树。现在 Kruskal 和 Prims 算法的应用基本上都是 MST 的应用。那么MST有哪些应用呢？
好吧，回答几个，这里有一些你会发现它们可用的领域：
- 如果您想使用高速公路或铁路网络连接多个城市，您可以使用这些算法来找到连接所有这些城市的道路/铁路的最短长度。
- 网络设计- 假设您有一家拥有多个办事处的企业。您必须租用电话线来连接所有这些办公室。因此，您可以利用这些算法找出以最少的电话线连接所有办公室的最低成本。
- 可用于求解旅行商问题。这是使用 MST 的一个非常著名的问题。
- 您想申请一组带有 - 电力、电话线、污水管道的房屋。
- 设计局域网。
于 2019-11-24T19:27:01.397 回答
0
Kruskal 和 Prim 算法的应用经常出现在计算机网络中。例如，如果您有一个带有许多交换机的大型 LAN，那么找到最小生成树对于确保只有最少数量的数据包将通过网络传输至关重要。
于 2014-11-08T15:21:34.510 回答
0
- 拓扑
- 制图
- 几何学
- 聚类
- 路由算法
- 迷宫的世代
- 机械/电气/计算机网络
- 化学中分子键的研究
于 2012-06-09T10:19:21.320 回答