AI Project 1: R91922034 Hung-Te Lin 資訊系研一 林弘德

程式執行方法

主要程式檔為 clique.lisp , 另外有 sample.lispsample1.lisp 對應到助教在網頁上 提供的 sample。還有clique.lisp,v 是 RCS 檔,可用來隨時抽出以前的版本來看。

VIM 的 LISP syntax highlight 雖然跟 emacs 上 syntax highlight (font-lock-mode) 看起來稍有不同,不過有方便的製作 HTML 功能, 所以我也用 VIM 轉換成 clique.lisp.html 以方便瀏覽。

執行方式為載入照助教規定的格式的 K 與 GRAPH 後, (load "clique.lisp") 然後就可 (clique-1)
(clique-2)
clique-1 即為 Part1 ,clique-2 則為 Part2。

不過在這裡有發現一些小問題,clisp 如果要重複載入用 defvar 定義的東西,後來載入的並不會修改到原值。 所以我改用 setq 以方便重複載入。 [3]> (clique-1)

(INITIALIZING AND CONSTRAINT CHECKING)
(3 5 6 7 9 10 13)
============================================
"Total Solutions Found:"
((3 5 6 7 9 10 13))
T
上面是 clique-1 一般執行的範例。clique-1 有支援搜尋超過一個解的功能, 所以每找到一個解它就會輸出,最後報告所有指定上限內找到的解。 語法是 (clique-1 n),後面有範例;在沒有指定的情況下預設為 1。 [4]> (clique-2)

(INITIALIZING AND CONSTRAINT CHECKING)
============================================
(3 5 6 7 9 10 13)
T
上面是 clique-2 一般執行的範例。 clique-2 只會找到一個解就停了, 沒有額外語法。 [5]> (setq K 8)
8
[6]> (clique-1)

(INITIALIZING AND CONSTRAINT CHECKING)
============================================
"Sorry, no solution found"
NIL
[7]> (clique-2)

(INITIALIZING AND CONSTRAINT CHECKING)
============================================
"Sorry, no solution found"
NIL
上面為 clique-1 與 clique-2 在無解情況下的輸出範例。 [8]> (setq K 7)
8
[9]> (clique-1 99)

(INITIALIZING AND CONSTRAINT CHECKING)
(3 5 6 7 9 10 13)
(3 6 7 9 10 13 14)
============================================
"Total Solutions Found:"
((3 6 7 9 10 13 14) (3 5 6 7 9 10 13))
T
上面是 clique-1 的特殊語法,指定找的解數的上限。

演算法設計與程式內容說明

The Code

我的程式碼寫了很多小的 utility function ,基本上看程式碼可看到大概是分成 basic(最基本的函式), algo-oriented(跟問題相關度較大), search(搜尋函式), 跟 solver(包裝好的solver) 四群。

每一函式都有 string comment,宣告結尾通常有被 comment 起來 可供測試此函式正確與否的 expression。

所以,下面我以解釋做法為主,不特定一個個詳列每個函式 (請自行見其 comment):

Common part

我沒有特地做 Part III,不過我把一些技巧弄進 Part I/II 來加速。

在 Part I 跟 Part II 中都有用到 constraint satisfication 預先處理: constraint-k

constraint-k 會根據 k 把接點不到 k 的 node 跟它所有的 edge 都刪掉, 並 propagate 出去。 這也就是 clique-1/clique2 在執行的一開始會寫 (INITIALIZING AND CONSTRAINT CHECKING) 時在做的事情。

Part I

clique-1 使用的方法相當的直覺, 就是 DFS (clique-dfs)。

clique-dfs 會一次次把點丟入 目前的 node set 中,並測試是不是 clique ,是不是新解。

再決定帶入點時我使用 greedy 的技巧,從 edge 數最多的點 (graph-ordered-range) 開始丟; 這個技巧也用在 Part II 中。

Part II

clique-2 一開始我寫成每次 會測試目前是不是 clique,不是就丟一個點往前呼叫,直到成為 clique 後叫 clique-dfs 過來解;不過就實際上來說,這樣實在不符合題意,所以我做了修正。

clique-2 先取得各 node 連接 edge 數排序過後的表,先取 edge 多的點, 再取 edge 少的點。然後每次拿掉一個點,呼叫 clique-match-set 把剩下的點所有符合長度的組合都找出來測試。 最後要測試完全沒有一開始 所選的點的剩下所有排列組合。

程式撰寫心得

以前我寫過 Scheme 跟一點點 LISP 的程式,不過常覺得自己寫起來老是沒有所謂 functional programming 的感覺; 這次寫程式我就把重點放在練習不要有用 setf 甚至 loop 之類壞習慣的地方。 這次的 code 中很明顯 lambda、 mapcar、 apply 之類的東西用得不少, 而 setf/setq 用得非常少 (幾乎都是拿來定義 global 變數,或是存 final result,不會把普通變數用 setf/setq 處理)。

開發時我用 Cygwin 上的 rxvt 跑 text-mode 的 emacs ,感覺很不錯; 也比較了解 emacs 的 inferior lisp 要怎麼用了,以前我都是寫 elisp-compatible 的 lisp 拿來當 lisp 跟 scheme 用,這次經驗後我想以後不用再這樣了 (elisp 畢竟還是功能太少了)。

All rights reserved by Hung-Te Lin (林弘德, piaip),
Website: piaip at ntu csie ,2003.

All HTML/text typed within VIM on Solaris.
Style sheet from W3C Core StyleSheets.