Modeling

Modeling

觀察問題的性質,轉化原問題,將之映射到另外一套恰如其分又耳熟能詳的模型(系統)上,或者是自行編出一套別出心裁的模型(系統),以便進行操作、解決問題。

換個方式說。觀察問題的性質,並選擇一套恰如其分又耳熟能詳的模型(系統),或者是自行編出一套別出心裁的模型(系統),套用在這個問題身上,以便進行操作、解決問題。

方才的釋義似乎太抽象。舉個實例:Joseph Problem有一種解法是把問題映射至queue,數數殺人變成了一連串的push和pop──該映射就是Modeling。再舉一例:State Space Search將狀態串聯,映射至圖,以圖論演算法來搜尋答案──該映射也是Modeling。

Simulation v.s. Modeling

Simulation與Modeling息息相關。Simulation是嘗試去模擬各種行為,Modeling則是統整行為後,歸納並設立一套固定模式,以後便可以此模式來模擬類似問題。

Lights Out Puzzle
(Minimum All-Ones Problem)

點燈遊戲

此遊戲的目的是操作開關以熄滅(或點燃)所有燈。按下一個燈上的開關後,會連帶影響自己及其四周的燈,亮變暗、暗變亮:http://oddest.nc.hcc.edu.tw/math171.htm

這篇文章將介紹最廣為人知的解法,是以線性函數當作模型:http://mathworld.wolfram.com/LightsOutPuzzle.html。以下文章只點到為止。

點燈遊戲的性質

無論開關們同時按和分開按、先按和後按,其造成的影響都一樣。
一個開關按兩次,跟按零次一樣,會相互抵銷。按開關次數可以模二。按開關可想成是與1做xor。
一個燈受開關們影響兩次,會相互抵銷,變成沒有影響,不論燈經過了任何點燃還是熄滅。

確立模型

該問題得以函數當作模型來表示之:f(按下的開關) = 盤面,f就是遊戲規則,是固定的。只要求出f的反函數,就可以用盤面求得按下的開關。巧妙的是,f是線性函數,故可以解聯立線性方程式來找到反函數。

加法封閉性:f(同時按下開關A和B) = f(按下開關A) + f(按下開關B),加法定義為xor。
倍率封閉性:f(按下開關A一共k次) = k * f(按下開關A),k模二後,乘法即可定義為and。

附帶一提,有一種常見的函數模型是:g(舊盤面) = 新盤面,g為一種按開關的方式。這種模型更加常見,但這裡並不適用此模型來解決問題。

解聯立線性方程式

要解聯立線性方程式,可以用高斯消去法或其他解聯立方程式的方法:http://mathworld.wolfram.com/LinearAlgebra.html。解聯立方程式是中級學校的數學教材,故省去不提。

時間複雜度為O((H*W)^3),H和W分別為盤面的長和寬,而三次方是高斯消去法的時間複雜度。

點燈遊戲必有解

解聯立方程式之時,同時也可以驗證出f必有唯一解。f有唯一解表示其反函數也為唯一解,或說是值域和對應域中的元素一一對應;這也就是說,一種盤面必恰好對應一組操作方式。無論燈是如何亮著的,必恰有一組獨特的操作方式,能熄滅(點燃)所有燈。點燈問題必有解。

做做題目吧。

UVa 10309

System of Difference Constraints

System of Difference Constraints in Linear Programming

問題:給定變數x1到xN,並給定一些xi-xj≤c的式子,做為條件限制。請判斷有沒有解,如果有解就求出其中一組解。

最短路徑

這個問題可以巧妙的轉換成最短路徑問題。x1到xN看做是圖上的N個點,一條xi-xj≤c的限制式子看做是一條xj到xi的邊,其權重是c。

如果無解,那麼圖上有負環。如果有解,那麼圖上各點的最短路徑長度就是其中一組解。為了讓圖上各點都有最短路徑長度值,可參考Johnson's Algorithm的做法。

UVa 515