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) 等。

設計的目標有:

  1. Correctness
    最起碼要能通老師指定的兩個 case 的試驗。
  2. Clarity
    系統架構設計要清晰、簡單、易理解,以方便對軟體作追蹤、審閱、除錯、細部調整、功能刪減等。
  3. Performance
    在滿足了correctness 及clarity之後,還要考量程式的高階效率和低階效率。舉凡底層資料結構的選擇、和高層抽象表示法連結上的介面設計等,都是考量重點。
  4. 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++ 編譯環境可能無法順利編出可執行檔。

※請參閱附件:

  1. The Report
  2. Its UML diagram
Tags: [] [] [] [] [] [] [] []

1 comments:

York said...

最近有人來信要 source code ,由於顧慮到可能是在校生上來要作業,所以我只回寄了一份刪掉 BFS, IDDFS, A* .cc 的版本過去,方便他個人觀摩與學習。現在也丟一份到這裡,供同好參考。

老實說,當初這份實作並不理想。主要是使用的資料結構只圖方便及一般化,所以採用 C++ 的 STL 來兜,造成記憶體消耗太嚴重,尤其電腦 RAM 不夠大時,很可能導致頻繁的 swap 。

這類東西的實作,不宜設計得太過一般化。這裡建議,為了效率考量,最好採用緊密些的資料結構。