Yukuan's Blog: OO

Showing posts with label OO. Show all posts

Tuesday, February 25, 2003

又遇 N Puzzle

針對 N Puzzle，之前以 CLIPS, C Language Integrated Production System 求解過，那是專家系統的課，所以我也很配合地，以 heuristic 的方式，寫起一條條的 production rules 。

這次研究所的 AI 課則要求分別利用 BFS (Breadth-First Search), DFS (Depth-First Search), Iterative Deepening DFS 及 A* Search 這四種方式來求解，並比較結果。

無論在 AI searh 理論方面，或是 OOA/OOD 上，這都是個有趣的練習，所以我自告奮勇要打頭陣，完成 framework, BFS, DFS, 和最後的整合及 CUI (Character-based User Interface) 等。

設計的目標有：

Correctness
最起碼要能通老師指定的兩個 case 的試驗。
Clarity
系統架構設計要清晰、簡單、易理解，以方便對軟體作追蹤、審閱、除錯、細部調整、功能刪減等。
Performance
在滿足了correctness 及clarity之後，還要考量程式的高階效率和低階效率。舉凡底層資料結構的選擇、和高層抽象表示法連結上的介面設計等，都是考量重點。
Flexibility
我們在設計時還希望對系統架構能保持一定的彈性。如，不要只針對 8-Puzzle 設計，而更進一步粹取出N-Puzzle的表達方式。

由於分析及設計階段就是採用 OOA/OOD 的方式，所以很自然地要採用支援 OO 的程式語言來實作。經討論，我們決定採用 ANSI C++ 來實作這份設計，並利用 GNU Compiler Collection 來製作可執行檔。

雖然我們只在 Windows 下的 DJGPP 搭配 rhide 的 IDE 及 Linux 下的 g++ 搭配 make 試著編譯過我們的源碼。但理論上應可以適用於任何支援「完整」ANSI C++ 語法的平台。除了 STL 外，還使用了namespace，所以古老的 C++ 編譯環境可能無法順利編出可執行檔。

※請參閱附件：

The Report
Its UML diagram

Saturday, August 17, 2002

State 模式和表格驅動法的比較

　　在 william 譯的《Design Patterns》中，第 353 頁有歸納表格驅動做法和 State 模式的差別： State 模式旨在描述特定狀態之下的行為，表格驅動則專注於定義狀態的轉移。

　　經我的詮釋，使用 State 模式的情況如下：

當每一 state 所面對的所有外界訊息都相同時，就用 State pattern
當狀態轉移條件更改的頻率不高時，可用 State pattern

　　反之：

各個 state 所面對的訊息，交集很少時，考慮用查表法。
當狀態的數目、所有可能的訊息集合、或轉移條件等，會在 run time 改變，那 State pattern 就沒輒了，可以改用查表法。

Tuesday, July 04, 2000

The Thread Class Library for Linux

在設計應用程式時，一些需要並行處理（concurrent processing）的功能，已經很少人使用中斷（interrupt）的方法解決，也不必再自行利用一個輪詢迴圈（Round-robin loop）來達到並行的效果──因為現在作業系統的設計，都已經支援執行緒（thread）了。一個程式可以透過許多執行緒達到並行處理的作用。

一個執行緒的產生，是在應用程式開始執行之後，而執行緒所能運用的系統資源是應用程式可用資源的子集；在應用程式結束前，執行緒就要被銷毀。因為執行緒是應用程式執行時的一個子功能，程式結束後，執行緒就沒有存在的必要。

Linux 作業系統核心提供了 clone() 這個 system call 來支援 thread 的功能。此外， Linux 的共用函式庫中，也利用了 clone() 來實作了 POSIX thread, PThread 標準的 C 語言 thread 應用程式介面。不過在現在到處充斥著物件的後 OO 時代裡，一個傳統 functional 的 C Language API 似乎顯得有些礙手。

這個類別庫（classes' library）主要目的是利用一個 C++ Thread Classes Library ，來提供一個容易使用的物件式介面（object interface），以方便日後在 Linux 系統下開發多執行緒的程式。

“一個具體的問題描述是與一千個尚未運用的抽象觀念等值的”，所以接下來，就先描述一下我們要的 Thread 是長成怎麼樣的：

一個多執行緒類別庫要考量的功能最基本的當然就是要能做好執行緒的內部管理，舉凡執行緒的識別、出生、狀態、行為和死亡等都要照料妥當。

如果執行緒之間要作通訊（communication），當然也要提供一個通訊的管道（channel）;此外，還要考慮到執行緒共用資源時所可能引發的同步（synchronization）問題和避免因互相等待而產生的死鎖（dead-lock）問題。

為了方便多個執行緒的管理，還可以提供執行緒分組的功能，分成一個個的 Thread Group，以方便整組一起操作。

當然，在更完備的功能設計下，每個執行緒和執行緒群組還可以設定個別的執行優先權（priority）。並納入凍結（blocked）後的執行排班（scheduling）設計。

※完整的說明請參閱：

Monday, July 03, 2000

Ant Simulation

大學（1997）的程式設計課要求學生在網路上找一個 JAVA Applet 的程式，研究後寫一篇報告上來。我在網路上找到 Mark Miller 所撰寫的“Manna Mouse”JAVA Applet，檢閱了原始碼後，覺得它的程式架構太雜亂了。於是決定自己利用物件導向分析與設計的方法，將整個程式重新設計過。

如此，一方面可以加深自己對物件導向分析與設計方法的熟練程度；另一方面我對於這個Applet 所使用的遺傳演算法也有很大的興趣，想藉此有更深的探究…

Grady Booch 一向在物件導向（Object Oriented, OO）的方法論上執領導的地位，他在1986年率先提出OO開發方法，開啟物件導向分析與設計的研究。

Booch方法在進行分析時，不只是針對問題本身作分析，也針對問題的領域進行分析。因為在同一領域的問題，有很多非常類似。實在不需要對這些類似的問題，每次都一一地重新作類似的分析。

對於問題的整個領域作一徹底的分析，雖然在一開始的時候需要耗費相當的心力，可是隨著分析的進行，我們對於整個領域就會有更深入的瞭解，最後不但累積了領域相關的知識，也完成了富彈性、高度可重複使用的軟體元件，對於將來開發新的系統將帶來非常大的助益。

Booch 的開發方法非常強調領域內的可重用性（Reuseability），其將軟體開發分成以下三個階段：

需求分析（Requirement Analysis）
領域分析（Domain Analysis）
系統設計（System Design）

上面三個步驟並不是像傳統瀑布式的分析設計方法般僵硬地要求一定要一步步地執行；而是允許在步驟間回溯（backtrack），進行反覆地修改與調整，直到系統符合需求為止。

根據生物學的說法，曾經在地球上出現過或現存的所有生物都是由構造簡單的、原始的生物，經由長期的演化而逐漸產生的。

生物演化的理論，在早期可分成：相信後天獲得的性狀可遺傳給後代的拉馬克（Lamarck）學說，及相信後天性狀不可遺傳給後代的達爾文（Darwin）學說兩大派。

由於後來新證據不斷地出現，及這幾十年來分子生物學的快速發展，生物學上已經知道自然界生物的演化機制是採用達爾文式的。雖然有學者提出人類文化的演進可以看成是採用拉馬克式的演進方式，不過這不是這裡所要討論的重點。

達爾文的生物演化論可分成以下幾個步驟：

遺傳變異（genetic diversify）：個體間因遺傳基因型（genotype）的差異而顯現出各式多樣的表現型態（phenotype）。
自然選擇（natural selection）：自然界對於不能夠於所在環境中適應良好的個體發生淘汰的現象。
繁殖複製（reproduction）：未被淘汰的個體經由繁殖，產生許許多多的後代。這其實是一種選擇放大（selection amplify）的情形。

新產生的後代間又稍有不同而產生了遺傳變異，因此不斷地變異－選擇－複製，變異－選擇－複製，變異－選擇－複製......一直反覆循環下去即發生了生物的演化。

遺傳演算法在電腦科學上屬於演化式計算（Evolutionary Computation）的一環。遺傳演算法其實是以電腦來模擬生物演化的過程。通常用來解一些對問題解法沒有很充分瞭解的例子，或在用傳統的解法成本過高的時候使用。

※請進一步參閱《模擬螞蟻──以物件導向分析遺傳演算法》

Yukuan's Blog