廣播中的近似算法

Question

對於braodcasting算法的近似解決方案意味着什麼... 我一直在研究一種算法，它說它有一個12近似的解。 是什麼實際上意味着.. 任何人可以幫我...

Answer 1

簡單（ISH）的話則意味着該算法保證產生的結果是最佳的解決方案的12倍之內。

對於您的示例，如果目的是爲了減少廣播延遲，那麼12倍因子近似最遲會比最佳解決方案的延遲差12倍。

之所以會出現一個不好的比率，實際上可能實際上是有用的是，它不可能以任何實際的方式來實際計算最佳值，或者對於特定的應用程序來說可能會花費太長時間 - 因此最好的近似值可能非常有用。

值得注意的是，「因素12」是最糟糕的情況 - 即保證12倍的最佳效果不會更糟。實際上，結果往往比這種最壞的情況好得多。