程式設計的古老技巧之一,就是分治法(Divide and conquer),也就是將一個問題不斷地分解為許多子問題,直到能見到子問題的解決方式,在個別擊破各個子問題後,最後整體問題也就隨之解決了,如果那些演算法文件或書籍上的題目過於抽象,何妨具體地從OpenSCAD建模來學習分治法,讓分治法成為一種思考習慣。

對分治法的迷思

雖然說分治法是個古老的技巧,不過,在學習分治法的過程中,從書籍或文件上看到的案例,多半已經告訴你子問題是長什麼樣子,以及應當如何解決各個子問題,也就是說,看到的其實已經是「結果」。然而,在一個問題的分治法成功之前,拆解子問題的過程中,可能有著無數次的失敗思路,而這個「過程」才是分治法中真正該探討學習的。

只是有時候問題本身過於抽象,以致於子問題難以識別;或者是識別出錯誤的子問題,以致於解決了這類子問題,整體問題得到了錯誤的答案;甚至是識別出的子問題其實還不夠具體,需要更進一步分解為更小的子問題,才足以看到具體的做法。

更糟的是,雖然不少演算法書籍上,試圖以虛擬碼來解說問題的解法流程,然而,不少人還是將分治法與程式設計甚至語言畫上等號。實際上,許多領域在設計時,都用得到分治法。

以人體素描為例,想要繪製一個人體時,其實腦袋中構思的並不是整個人體曲線,而是先找出一個長度基準,像是身體會是七個頭的高度,而臉寬會是五個眼睛的長度等,接著使用圓、三角等基本圖案來畫出骨架,逐一勾勒出整個人體。

如果從程式設計的角度來學習分治法,那麼命令式的語言往往也加深了它的複雜性,因為很容易就寫出程式碼的邏輯泥塊,最常見的是一個變數貫穿整個函式,而一個函式的程式碼又臭又長,這麼一來,也許在撰寫的過程中,確實曾經試圖解決各個子問題,然而,最後的程式碼結果卻根本就看不出子問題的界限。

如果使用純函數式語言的話會好一些,因為語言本身在變數不可變動等特性的強制下,就算還不清楚子問題,還是不得不寫出一個又一個子函式,有時還不得不被迫寫出一個又一個的遞迴函式。

不過,將遞迴當成分治法的必然形式之一,本身也是個迷思,遞迴本身的意義是,子問題接下來的連續切分有著一致的關係,目前的函式本身正巧可以解決下個被切分的子問題,因此與其再使用迴圈來實作,不如直接呼叫函式本身來得直接。

具體地拆解子模型

分治法實際上並不限於程式設計,人體素描是一個實例,類似地,3D建模也是其中之一,也因此我在〈3D建模與程式設計〉中,就談過3D建模的分而治之,無怪乎我初次接觸3D建模時,就察覺它與程式設計有著極高的相似性,也從而後來轉向了程式建模的路線。

學習3D建模,一開始就得使用分治法,因為無論是哪個3D建模軟體,都提供有限的基本模型元件,因此,想要創造出心中想要的模型,一定得將模型分解,直到能用基本的模型元件組合起來為止,對於簡單的模型來說,以這樣的思路來察覺子模型,就是件很具體的事。舉例來說,面對一個簡單的平面愛心,不難觀察出,它可以使用矩形與圓形來組合出來。

當然,還是有複雜的模型,以愛心為例,也有各種不同的愛心,也有著各種不同的數學公式可以來繪製愛心,實際上,看似複雜、抽象的數學公式,本身也是分而治之的成果,也就是將子問題分解到極緻的一種表現,每個座標點實際上是由許多子數學公式的交互作用而成。

如果想要創造立體的愛心呢?既然會創造平面愛心了,那麼一層一層從小到大、再從大到小疊起來,只要每層夠薄,看起來就會是圓滑而不是層次分明的立體愛心了,像這樣從簡單的模型開始,試著具體地拆解子模型,然後逐漸挑戰更複雜的模型,在習慣這樣的思路過程之後,每每看到一個立體物件,就會開始自然地想要去分解它了。

結合OpenSCAD語言特性

如果學習分治法的目的是想應用在程式設計上,而3D建模也對於學習分治法有利,那麼直接結合兩者益處的方式,就是使用程式設計來進行3D建模,方才也提過,如果使用純函數式語言來學習分治法會好一些,那麼,使用函數式為典範的OpenSCAD,來進行程式設計3D建模,就更能一舉三得了。

在程式設計上強調抽象化,建立函式是一種抽象化,因為隱藏了流程實作細節。而在使用OpenSCAD建立子模型時,往往是從定義一個模組開始,舉例來說,要建立一個愛心模型,就算還不清楚愛心怎麼用矩形、圓形實作出來,也建議先定義一個heart模組,然後呼叫這個heart模組,接著,才是在heart模組中建立矩形、圓形等子模型,如果需要任何的數字,建議定義一個變數或參數來代表它,不要有任何的魔法數字(Magic number)。

在學習分治法的過程中,實際上,如何發現子問題,以及如何切除子問題之間的相依性,才是重點。定義模組本身,就是在切除相依性;而使用變數或參數來代表數字,而不是使用魔法數字,這也是在切除相依性,一個模組可以透過指定不同的參數值,而自由變化且不變形的情況下,才能被看成是獨立解決了一個子問題。

如果定義出來的子模組都能獨立運作,對想設計的整體模型來說,模組名稱就只是個抽象的介面,例如呼叫heart(height),就是建立一個高度為height的愛心,將來如果想改變愛心的實作,只要在heart模組中進行,然後整個模型就會有不同的風貌了。

有時,子模型會呈現出一致的規律性,特別是想設計出雪花、蜘蛛網、禪繞畫,甚至是足球面這類的模型時,而這就是使用程式實作最能派得上用場的時候。

然而,遞迴不是唯一的做法,在函數式語言中會有list comprehension語法,OpenSCAD中也有類似語法,使用它來實作,往往比較簡單而直覺,更能呈現子模型一致的規律性,突顯分而治之的意圖。

先建立子模型、再組建出整體模型,基本上,是一種分治法實作時由下而上(Bottom-up)的方式,另一個實作方向則是由上而下(Top-down)。

舉例來說,建立一個足球多面體(截角二十面體),可以在設計時抽象地定義:這邊需要五角形或六角形的東西,在OpenSCAD中可以使用children()來表示;至於這五角形或六角形的東西,未來可能是指定是五角迷宮或六角迷宮,甚至是五角拼圖或六角拼圖片。這不就很像是某些語言中多型設計的概念嗎?

讓分治法真正成為一種習慣

當然,使用OpenSCAD從事程式3D建模,並不是最終的目的,而是在這個過程中,培養出看到問題,自然而然地去分解它的習慣,並且將這種習慣,帶回自己平常的程式設計工作之中,甚至是日常解決問題的方式之中。

一個有趣的練習是,假以時日重新回去看看那些討論演算法的相關文件上的問題,如果忘了當中對問題的解決方式的話更好,試著用建立起來的分治法習慣去思考,嘗試自行解決,建立自己的思路,這會是種截然不同的體驗。

作者簡介


Advertisement

更多 iThome相關內容