location allocation problem

location allocation problem(facility location problem)

給定許多個地點,設立p個聯絡站,使得每一個地點皆可被其中一間聯絡站聯絡到,而且越有效率越好。

深入地定義「效率」的意義,得以細分許多問題:

p-median problem:令聯絡站離各地點的距離總和最小。
p-center problem:令聯絡站離各地點的距離最大值最小。
uncapacitated facility location problem:在各地設立聯絡站需要成本,
但建立聯絡站後會從周遭地點獲得利益,令設立聯絡站後利益最大。
range assignment problem:令各地點離聯絡站的中繼點不超過一定數量。

這些問題在現實生活中的應用,例如超商的物流通路、有線電視的纜線鋪設、基地台的設立位置等等。可惜這些問題已經被證明是NP-hard問題,無法快速得到精準解答。

以下只討論一維版本。所有的地點和連絡站都在數線上。

p-median problem

p-median problem

給定許多個地點,設立p個聯絡站,使得每一個地點皆可被其中一間聯絡站聯絡到。令聯絡距離的總和最小。

此處討論一維版本,地點和連絡站落於數線上。

簡化問題、觀察問題:只有一個連絡站

將聯絡站放在中位數是最好的。如果中位數是在兩個位置中間,那麼聯絡站可以游移於兩個位置之間、其上,不會改變聯絡距離的總和。所有的聯絡站都可以挪至地點之上!

證明不難。試著移動聯絡站,讓各個地點的聯絡距離此消彼長,觀察一下就會明白了。動手試試看吧!

另外也得到一個重要的結論:所有的聯絡站都可以挪至地點之上,而不會改變聯絡距離的總和。

簡化問題、觀察問題:只有一個地點

將全部的聯絡站放在該地點上是最好的。

聯絡站全部疊在一起,有摩肩接踵、水洩不通的感覺,理當好好分配才對。說到分配,如果聯絡站數量大於等於地點數量,只要將聯絡站安排在各個地點上,聯絡距離的總和就是零了。

簡化問題、觀察問題:地緣

為了拉近聯絡距離,所有地點都會連向最近的聯絡站,而不會有捨近求遠的情形。換個觀點來看,一個聯絡站只會連向鄰近的地點,而不會有捨近求遠的情形。

p-median problem可以重新想成:依照地緣,所有地點分配成p個區域,每一區自行設立一個聯絡站,位於中位數,可挪至鄰近地點。

至此,p-median problem就成了如何分區的問題。

簡化問題、觀察問題:分區

如果有地點選擇聯絡站時捨近求遠,表示這種分區方式不好。

各個區域之間相鄰越遠越好?大家自行觀察看看吧。

動態規劃

聯絡距離的總和,可以以區為單位,分別計算,最後再統計——這就是在分割問題。

拿掉最邊邊的一區、拿掉該區的聯絡站,如此便縮小了問題範疇,讓小問題與原問題類似。接著窮舉該區的各種大小,求得遞迴式。

注意別讓剩下來的地點太少、剩下的聯絡站太多,而導致連絡站重疊。妥善分配重疊的聯絡站,一定能使聯絡距離的總和更小。沒有必要枚舉出讓聯絡站重疊的分區方式。

f(p, n) = 
 ⎧ min( f(p-1, p-1) + d(p  , n) ,
 ⎪      f(p-1, p  ) + d(p+1, n) ,
 ⎪      ...                     ,
 ⎨      f(p-1, n-2) + d(n-1, n) ,
 ⎪      f(p-1, n-1) + d(n  , n) )  if p < n  && n >= 0
 ⎪
 ⎪ 0                               if p >= n && n >= 0
 ⎩ +inf                            otherwise

p:已設立了p個聯絡站。
n:已涵蓋了第1個到第n個地點。
f(p, n):設立p個聯絡站,涵蓋第1個到第n個地點時,其聯絡距離的總和。
d(i, j):第i個地點到第j個地點所構成的區域,其聯絡距離的總和最小值。
         可利用中位數算得。

N為地點個數,P為聯絡站個數。總共O(NP)個子問題,計算一個子問題需時O(N),時間複雜度O(N²P)。

動態規劃:monotonicity

不難發現,分界線位於最適中、最均衡的位置,讓聯絡距離的總和最小。

觀察地點逐步增加的問題們。最佳分界線漸漸右移。

觀察聯絡站逐步增加的問題們。最佳分界線漸漸右移。

因此我們不必窮舉所有的區域大小!但是時間複雜度仍是O(N²P)。

UVa 662

動態規劃:convex hull

採用convex hull加速,斜率皆是1,可視作deque加速,時間複雜度O(NP)。

p-center problem

p-center problem

給定許多個地點,設立p個聯絡站,使得每一個地點皆可被其中一間聯絡站聯絡到。令聯絡距離的最大值最小。

也可以想做是:各個聯絡站各自使用一個圓,以自己為圓心,向外擴張以包住其負責的地點,然後讓最大的圓的半徑越小越好。

p-center problem的主要應用是設立基地台。基地台放送電波,地點距離越遠,就需要越多能量、耗費越多電能;跟地點個數無關。為了節省電能,所以要適當的安排基地台的位置,縮短電波的放送距離。

此處依舊討論一維版本。

簡化問題、觀察問題:只有一個連絡站

聯絡站放在相離最遠的兩個地點的正中央是最好的。應該不用證明了吧?

其他性質皆與p-median problem類似,不再複述。

p-center problem可以重新想成:依照地緣,所有地點分配成p個區域,找出最寬的區域,其寬度的一半,即是答案。

簡化問題、觀察問題:分區

p-center problem只關心最寬的區域,其餘區域的寬度根本無所謂,不要超過最寬的區域就好了。

動態規劃:monotonicity

p-center problem特性更強。分界線往右移動,一旦左方最寬的區域的寬度(的一半),大於等於右方區域的寬度(的一半),分界線就沒有必要繼續往右移動。往右移動只會讓答案更大。

p-median problem僅掌握分界線的起點。p-center problem同時掌握起點與終點,時間複雜度O(NP)。

此技巧尚無正式名稱,英文網路稱作「divide-and-conquer optimization」。

試誤法:窮舉最寬的區域的寬度

p-center problem只關心最寬的區域。這種情況下,可以直接令每個區域都一樣大,跟最寬的區域一樣大,從第一個地點開始分區,儘量涵蓋越多地點。若能涵蓋全部地點,表示此寬度可行。

「最寬的區域」寬度適中,區域數量正確,可能是答案。

「最寬的區域」寬度太大,區域數量太少,可能是答案。

「最寬的區域」寬度太小,區域數量太多,不可能是答案。

寬度總共O(N²)種,驗證一種寬度需時O(N),時間複雜度O(N³)。

或者實施排序、二元搜尋,時間複雜度O(N²logN)。

或者length(i,j)是已排序矩陣,樓梯搜尋,時間複雜度O(N²);二維二元搜尋,時間複雜度O(NlogN)。

或者寬度取實際數值。下限是0,上限是最遠的兩個地點的距離L。時間複雜度O(NlogL)。

UVa 714 11413 907

p-coverage problem

p-coverage problem

每個地點有半徑、支出、收入。連絡站建好後,涵蓋範圍為半徑、涵蓋到的地點有收入、沒涵蓋到的地點須支出,令總金額最高。

word wrap

word wrap

一大段英文,適度換行,讓文字不超過紙張邊界。

為了美化版面,行末留白越少越好。

自訂一行留白代價,例如留白長度的平方。

統計各行留白代價,例如總和越小越好。

簡單起見,簡化細節:一、假設字母等寬。二、假設字母寬度是基本單位。三、假設頁面寬度是字母寬度的整數倍。

簡單起見,實施限制:一、單字不能從中切開換行。(實務上,多音節單字可以利用hyphen換行。)二、標點符號貼緊單字尾端。(實務上亦如是。)三、同行單字之間相隔一格空白。(實務上是行中均勻留白,而不是行末留白。)

現代文書編輯軟體退化成古代文字編輯器。

貪心法

留白代價是每單位均等,貪心法得以派上用場。

單字盡量往前擠,擠不下就換行。時間複雜度O(N)。

動態規劃

留白代價是特殊的公式,貪心法不管用。

事先計算總行數P,問題化作「所有單字分成P行」。問題等價於location allocation problem,留白代價宛如聯絡距離。

從最後一行的地方分開,化作兩串單字。開頭單字擠入前面幾行,尾端單字擠入最後一行,考慮所有可能的單字數量。

先枚舉行數,再枚舉最後一行有多少字數。時間複雜度O(N²P)。空間複雜度O(NP)。調整計算順序,空間複雜度降為O(N)。

f(p, i) =  min  { f(p-1, j) + cost(j+1, i) }
         j=0⋯i-1

where cost(a, b) = penalty(S - length(a, b))

f(p, i):前i個單字擠入前p行的代價。
cost(a, b):第i個單字到第j個單字,擠入同一行,其留白代價。
length(a, b):文字長度,第i個單字到第j個單字。
penalty(x):留白代價,當留白長度是x。(當x是負值,則代價無限大。)

動態規劃:降維

要讓留白代價盡量小,就要讓行數盡量小。也就是說,總行數是明確數值,無須更動。

任意一串單字,總行數都是明確數值。遞迴公式得以省略行數。

換句話說。變數i的每一種數值,都可以求得明確數值p。有i就不必有p,於是省略變數p。

f(i) =  min  { f(j) + cost(j+1, i) }
      j=0⋯i-1

f(i):前i個單字的留白代價總和。
cost(a, b):第i個單字到第j個單字,擠入同一行,其留白代價。

時間複雜度O(N²)。空間複雜度O(N)。

所有N個單字通常無法擠入同一行。時間複雜度寫成O(N²),其實不太精準。令最多連續M個單字擠入同一行,時間複雜度寫成O(NM),變得比較精準。

UVa 709 848 400

動態規劃:unimodal function

留白代價恰是凸函數。兩個凸函數相加仍是凸函數。一個問題的候選解大小,恰巧形成凸函數(單峰函數)。各個問題的最佳解位置(山谷位置),恰巧遞增(往右移動)。用同一條掃描線尋找山谷。【尚待確認】

時間複雜度O(N)。空間複雜度O(N)。

動態規劃:totally monotone matrix

時間複雜度O(NlogN)。本題大可不必採用如此複雜的解法。

Zuma game

Zuma game【尚無正式名稱】

逐步消去一連串同色彩珠,找到步驟最少的消除方式。

據說時間複雜度O(N)。如果你會,麻煩教我。

問題分成兩種情況。一、可以分段處理:即是word wrap。二、無法分段處理(連續combo):遞迴求解。

UVa 10559 11523