荷蘭國旗問題 The Dutch National Flag Problem(中)

上回說到,為解荷蘭國旗問題,我們至少有兩種不變量可選。一是把未知區段放旁邊:一是把未知區段夾在某兩色之間:
該用哪個比較好呢?

答案是:用兩者都寫得出可運作的程式,但後者好寫得多。原因是:未知區段是我們的工作區,而我們有三種顏色要搬來搬去,把未知區段放在旁邊會使得某些搬移相當不便。

因此以下我們用第二個不變量,寫成邏輯式子是這樣的:

M ≤ r ≤ w ≤ b ≤ N ∧
(∀i : M ≤ i < r : red(i)) ∧
(∀i : r ≤ i < w : white(i)) ∧
(∀i : b ≤ i < N : blue(i))

最初若把 r, w, b 設為 M, M, N,不變量自然成立 --- M ≤ i < r, r ≤ i < w, 和 b ≤ i < N 三個區段都是空的,整個陣列都視為灰色的未知區。接下來我們希望在一個迴圈中逐漸縮小 wb 的差距。當 w = b 時,陣列就照我們想要的顏色順序排好了。

迴圈中應該作什麼呢?既然目標是把 b - w 變小,關鍵的元素可能是 a[w]a[b-1]. 也許我們可以先看看 a[w] 是紅、白、或藍色,分三種情況處理:或著我們也可檢查 a[b-1] 的顏色。個中優劣只有試過才知道了。依後見之明,我們發現先檢查 a[w] 較好。另一種選擇待會兒再談。

所以,程式架構大約是這樣:

   r, w, b, := M, M, N
   { Inv: M ≤ r ≤ w ≤ b ≤ N ∧ Pr ∧ Pw ∧ Pb, bound: b - w }
 ; do w < b →
     if red(w)   → Sr
      | white(w) → Sw
      | blue(w)  → Sb
     fi
   od
   { M ≤ r ≤ w ≤ b ≤ N ∧ Pr ∧ Pw ∧ Pb ∧ b = w }

其中 Pr, Pw, 和 Pb 分別是關於三個顏色之條件的簡寫:

Pr ≡ (∀i : M ≤ i < r : red(i))
Pw ≡ (∀i : r ≤ i < w : white(i))
Pb ≡ (∀i : b ≤ i < N : blue(i))

我們還需找出 Sr, Sw, 和 Sb 分別該是什麼。

white(w) 的情形最簡單:把 w 遞增之後不變量仍然滿足。Sw 可以是 w := w + 1.

blue(w) 的情況呢?若把 a[w]a[b] 交換,我們可把 b 遞減,不變量也剛好滿足。Sb 可以是 swap(b,w); b := b - 1.

最複雜的是 red(w) 的情況。我們可把紅元素換到後面去,但之後為了滿足不變量,我們得把 rw 都遞增。

總結下來,我們的程式是:

  r, w, b, := M, M, N
  { Inv: M ≤ r ≤ w ≤ b ≤ N ∧ Pr ∧ Pw ∧ Pb, bound: b - w }
; do w < b →
    if red(w)   → swap(r,w);  r, w := r + 1, w + 1
     | white(w) → w := w + 1
     | blue(w)  → swap(b,w);  b := b - 1
    fi
  od
  { M ≤ r ≤ w ≤ b ≤ N ∧ Pr ∧ Pw ∧ Pb ∧ b = w }

然而,上面的圖片其實遺漏了許多情況。例如,在 red(w) 的情形中,如果 b = w ,程式還會對嗎?我們得切記畫圖僅可幫助理解,程式的推導驗證還是得回到形式系統來作。

red(w) 的情況為例,我們得證明:

  { M ≤ r ≤ w < b ≤ N ∧ Pr ∧ Pw ∧ Pb ∧ red(w) }
  swap(r,w)
  { (M ≤ r ≤ w ≤ b ≤ N ∧ Pr ∧ Pw ∧ Pb)[r, w := r + 1, w + 1] }
; r, w := r + 1, w + 1
  { M ≤ r ≤ w ≤ b ≤ N ∧ Pr ∧ Pw ∧ Pb }

據我所知,在國內只有 FLOLAC 程式建構課教過這種證明(如果你會的話,來認識一下吧!),所以除非有人要求,這裡就只透露我們得分出 r = wr < w 的兩種情形,不深入談細節了。

這是一個 O(N-M) 的程式。如果三色數量相同,我們平均需要大約 2(N-M)/3 次交換。如果我們當初選擇從檢查 a[b-1] 開始,也可做出一個稍微不同的程式,但平均需要的交換次數增加到 N-M 次。

下圖是排序 [w,r,b,b,r,b,r,r,b,r,r,w,r,r] 的例子。SrSb 兩種情況的交換分別用 表示。這個例子中,陣列有 14 個元素,而我們用了 13 次交換。

This entry was posted in 未分類. Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>