算法：Esau-Williams算法

Question

我想問一下Esau-Williams算法可能有用嗎？我知道它是用來解決CMST問題的，但我找不到任何可能出現CMST問題的情況。

Answer 1

根據Wikipedia，「CMST問題在網絡設計中很重要：當許多終端計算機必須連接到中心集線器時，星形配置通常不是最低成本設計。找到將終端組織成子網的CMST可以降低實施網絡的成本。「

Answer 2

顧名思義，CMST代表容量最小生成樹，其中每個節點具有有限的連接到其他節點的容量。這使節點根據節點的容量連接到有限數量的其他節點。 通常在任何實際應用中，最小生成樹不是唯一的目標。還有很多其他限制，例如，在網絡設計中，路由器（節點）的輸出端口可以處理的最大數據量是一個容量限制。這標誌着啓發式算法，如以掃 - 威廉姆斯中儲算法的重要性，修改克魯斯卡中儲算法等。 網絡一樣，它使用的圖表，例如物流的任何領域，根據它們的約束可以使用啓發式算法，如以掃威廉

Answer 3

CMST可用於諸如決定海上風力渦輪機的電纜佈局的情況，其中每個渦輪機必須連接到稱爲子站的歐幾里得空間中的點。我們無法使用最小生成樹，因爲它對單根電纜上可連接的渦輪機數量具有容量限制。