問題:用最少的集合覆蓋所有元素。這是 NP-Complete 問題。
貪心近似:每次選擇覆蓋最多未覆蓋元素的集合。
近似比 = O(log n),其中 n 是元素數量。
伺服器選址是集合覆蓋的特例:
- 元素 = 城市
- 集合 = 每個位置能覆蓋的城市
- 目標 = 最少伺服器覆蓋所有城市
近似比 = 你的解 / 最佳解,越接近 1 越好