算法：Esau-Williams算法

Question

我想问一下Esau-Williams算法可能有用吗？我知道它是用来解决CMST问题的，但我找不到任何可能出现CMST问题的情况。

Answer 1

根据Wikipedia，“CMST问题在网络设计中很重要：当许多终端计算机必须连接到中心集线器时，星形配置通常不是最低成本设计。找到将终端组织成子网的CMST可以降低实施网络的成本。“

Answer 2

顾名思义，CMST代表容量最小生成树，其中每个节点具有有限的连接到其他节点的容量。这使节点根据节点的容量连接到有限数量的其他节点。 通常在任何实际应用中，最小生成树不是唯一的目标。还有很多其他限制，例如，在网络设计中，路由器（节点）的输出端口可以处理的最大数据量是一个容量限制。这标志着启发式算法，如以扫 - 威廉姆斯中储算法的重要性，修改克鲁斯卡中储算法等。 网络一样，它使用的图表，例如物流的任何领域，根据它们的约束可以使用启发式算法，如以扫威廉

Answer 3

CMST可用于诸如决定海上风力涡轮机的电缆布局的情况，其中每个涡轮机必须连接到称为子站的欧几里得空间中的点。我们无法使用最小生成树，因为它对单根电缆上可连接的涡轮机数量具有容量限制。