Algorithm筆記 8 - 小孩分群演算法

分群問題

如何將一群n個小孩根據某條件p來分成最少的群呢?

最直接(笨)的方法就是把所有的可能分法都窮舉出來，亦即找出一個set的所有subset，當然空集合是一個合法的subset。

最小限度來說，如果要把n個物體分到相異2群中 (某群可以完全是空)，至少就要花上2^n次方次的對條件p的篩選，因為對每個小孩來說都有2種選法，所以總共是2^n個選法，也就是running time O(2^n)。

然而分成相異兩群的所有方法只是窮舉所有分群法中的一個subset，所以O(2^n)是窮舉法的下限running time，也就是OMEGA2(^n)。

這是一個exponential (變數n在指數) running time algorithm，執行時間隨n變化將極為陡峭劇烈，我們必須尋求更好asymptotic running time的方法。

Greedy approach

解決問題通常將之轉成數學model，這有助找出特性與轉化成簡單問題的方式。

假設這個條件p為 每群中的小孩年齡相差不能超過一歲

一個數學上的模型是轉成數線，數線上的點(值) 代表每個小孩的年齡:

同群中任何兩人不能相差超過一歲的限制，就用一個長度為1的線段來表示，所以每個線段涵蓋的點，就是一個滿足條件p的同一群人，以下是其中一種分法 (分成四群):

如果一個點同時被兩個線段涵蓋，那並不構成model上的任何意義，因為此點只會屬於其中一群。

當然也可以這樣分 (更好一些，分成三群):

能不能有一個greedy algorithm?

首先我們必須要找出一個safe move，也就是某個optimal solution的第一步，假設以下敘述是一個safe move:

長度為1的線段最左緣，如果重合了最左邊的點(年紀最小者)，則這是一個safe move。

記得我們必須證明safe move成立，否則不能使用greedy approach，因為不見得是optimal solution。如何證明上述描述是一個safe move?

greedy algorithm

如果我們把任意一個optimal solution的第一條線段 (group 1)的左緣，拉到與數線上最左邊的點重和的話，原本在線段1涵蓋的點的總數不會改變，所以group 1的人數也不會改變:

上圖中第3個點雖然同時被涵蓋在第一條紅線和第二條藍線中，但是並沒有什麼影響，它仍然屬於group 2的點。 由於紅線位置的改變並不影響optimal solution最後的output，所以這個移動方式是一個optimal solution，所以是一個safe move。

有了safe move，根據greedy algorithm的實作方式，我們把剃除掉第一群的點 (上圖紅線中的前兩個點)，剩下的所有點就構成了一樣的分群問題，就是一個subproblem。

所以這是一個greedy algorithm可以找到optimal solution的問題。演算法如下:

首先所有的小孩的年紀被map到一個sorted array{x1, x2, ... , xn}，R是最後的分法集合，指標i從第一個點x1開始檢查。

先列出先把這個線段的涵蓋範圍l和r設定為x1和x1+1，+1的意思是線段長度。
然後inner while loop找出下一個xi，使得此xi > r，亦即找出下一個不在此線段涵蓋範圍內的點，當作下一個subproblem的最左邊的點。

pseudo-code大概就這樣，來分析它的running time。

Polynomial time 

這個演算法從頭到尾走了n次，所以是O(n)，不過這是建立在我們先把x1..xn排序過的前提下，如果沒有排序的話，必須要進行排序，則目前已知最好的排序演算法的running time為O(nlogn)。

所以整體running time = O(nlogn) + O(n) = O(nlogn)。

相對於OMEGA(2^n)的 naiive algorithm的改善相當的大!