[轉錄]Re: 演算法問題
※ [本文轉錄自 sorryChen 信箱]
作者: forken (forken)
標題: Re: 演算法問題
時間: Mon Apr 12 03:06:49 2010
※ 引述《sorryChen (陳揚和)》之銘言：
: (不好意思post再這裡,若應該post再其他版上還請版友告知見諒)
: 給定n個數選k個數使其中選中的數之間的最短距離最大化
: 就比如說一個街道上要從n個點中選k個點放垃圾桶
: 要使最近的兩個垃圾桶距離最大化
: 一開始覺得這個是個簡單又典型的問題 但想了兩天除了一個O(n^3k)的DP方法
: 並沒有什麼好的解法... 其他一些想法是..頭尾都一定會選
: 如果可以隨便放的話L/(k-1)的間隔距離放最好, L 為街道總長
: 所以若第二個個點大過L/(k-1)則就一定會要選 因為選的時候不會造成瓶頸
: 但若小於則不一定是最好的 因為可能會造成瓶頸...
: 不知道版友們能不能指導一下
哈囉!揚和, 我是效飛,
我想這個問題應該可以在用類似 binary search 的方式
在 O(n log n) 解決,
Preprocessing:
先把 n 個數 sorting into (a1, a2,..., an)
Verification:
考慮如果給一個 value s，
我們要如何在 O(n) 驗證是否有一種選法,
可以使得 max min {任兩個選中的數} >= s?
首先 a1 一定要選，所以設 b1 := a1,
第二個數 b2 := min ai such that ai-b1>=s
第三個數 b3 := min ai such that ai-b2>=s
...
依此類推
如果到 bk 都存在，則表示{b1,...bk} 為一種選法，
可使得 max min{任兩個選中的數} >= s。
反之如果某個 bi 不存在，
則表示不存在一種選法使得 max min{任兩個選中的數} >= s。
Search:
我們知道如何驗證是否有一種選法，
可以使得 max min{任兩個選種的數} >=s，
剩下的問題就是找到最大的 s。
總共有大約 n^2 個可能的 s，
所以用 binary search 總共會有 log (n^2) = O(log n) 個 iterations，
每個 iteration 所需的驗證時間是 O(n)，所以總共的時間是 O(n log n)。
-------------------------------------------------------------------
但還存在一個問題，
就是我們如何在所有可能的 s 中進行 binary search?
(如果真的把所有可的 s 都列出，時間至少就是 Omega(n^2))
這可以利用 Cartesion Sum selection 做到，
關於 Cartesion Sum selection 可以參考:
"Selection in X + Y and matrices with sorted rows and columns"。
IPL, Volume 20, Issue 1, 2 January 1985,
這個方法不是很漂亮，畢竟還是利用到 cartesian sum selection，
但應該可以解決你的問題。
如果對 complexity 要求不那麼嚴格，也可以把所有 n^2 種 s 都列出，
做 sorting 後進行 binary search，
這樣時間就變成 O(n^2 log n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.126.169.230
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 207.151.231.39
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
