針對 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
1 comments:
最近有人來信要 source code ，由於顧慮到可能是在校生上來要作業，所以我只回寄了一份刪掉 BFS, IDDFS, A* .cc 的版本過去，方便他個人觀摩與學習。現在也丟一份到這裡，供同好參考。
老實說，當初這份實作並不理想。主要是使用的資料結構只圖方便及一般化，所以採用 C++ 的 STL 來兜，造成記憶體消耗太嚴重，尤其電腦 RAM 不夠大時，很可能導致頻繁的 swap 。
這類東西的實作，不宜設計得太過一般化。這裡建議，為了效率考量，最好採用緊密些的資料結構。
Post a Comment