Greedy

Greedy Method

中文譯作「貪心法」,以Incremental Method或Iterative Method來製造答案的方法,大致上分為兩類:

一、填答案(Incremental Method):
  從沒有答案開始,逐步填滿答案,
  每次根據現況算出一部分答案,直到答案都填滿為止。

二、改答案(Iterative Method):
  先隨便弄個答案,逐步修飾答案,
  每次根據現況修飾一部分答案,直到答案夠漂亮為止。

用這般投機取巧的手段,自以為能獲得正確答案,實在是太貪心了,故得名「貪心法」。

Greedy性質

當一個問題真的可以這樣胡搞瞎搞弄出正確答案,就稱這個問題「有Greedy性質」。有Greedy性質的問題,能以Greedy Method求出正確答案。

天底下哪有這麼碰巧的問題?就是有這麼碰巧的問題!想盡辦法利用這種碰巧,把正確答案算出來,這真的是貪心十足了,不愧名為「貪心法」。

用Greedy Method設計演算法時的步驟

1. 觀察問題特徵,擬定一個填答案\改答案的原則。
2. 隨便挑幾個特例,手算一下。如果答案都對,就採用此原則。
   (也可以嘗試證明此原則必定正確。)
3. 實作程式碼,把答案算出來。

觀察問題所展露的性質,舉幾個單純的例子,然後根據這些例子,猜測一個簡單的計算方法。若這些單純的例子能算出正確答案,就大膽假設複雜的例子可以用一樣的方式,漸進地算出正確答案。

範例:Coin Change(找零錢)

你去商店買東西,你掏出了一張一百元,買了一包23元的零食。櫃員須找零錢給你,但是你希望櫃員找給你的硬幣數目越少越好,如此口袋會輕一點。那麼櫃員會給你幾個硬幣呢?

填答案的原則是:先給你面額較高的硬幣。

Matroid

要證明一個問題是否有Greedy性質,數學領域已經建立一套稱做「Matroid」的數學模型,可以用於證明。這方面的知識頗為艱深,故此處省略之。

UVa 120 311 410 514 538 668 757 10020 10037 10148 10249 10382 10440 10602

Stable Marriage Problem

穩定婚姻問題

一家婚友社將N位男士與N位女士進行媒合,一位男士配一位女士,共要撮合N對婚姻。

每位男士各自擁有一個好感度列表,對N位女性各以1到N的數字進行排名。每位女士各自亦有一個好感度列表,對N位男性各以1到N的數字進行排名。

媒合時必須避免,不是伴侶的某男某女,出現婚外情的傾向:「男對女說:我愛你比愛我妻子還深。同時女對男說:我愛你比愛我丈夫還深。」請找出適合的配對方式。

演算法(Gale-Shapley Algorithm)

這個問題已被證明恰有兩解(或一解,當此兩解相同時),其中一解稱為男士最佳解,另一解則稱為女士最佳解。男士最佳解的演算法如下:

1. N位男士各自向自己最喜愛的女士求婚。
2. N位女士各自從自己的求婚者中,挑最喜愛的那位男士訂婚,但是往後可背約。
   沒有求婚者的女士,就只好等等。
3. 失敗的男士們,只好各自向自己次喜愛的女士求婚。
4. N位女士各自從自己的求婚者中,挑最喜歡的那位男士訂婚,但是往後可背約。
   已訂婚卻有更喜愛的男士求婚的女士,就毀約,改為與此男士訂婚。
  沒有求婚者的女士,就只好再等等。
5. 重複3. 4.直到形成N對伴侶為止。

男士不斷降格以求,女士不斷水漲船高,最後達成平衡。

女士最佳解的演算法則改為由女士主動求婚即可。

時間複雜度是O(N^2)。