伺服器選址 - Approximation ← 返回遊戲列表
在地圖上點擊放置伺服器(紅點),目標是用最少伺服器覆蓋所有城市。
覆蓋半徑 = 80 像素
城市
伺服器
已覆蓋城市
0
伺服器數量
0 / 0
覆蓋城市
?
最佳解 (估計)
-
近似比

集合覆蓋問題 (Set Cover)

問題:用最少的集合覆蓋所有元素。這是 NP-Complete 問題。

貪心近似:每次選擇覆蓋最多未覆蓋元素的集合。
近似比 = O(log n),其中 n 是元素數量。

伺服器選址是集合覆蓋的特例:
- 元素 = 城市
- 集合 = 每個位置能覆蓋的城市
- 目標 = 最少伺服器覆蓋所有城市

近似比 = 你的解 / 最佳解,越接近 1 越好