# 人工智慧概論程式作業一
> [name=曾文鼎 NCTU.CS 0716023]
###### tags: `人工智慧概論` `王才沛`
我用 Java 寫這份作業，使用的版本是 JDK 12 。因為篇幅限於五頁，部份測資沒辦法給的太詳盡。附錄（一）是程式碼實作的概念和各種類別的簡介，附錄（二）是演算法實作的 Code。若有需要檢視詳細的數據，可以在 [Github](https://github.com/Hyperbolas/AI-Searching) 中找到。
## 數據分析
### 尋找測資的解答
#### 所有解答的數量
老師給了 4 筆測資和一本約 3000 字的字典，我將其隨機排序並揀選，重新製成 200、500、1000、1800 字的字典各一本。搭配不同的字典，不同測資存在的解答數量都不同。
| | 200 Words | 500 Words | 1000 Words | 1800 Words | 3000 Words |
| ---: | ---: | ---: | ---: | ---: | ---: |
| 測資一 | 0 | 32 | 1381 | 31643 | 276215 |
| 測資二 | 0 | 509 | 20593 | 477843 | 10538886 |
| 測資三 | 0 | 70 | 11561 | 444498 | 7326632 |
| 測資四 | 0 | 0 | 320 | 447987 | 75325712 |
#### 尋找一個解答
<style>
table.bd {
margin: 6px 0;
background: transparent;
}
table.bd tr {
border: none;
background: transparent !important;
}
table.bd td {
font-size: 85%;
min-width: 1.55em !important;
height: 1.55em !important;
padding: 0;
vertical-align: middle;
border: none;
}
table.bd td:not(:empty) {
background: #fee;
}
</style>
以下給出一個非隨機搜索 (S) 和三個隨機搜索 (R1~R3) 的結果。非隨機搜索的大意是，先規定一個預設的 variable 排序方式 (即自然排序) 。經過特定演算法 (如 MRV) 篩選出所有符合條件的 variable 之後，再依自然排序法選擇最小的變數。填充詞則總是選擇字典序最小者。
| | 測資一 | 測資二 | 測資三 | 測資四 |
|:---:|:---:|:---:|:---:|:---:|
| S | <table class='bd'><tbody><tr><td>A</td><td>B</td><td>L</td><td>E</td></tr><tr><td>B</td><td></td><td>A</td><td></td></tr><tr><td>O</td><td></td><td>T</td><td>O</td></tr><tr><td>U</td><td>S</td><td>E</td><td></td></tr><tr><td>T</td><td></td><td></td><td></td></tr></tbody></table> | <table class='bd'><tbody><tr><td></td><td></td><td></td><td>C</td><td></td><td></td><td></td></tr><tr><td></td><td>A</td><td></td><td>L</td><td></td><td></td><td></td></tr><tr><td>A</td><td>B</td><td>O</td><td>U</td><td>T</td><td></td><td></td></tr><tr><td></td><td>O</td><td></td><td>S</td><td></td><td></td><td></td></tr><tr><td></td><td>U</td><td>N</td><td>T</td><td>I</td><td>L</td><td></td></tr><tr><td></td><td>T</td><td></td><td>E</td><td></td><td>E</td><td></td></tr><tr><td></td><td></td><td></td><td>R</td><td>A</td><td>T</td><td>E</td></tr></tbody></table> | <table class='bd'><tbody><tr><td></td><td></td><td>A</td><td>B</td><td>L</td><td>E</td></tr><tr><td>A</td><td></td><td>D</td><td></td><td></td><td>X</td></tr><tr><td>C</td><td>A</td><td>M</td><td>E</td><td>R</td><td>A</td></tr><tr><td>T</td><td></td><td>I</td><td></td><td></td><td>C</td></tr><tr><td></td><td></td><td>T</td><td>E</td><td>N</td><td>T</td></tr></tbody></table> | <table class='bd'><tbody><tr><td>A</td><td>B</td><td>O</td><td>V</td><td>E</td><td></td><td>B</td><td></td></tr><tr><td>B</td><td></td><td></td><td></td><td>N</td><td>E</td><td>E</td><td>D</td></tr><tr><td>A</td><td></td><td></td><td></td><td>O</td><td></td><td></td><td>E</td></tr><tr><td>N</td><td>U</td><td>M</td><td>E</td><td>R</td><td>O</td><td>U</td><td>S</td></tr><tr><td>D</td><td></td><td>O</td><td></td><td>M</td><td></td><td></td><td>K</td></tr><tr><td>O</td><td>B</td><td>V</td><td>I</td><td>O</td><td>U</td><td>S</td><td></td></tr><tr><td>N</td><td></td><td>I</td><td></td><td>U</td><td></td><td>O</td><td>F</td></tr><tr><td></td><td>L</td><td>E</td><td>S</td><td>S</td><td></td><td></td><td></td></tr></tbody></table> |
| R1 | <table class='bd'><tbody><tr><td>T</td><td>A</td><td>S</td><td>K</td></tr><tr><td>R</td><td></td><td>L</td><td></td></tr><tr><td>A</td><td></td><td>I</td><td>T</td></tr><tr><td>C</td><td>U</td><td>P</td><td></td></tr><tr><td>K</td><td></td><td></td><td></td></tr></tbody></table> | <table class='bd'><tbody><tr><td></td><td></td><td></td><td>S</td><td></td><td></td><td></td></tr><tr><td></td><td>W</td><td></td><td>P</td><td></td><td></td><td></td></tr><tr><td>T</td><td>H</td><td>R</td><td>E</td><td>E</td><td></td><td></td></tr><tr><td></td><td>I</td><td></td><td>C</td><td></td><td></td><td></td></tr><tr><td></td><td>C</td><td>L</td><td>I</td><td>M</td><td>B</td><td></td></tr><tr><td></td><td>H</td><td></td><td>E</td><td></td><td>A</td><td></td></tr><tr><td></td><td></td><td></td><td>S</td><td>I</td><td>G</td><td>N</td></tr></tbody></table> | <table class='bd'><tbody><tr><td></td><td></td><td>S</td><td>P</td><td>I</td><td>N</td></tr><tr><td>E</td><td></td><td>U</td><td></td><td></td><td>U</td></tr><tr><td>A</td><td>P</td><td>P</td><td>E</td><td>A</td><td>R</td></tr><tr><td>T</td><td></td><td>E</td><td></td><td></td><td>S</td></tr><tr><td></td><td></td><td>R</td><td>A</td><td>C</td><td>E</td></tr></tbody></table> | <table class='bd'><tbody><tr><td>B</td><td>A</td><td>S</td><td>I</td><td>C</td><td></td><td>A</td><td></td></tr><tr><td>E</td><td></td><td></td><td></td><td>R</td><td>U</td><td>S</td><td>H</td></tr><tr><td>N</td><td></td><td></td><td></td><td>I</td><td></td><td></td><td>U</td></tr><tr><td>E</td><td>X</td><td>C</td><td>I</td><td>T</td><td>I</td><td>N</td><td>G</td></tr><tr><td>A</td><td></td><td>A</td><td></td><td>I</td><td></td><td></td><td>E</td></tr><tr><td>T</td><td>O</td><td>B</td><td>A</td><td>C</td><td>C</td><td>O</td><td></td></tr><tr><td>H</td><td></td><td>L</td><td></td><td>A</td><td></td><td>H</td><td>E</td></tr><tr><td></td><td>F</td><td>E</td><td>E</td><td>L</td><td></td><td></td><td></td></tr></tbody></table> |
| R2 | <table class='bd'><tbody><tr><td>S</td><td>I</td><td>N</td><td>G</td></tr><tr><td>T</td><td></td><td>E</td><td></td></tr><tr><td>A</td><td></td><td>A</td><td>H</td></tr><tr><td>F</td><td>A</td><td>R</td><td></td></tr><tr><td>F</td><td></td><td></td><td></td></tr></tbody></table> | <table class='bd'><tbody><tr><td></td><td></td><td></td><td>F</td><td></td><td></td><td></td></tr><tr><td></td><td>Q</td><td></td><td>E</td><td></td><td></td><td></td></tr><tr><td>G</td><td>U</td><td>I</td><td>D</td><td>E</td><td></td><td></td></tr><tr><td></td><td>I</td><td></td><td>E</td><td></td><td></td><td></td></tr><tr><td></td><td>T</td><td>H</td><td>R</td><td>O</td><td>W</td><td></td></tr><tr><td></td><td>E</td><td></td><td>A</td><td></td><td>H</td><td></td></tr><tr><td></td><td></td><td></td><td>L</td><td>O</td><td>O</td><td>K</td></tr></tbody></table> | <table class='bd'><tbody><tr><td></td><td></td><td>R</td><td>O</td><td>O</td><td>M</td></tr><tr><td>P</td><td></td><td>E</td><td></td><td></td><td>A</td></tr><tr><td>I</td><td>N</td><td>F</td><td>A</td><td>N</td><td>T</td></tr><tr><td>E</td><td></td><td>E</td><td></td><td></td><td>C</td></tr><tr><td></td><td></td><td>R</td><td>I</td><td>C</td><td>H</td></tr></tbody></table> | <table class='bd'><tbody><tr><td>S</td><td>A</td><td>L</td><td>E</td><td>S</td><td></td><td>O</td><td></td></tr><tr><td>A</td><td></td><td></td><td></td><td>C</td><td>O</td><td>R</td><td>E</td></tr><tr><td>T</td><td></td><td></td><td></td><td>H</td><td></td><td></td><td>V</td></tr><tr><td>I</td><td>N</td><td>C</td><td>R</td><td>E</td><td>A</td><td>S</td><td>E</td></tr><tr><td>S</td><td></td><td>A</td><td></td><td>D</td><td></td><td></td><td>N</td></tr><tr><td>F</td><td>O</td><td>R</td><td>M</td><td>U</td><td>L</td><td>A</td><td></td></tr><tr><td>Y</td><td></td><td>R</td><td></td><td>L</td><td></td><td>D</td><td>O</td></tr><tr><td></td><td>T</td><td>Y</td><td>P</td><td>E</td><td></td><td></td><td></td></tr></tbody></table> |
| R3 | <table class='bd'><tbody><tr><td>S</td><td>O</td><td>M</td><td>E</td></tr><tr><td>W</td><td></td><td>A</td><td></td></tr><tr><td>E</td><td></td><td>I</td><td>N</td></tr><tr><td>A</td><td>L</td><td>L</td><td></td></tr><tr><td>R</td><td></td><td></td><td></td></tr></tbody></table> | <table class='bd'><tbody><tr><td></td><td></td><td></td><td>S</td><td></td><td></td><td></td></tr><tr><td></td><td>F</td><td></td><td>C</td><td></td><td></td><td></td></tr><tr><td>N</td><td>I</td><td>G</td><td>H</td><td>T</td><td></td><td></td></tr><tr><td></td><td>N</td><td></td><td>O</td><td></td><td></td><td></td></tr><tr><td></td><td>A</td><td>L</td><td>L</td><td>O</td><td>W</td><td></td></tr><tr><td></td><td>L</td><td></td><td>A</td><td></td><td>I</td><td></td></tr><tr><td></td><td></td><td></td><td>R</td><td>A</td><td>N</td><td>K</td></tr></tbody></table> | <table class='bd'><tbody><tr><td></td><td></td><td>C</td><td>O</td><td>O</td><td>L</td></tr><tr><td>E</td><td></td><td>R</td><td></td><td></td><td>A</td></tr><tr><td>N</td><td>E</td><td>A</td><td>R</td><td>B</td><td>Y</td></tr><tr><td>D</td><td></td><td>Z</td><td></td><td></td><td>E</td></tr><tr><td></td><td></td><td>Y</td><td>E</td><td>A</td><td>R</td></tr></tbody></table> | <table class='bd'><tbody><tr><td>D</td><td>R</td><td>E</td><td>A</td><td>M</td><td></td><td>G</td><td></td></tr><tr><td>I</td><td></td><td></td><td></td><td>I</td><td>R</td><td>O</td><td>N</td></tr><tr><td>S</td><td></td><td></td><td></td><td>N</td><td></td><td></td><td>E</td></tr><tr><td>M</td><td>U</td><td>L</td><td>T</td><td>I</td><td>P</td><td>L</td><td>E</td></tr><tr><td>I</td><td></td><td>A</td><td></td><td>S</td><td></td><td></td><td>D</td></tr><tr><td>S</td><td>T</td><td>R</td><td>E</td><td>T</td><td>C</td><td>H</td><td></td></tr><tr><td>S</td><td></td><td>G</td><td></td><td>E</td><td></td><td>I</td><td>F</td></tr><tr><td></td><td>P</td><td>E</td><td>E</td><td>R</td><td></td><td></td><td></td></tr></tbody></table> |
### 五種演算法和 Forward Checking 的比較
以下給出尋找測資二所有解答的各種非隨機搜索的數據，受限於篇幅，詳細測資請看[這裡](https://github.com/Hyperbolas/AI-Searching/tree/master/res/data)。所有測試均執行五次，然後取其時間平均值。因為搜索的過程不存在隨機性，過程永遠相同，步數和最大堆疊大小總是相同，沒有平均值的問題。這裡使用的字典是老師給的 3000 Words 字典。
* None 表示沒有演算法的演算法，該演算法總是選擇自然順序最前的 Variable ，然後將可填充詞依照字典序排序
* LCV 自身帶有 Forward Cheking
* DML 表示先 Degree Heuristic 再 MRV 然後 LCV 的演算法
* MDL 表示先 MRV 再 Degree Heuristic 然後 LCV 的演算法
| Algorithm | Checking | Max Stack Size | Time (ms) | Steps |
| :---| :--- | ---: | ---: | ---: |
| None| None | 618 | 35672 | 42213202 |
| MRV | None | 336 | 6005 | 13283688 |
| Degree Heuristic | None | 1072 | 161559 | 151452195 |
| MDL | None | 212 | 8600 | 13283124 |
| DML | None | 449 | 9230 | 14916334 |
| None | Forward Checking| 580 | 62555 | 20272163 |
| MRV | Forward Checking| 309 | 6833 | 12871059 |
| Degree Heuristic | Forward Checking| 771 | 43925 | 19480659 |
| LCV |Forward Checking | 502 | 22403 | 20272163 |
| MDL |Forward Checking | 190 | 8099 | 12870623 |
| DML | Forward Checking | 437 | 6618 | 13444678 |
| None | AC-3| 580 | 49740 | 14095201 |
| MRV| AC-3|190|8714|12566757|
| Degree Heuristic | AC-3| 771 | 25965 | 14674672 |
| LCV |AC-3 | 502 | 22307 | 14095201 |
| MDL |AC-3 | 190 | 8714 | 12566757 |
| DML | AC-3 | 437 | 8145 | 12787278 |
#### Degree Heuristic 的悲劇
在沒有任何 Checking 的情況下， Degree Heuristic 的效能竟然慘輸沒有任何演算法的 None 。我認為原因是 Puzzle 這個東西的 Degree Heuristic 受限於英文單字的長度，因為英文單字的長度很難超過 8 個字，這意味著任意個變數最多只有 8 個相鄰的變數 (以下簡稱鄰居) ，而且實際情況更少。在測資二當中，鄰居的數量不是 2 就是 3， Degree Heuristic 幾乎沒辦法發揮，反而因為其演算法搜尋而徒勞消耗時間。
但這種情況並不是必然。測資一和三的數據 (受限於篇幅不列出) 顯示 Degree Heiristic 的效能沒那麼悲劇，效能和 None 差不多，而這兩筆測資的鄰居數量落在 1 到 3 個之間。因此測資二會如此悲劇，可能只是變數排列陣行的偶然。
#### MRV 完勝其他演算法， LCV 效果有限
承上所述， Puzzle 這東西的變數長度實在有限，然而 Domain 大小卻是大相逕庭，熱門長度 4 至 7 各有數百個詞，這讓 MRV 有極大的發揮空間。因此在這個遊戲中 MRV 明顯優於 Degree Heiristic 。比較 MDL 和 DML 的數據也可以證明這點，因為 MDL 是先篩選 MRV ，所以效能比較高。
LCV 能否發揮取決於 Domain 的歧異度。雖然 26 個英文單字在分布上有顯著的歧異，但老師給的字典中的主流單字長度的差不多，導致各變數的 Domain 大小相差無幾，最終導致 LCV 的發揮仍然有限。
#### 各種演算法搭配 Checking 的觀察
None 演算法若搭配 Checking ，可以很有效地降低走訪的節點數量，但從這份數據來看時間上反而變慢了。可能是因為 Checking 以時間換空間的代價。MRV 亦是如此。
Degree Heuristic 搭配 Checking 後，無論是 Max stack size 、時間或步驟都有很大的進步，我認為是因為 Degree Heuristic 的特性容易創造許多 Domain 很小的變數，讓前項檢查有非常大的發揮空間。因此我的結論是 Degree Heuristic 一定要搭配 Checking 才好用。
LCV 自身附帶 Checking ，因此搭配 AC-3 的話會有演算法重疊的特性，就是所謂一加一小於二的效果，但效能讓仍有小幅的改進，這是因為 LCV 趨向於創造一連串的小型 Domain 。
從數據上來看，不管是哪種演算法，搭配 Checking 之後都能壓低 Max stack size 和走訪的節點數，搜索時間則有進有退。然而 AC-3 和 Forward Checking 能壓低的 Max stack size 大小幾乎一樣，主要差別仍是走訪的節點數。這是因為 Max stack size 往往取決於最大的 Domain 值，而兩種 Checking 都著眼於小 Domain ，因此效果上沒有什麼差異。
### 隨機搜索討論
我將測資一到三以各種演算法測試非隨機和隨機搜索。非隨機搜索測試 5 次取平均值，隨機搜索測試 87 次取平均。測試的方式是對每筆測資尋找 16023 (這是我的學號末五碼) 個解答。下表列出對測資一隨機搜索的數據，扣除非隨機結果的比較值，詳細數據可以在[這裡](https://github.com/Hyperbolas/AI-Searching/tree/master/res/data)找到。
各種隨機演算法的規則是，若篩選出超過一個合格的變數時，隨機選擇一個。對於有同樣排序等級的待填充詞，隨機排序之。
數據顯示，對於大部分的演算法，使用隨機排序會嚴重降低效能； MRV 是少數的例外，在有 Checking 的情況下效能有顯著提昇，原因應是這種演算法本身就不適合總是將待填充詞用字典序排序，因此亂數排序會有較佳的效果。大部分演算法不適合亂數排序，原因可能和英文字母順序的自然特性相關；也有可能是因為亂數排序的實作降低了效率，畢竟多次地對長度為 3000 的 List 洗牌，對性能還是會有一定影響。
| Algorithm | Checking | Max stack size | Time (ms) | Steps |
| :--- | :--- | ---: | ---: | ---: |
| None | None | +313 (+104%) | +43 (+66%) | +1823 (+8%) |
| MRV | None | -230 (-73%) | 0 (0%) | -209 (0%) |
| Degree Heuristic | None | +627 (+112%) | +795 (+2839%) | +685458 (+1630%) |
| MDL | None | +43 (+19%) | +10 (52%) | +268 (+1%) |
| DML | None | +36 (+6%) | -36 (-65%) | -1441 (-7%) |
| None | FC | +357 (+119%) | +203 (+812%) | +10343 (42%) |
| MRV | FC | -32 (-10%) | -12 (-38%) | -180 (0%) |
| Degree Heuristic | FC | +127 (+27%) | +86 (+614%) | +3077 (+12%) |
| LCV | FC | +431 (+186%) | +47 (+204%) | +12253 (+48%) |
| MDL | FC | +43 (+19%) | +10 (+52%) | +268 (+1%) |
| DML | FC | +36 (+6%) | -36 (-65%) | -1441 (-7%) |
| NONE | AC-3 | -313 (-51%) | -83 (-79%) | -1823 (-8%) |
| MRV | AC-3 | -32 (-10%) | -7 (-21%) | +87 (0%) |
| Degree Heuristic | AC-3 | +114 (+25%) | +42 (+233%) | +148 (0%) |
| LCV | AC-3 | +397 (+171%) | -16 (-24%) | +2263 (+10%) |
| MDL | AC-3 | +43 (+19%) | +5 (+26%) | +317 (+1%) |
| DML | AC-3 | +25 (+4%) | -27 (-56%) | -307 (-1%) |
## 心得
我覺得這份作業讓我對搜索有非常深入的了解。⼀開始沒有想到整個程式會寫得這麼龐⼤，雖然類別很多，但每個類別都很精巧，不是肥肥的那種，⽽且簡化了很多重複的程式碼，功能很完備也很靈活，可拓展性非常⾼。**我希望老師應該多出這樣的作業。**
### Degree Heuristic
我⾃⼰是對 Degree Heuristic 的性能抱有⼀點疑慮。沒有任何 Checking 的測資⼆實測數據顯⽰， Degree Heuristic 真的慢得不得了、真的沒什麼發揮，甚⾄筆沒有演算法還要慢兩道三倍。在跑測資四所有解的時候我試過⽤沒有 Checking 的 Degree Heuristic 的，⾃⼰去清夜吃了宵夜回來⼤概⼀個⼩時， Degree Heuristic 竟然還沒跑完！後來⽤三合⼀配 AC-3 不到⼀分鐘終究跑完了。
我在想，在其他的遊戲裡⾯，如果牽涉到的鄰居的數量有較⼤的落差時，這個演算法是不是能有跟 MRV 媲美的效果呢？我有
設計過幾個測資讓相鄰的 varirable 數量比較分散，確實演算法有比較好的效果，但總是沒辦法跟 MRV ⼀樣好。
### Random
Random 搜索讓我蠻失望的，本來以為能夠有什麼出乎意料的發現，像是某種排序⽅法對 Puzzle 特別有⽤等等，但是看來看去，最基本字典排序法貌似已經是最有效的排序法了。整體來說，使⽤ Random 會降低效能。
### Checking 的時間問題
其實看到這個數據我⼼裡頭就是覺得哪裡怪怪的，撇除 Degree Heursitic 不談，當我發現 Forward Checking 對某些演算法會拉⻑時間的時候我就覺得很奇怪，雖然說有壓低 stack size 和節點數量在預期之內。
## 附錄一：程式實作過程和類別簡介
### 兩個核心套件
整個程式碼包含兩個核心套件 `base` 和 `algo` 。 `base` 中有各種基本的作業元素，無關演算法，所以以下僅作簡述。 `Variable` 類別顧名思義記錄 varirable 的座標和長度。 Board 類別代表拼圖版，可以填英文單字上去。 `Assignment` 類別記錄一個 `Variable` 和一個字串，該字串就是指 Variable 被填入的詞。
在談論演算法之前，先講一下 `Variable` 物件的預設排序規則，之後的演算法會提到。 `Variable` 的排序歸則是座標 $x$ 和 $y$ 相加較小者為「較小」。如果多個實例與原點距離相同，則 $x$ 值較小的物件「較小」。若仍存在 $x$ 值相等，則垂直者「較小」，水平者「較大」。
演算法套件 `algo` 實現各種搜尋的演算法。這個套件有三個核心介面 `Node` 、 `Expander` 和 `PuzzleIterator` ，這三個介面的功能互相獨立，其實作類別可以任意搭配組合，成為一個獨立的演算法。我先講解這三個介面的功能，然後會示範怎麼組合這些功能。
當然還有其他套件，但不是很重要，因此本篇不談。我寫程式的習慣是，先決定我需要那些功能，把這些功能用介面定義，然後才寫子類別去寫這些功能。因此，這份作業會看到一些沒有任何程式碼實作的介面。
### Node 介面
* Node
* ~~AbstractNode~~
* BasicNode
* Ac3Node
首先 `Node` 介面表示一個搜索過程中的節點。一個節點持有其父節點，並且紀錄著所有變數的狀態，包含其是否已被填詞、以及被填入哪個詞。為了加速搜索，我後來讓其加以記錄每個變數有哪些鄰居，這個舉動讓 Degree Heuristic 演算法加速了 3 倍。
`Node` 只實現兩個功能。
* 其一，在給定一個 `Assignment `之後， `Node` 必須要能夠生出一個子節點出來，也就是說要能夠自我更新變數與 Domain 。
* 其二， `Node` 依使用者需求決定是否進行 Checking 。 `Node` 有兩個實作類別 `BasicNode` 和 `Ac3Node` 各自實作兩種 Checking 。
`Node` 介面的直接子類別是 `AbstractNode` ，但他只是不重要的抽象類別。這裡只講實際上有演算法的底層類別。
* `BasicNode` 即是最簡單的節點，分成是否支援 Forward Checking 兩種模式。本來想要把有無 Forward Checking 再分成兩種類別，因為但程式碼只差一行，最後還是決定不分了。
* `Ac3Node` 實作 AC-3 演算法。這就是說，他在被生成的時候，會先檢查自己是否含有 Domain 大小為一的變數。如果發生這樣的情況，會持續產生新的節點，直到所有變數都有大小大於 1 的 Domain 為止，最後把過程中所有生成的中間節點串起來。 `Ac3Node` 總是支援 Forward Checking 。
無論是何種節點類別，如果它實作 Forward Checking ，那麼它的實例在被生成時總是會檢查有沒有 Domain 為空；如果有，就會拋出 `DomainEmptyException` 自爆。這樣一來，就能保證每個生成的節點，其變數總是有非空的 Domain 。
### Expander 介面
* Expander
* BasicExpander
* RandomExpander
* MinimumValueRemainingExpander
* BasicMinimumValueRemainingExpander
* RandomMinimumValueRemainingExpander
* DegreeHeuristicExpander
* BasicDegreeHeuristicExpander
* RandomDegreeHeuristicExpander
* LeastConstrainingValueExpander
* BasicLeastConstrainingValueExpander
* RandomLeastConstrainingValueExpander
* ThreeInOneExpander
* BasicThreeInOneExpander
* RandomThreeInOneExpander
剛剛講到 `Node` 具有自我衍生的能力，但前提示要先給它已知的 `Assignment` 。至於 `Assignment` 怎麼決定，則是 `Expander` 介面的任務。 `Expander` 作業的大抵流程是，先給它一個我想要拓展的節點， `Expander` 會對其做身家調查，也就是確認 Variable 和 Domain 的狀態，然後以其實作的演算法決定要給他的 `Assignment` 清單。 `Node` 收到清單之後，會依照清單生成順序與數量相同的子節點。
`Expander` 介面有非常多實作類別。 `MinimumValueRemainingExpander` 、 `DegreeHeuristicExpander` 、 `LeastConstrainingValueExpander` 如其名依序實現 MVR 、 Degree Heuristic 和 LCV ；此外還有一個 `ThreeInOneExpander` 將三種以算法融合。這四個抽象類別都各有兩個衍申類別 `BasicXxx` 和 `RandomXxx` 。
#### 兩個沒有演算法的演算法
最基本的 `BasicExpander` 沒有實作任何演算法，它總是挑選最小的 `Variable` ，然後將可填充詞依照字典序排序。 `RandomExpander` 也沒有實作任何演算法，它總是隨機挑選一個 `Variable` ，然後將可填充詞隨機排序。
`PuzzleIterator` 有非常豐富的操作方法，包含走下一步、找下一組解答、找下一組失敗、搜尋到底，還可以隨時檢視 `Board` 的狀態，功能非常強大。
#### 三個演算法和四個類別
* `MinimumValueRemainingExpander` 總是選擇 Domain 最小的 Variable ，若存在多個符合條件的 Variable ，則由其子類別挑選其一。至於填充詞的順序也是由其子類別決定。
* DegreeHeuristicExpander 總是選擇相鄰 Variable 最多的 Variable ，相似地，若存在多個符合條件的 Variable ，則由其子類別挑選其一；填充詞的順序也是由其子類別決定。
* `LeastConstrainingValueExpander` 總是先由其子類別先挑出一個 `Variable` ，然後依照 LCV 將所有可填充詞排序。遇到多個等級相同的可填充詞時，由其子類別決定如何排序。另外補充一點， `LeastConstrainingValueExpander` 總是會簡差空 Domain ，相當於自身擁有 Forward Checking 的能力。
* `ThreeInOneExpander` 同時實作上述三種演算法，依使用者決定先 MRV 還是先 Degree Heuristic ，然後才 LCV 。同樣，排序是若遇到複數個等級相同的 `Varirable` 或可填充詞，都由其子類別決定最後排序。
上述四個類別的子類別會做無關痛癢的小原則排序：
* 類別 `BasicXxx` 總是挑選最小的 `Varirable` ；排序可填充詞時，依照字典序排序。因為這樣的排序是有固定順序的，無論執行幾次，都會進行同樣的搜索步驟。
* 類別 `RandomXxx` 總是隨便挑選一個 `Variable` ；排序可填充詞時，則將其隨機排序。
### PuzzleIterator 介面
* PuzzleIterator
* DepthFirstPuzzleIterator
* ~~BreathFirstPuzzleIterator~~
這個介面的唯一任務就是將生成的 `Node` 依照某種方式填入自身持有的堆疊中。不過這份作業只有用到 Depth First Searching 而已，因此堆疊弄成先進先出即可。本來還想試試看 BFS ，後來覺得不需要就沒寫了。
除了將生成的節點放入堆疊之外，這個類別也是主要的搜尋過程操控者，其持有重要的 `hasNext` 和 `next` 方法，讓使用者依照自己想要的進程搜索。此外也提供各種很方便的方法像是 `nextSolution` `nextFailure` `step` `maxStackSize` 等等，方便我做數據收集。
#### 一步
`PuzzleIterator` 從堆疊開頭拿出一個節點，使用 `Expander` 使其生成數個子節點，然後將這些子節點放回堆疊。如此過程稱為一步。
### 動手組裝演算法
上面提到的演算法當中，有 3 種 `Node` ( 因為 `BasicNode` 可以開啟或關閉 Forward Check ，可以算 2 種 ）、 10 種 `Expander` 和 1 種 `PuzzleIterator` 。不過 `LeastConstrainingValueExpander` 功能，所以實際上的演算法組合有 28 種。
下面示範一個單純 Forward Checking 配上 MVR 演算法 和 Depth First Searching 的演算組合。如果遇到階層相同的 `Variable` 則隨機則一個，並且令可填充詞隨意排序。然後試圖找出 100 組解答，並計算其步數和最大堆疊大小。
```java=
void test() {
VariableSurveyResult vsr = ... ;
Dictionary dict = ... ;
BasicNode node = new BasicNode(vsr, dict, true);
Expander exp = new RandomMinimumValueRemainingExpander();
PuzzleIterator pi = new DepthFirstPuzzleIterator(node, exp);
int i = 0;
while(pi.nextSolution() && i < 100) i++;
System.out.println("Step: " + pi.step());
System.out.println("Max stack size: " + pi.maxStackSize());
}
```
## 附錄二：演算法原始碼
### Node 介面
以下列出實作 Forward Checking 的程式碼。它是靜態的函數，在各種節點的建構子被呼叫。在 Node 生成時，如果發現空 Domain ，就會拋出 `EmptyDomainException` ，如此一來該節點建構式就不能完成，節點也不會產生 (第 27 至 33 行) 。這個函數也會更新每個變數的鄰居，但這不是重點。
```java=
/**
* Given the variable-domain map and an assignment, updating the map.
* @param domainMap variable-domain map
* @param requireNonEmptyDomain set to true to ensure the domains in the
* resulting map are all non-empty.
* @throws EmptyDomainException when requireNonEmptyDomain is set to true
* and an empty domain is found
*/
protected static void updateVarDomainAndVarNeighborsMap(
Assignment assignment,
Map<Variable, List<String>> domainMap,
Map<Variable, List<Variable>> neighborsMap,
boolean requireNonEmptyDomain) {
Variable assignedVar = assignment.variable;
assert domainMap.containsKey(assignedVar);
assert neighborsMap.containsKey(assignedVar);
List<String> domain;
List<Variable> updatedNeighborList;
IntersectJudger j;
for (Variable n: neighborsMap.get(assignedVar)) {
// Update the domain
domain = domainMap.get(n);
j = new IntersectJudger(n, assignedVar, assignment.word);
// Finds the words that are still valid for the varirable
domain = domain.stream()
.filter(j::judge)
.collect(toList());
if (requireNonEmptyDomain && domain.isEmpty()) {
throw new EmptyDomainException();
}
domainMap.put(n, domain);
// Update the neighbors
updatedNeighborList = new ArrayList<>(neighborsMap.get(n));
assert updatedNeighborList.contains(assignedVar);
updatedNeighborList.remove(assignedVar);
neighborsMap.put(n, updatedNeighborList);
}
domainMap.remove(assignedVar);
neighborsMap.remove(assignedVar);
}
```
以下列出實作 AC-3 的部份。如果偵測到大小為 1 的 Domain ，變數就會自動被填入，然後繼續外層的 while 迴圈 (第 31 至 44 行)。
```java=
/**
* Creates a non-root node.
* @param parent node which is expanded
* @param lastAssignment the parent node performs this assignment and
* then generates this node
* @throws EmptyDomainException if such assignment resulting to some
* variable having empty domain
*/
private Ac3Node(Ac3Node parent, Assignment lastAssignment) {
Map<Variable, List<String>> unassignedVarDomainMap
= new HashMap<>(parent.unassigned);
Map<Variable, List<Variable>> unassignedVarNeighborsMap
= new HashMap<>(parent.unassignedNeighbors);
// Only neighbors of last assigned variable should be checked
outer:
while (true) {
// Updates the domain and neighbors map
updateVarDomainAndVarNeighborsMap(lastAssignment,
unassignedVarDomainMap,
unassignedVarNeighborsMap,
true);
// Checks if any variable with one-item-domain exists
List<Variable> unassignedVars
= new ArrayList<>(unassignedVarDomainMap.keySet());
unassignedVars.sort(null); // must be iterated in natural order
for (Variable v: unassignedVars) {
List<String> domain = unassignedVarDomainMap.get(v);
if (domain.size() != 1) continue;
// Here we found
// Builds a medium node
parent = new Ac3Node(parent,
lastAssignment,
unassignedVarDomainMap,
unassignedVarNeighborsMap);
// Updates the assignment so that the variable-domain map will
// be updated in the next loop
String theOnlyWord = domain.stream().findFirst().get();
lastAssignment = new Assignment(theOnlyWord, v);
// Continues the loop. Again checks if any variable with
// one-item-domain exists
continue outer;
}
// No such variable exists, done!
break;
}
}
```
### Expander 介面
以下列出實作 Degree Heuristic 的程式碼。注意該函數只是返回一個過濾器，該過濾器的真實內容才是演算法。我沒有在上面的介紹中講過濾器，因為它跟演算法無關，只是為了減少重複的程式碼的工具而已。該過濾器返回一個變數清單，該清單裡的所有變數都擁有相同大小的鄰居，而且這個大小是最大的。
第 10 行的 `peekCountOfUnassignedNeighborsOf` 表示取得某變數的鄰居數量的方法，該方法由節點提供，因為這些數據是節點才持有的。
```java=
/**
* A filter that always selects variables having most unassigned
* neighbors.
*/
public static final Filterer<Variable> DEGREE_HEURISTIC_FILTER
= (candidates, successor) -> {
int max = -1, nUnassignedNeighbor;
List<Variable> passed = new ArrayList<>();
for (Variable v: candidates) {
nUnassignedNeighbor = successor.peekCountOfUnassignedNeighborsOf(v);
if (nUnassignedNeighbor < max) continue;
// Here we found
if (nUnassignedNeighbor > max) {
// New maximum, reset the list
max = nUnassignedNeighbor;
passed.clear();
}
passed.add(v);
}
return passed;
};
```
以下列出實作 MRV 的程式碼。同樣，該函數只是返回過濾器，其內容才是演算法。
```java=
/** A filter that always selects variables having minimum count of domains. */
public static final Filterer<Variable> MINIMUM_REMAINING_VALUE_FILTER
= (candidates, successor) -> {
List<Variable> passed = new ArrayList<>();
int minDomainSize = Integer.MAX_VALUE, domainSize;
for (Variable v: candidates) {
domainSize = successor.peekDomainSizeOf(v);
if (domainSize > minDomainSize) continue;
// Here we found
if (domainSize < minDomainSize) {
// New minimum, reset the list
minDomainSize = domainSize;
passed.clear();
}
passed.add(v);
}
return passed;
};
```
以下列出實作 LCV 的程式碼，也是返回過濾器。
```java=
/**
* Given the elected variable, sorts words in the order of LCV algorithm.
* Noted that sometimes not all words are found in the returned list if
* such assignment empties another variable's domain.
* @param elect elected variable
* @param wordCandidates words should be sorted
* @param successor successor node
* @param randomSort set to true to randomly sort words having same level
* @param forwardCheck true to enable forward checking
*/
public static List<String> lcv(Variable elect,
List<String> wordCandidates,
AbstractNode successor,
boolean randomSort,
boolean forwardCheck) {
// Find all neighbors
List<Variable> neighbors
= successor.peekUnassignedNeighborsOf(elect);
if (neighbors.isEmpty()) {
// This assignment is not concerning others,
// just returns standard assignments.
if (!randomSort) return wordCandidates;
List<String> words = new ArrayList<>(wordCandidates);
sortWords(words, true);
return words;
}
// Sorts all the words in the lcv order.
// Builds a count-to-words map
Map<Integer, List<String>> nValMap = new HashMap<>(wordCandidates.size());
int count;
IntersectJudger j;
next:
for (String word: wordCandidates) {
count = 0;
for (Variable n: neighbors) {
j = new IntersectJudger(n, elect, word);
// Finds the size of single unassigned variable's domain
int passed = (int) successor.peekDomainOf(n)
.stream()
.filter(j::judge)
.count();
if (forwardCheck && passed == 0) {
// If this word contributes to some another unassigned
// variable having empty domain, this word must lead to
// failure; hence this word is not put into consideration
// and such node should not be generated.
continue next;
}
count += passed;
}
List<String> list = nValMap.computeIfAbsent(count,
k -> new ArrayList<>());
list.add(word);
}
// Then converts this map to a list of ordered words
List<Integer> counts = new ArrayList<>(nValMap.keySet());
counts.sort(null);
List<String> words = new ArrayList<>(wordCandidates.size());
for (int c: counts) {
List<String> picked = nValMap.get(c);
sortWords(picked, randomSort);
words.addAll(picked);
}
return words;
}
```
### PuzzleIterator 介面
以下列出實作 DFS 的程式碼。
```java=
@Override
public int next() {
AbstractNode n;
// Pops the node at the front of the stack.
try { n = stack.pop(); }
// If the stack is empty, the searching is ended.
catch (NoSuchElementException e) {
throw new IllegalStateException();
}
step++;
currentNode = n;
List<? extends AbstractNode> expanded = ea.expand(currentNode);
if (expanded.isEmpty()) {
// If the node has no offspring, this node is at the end; hence
// it is either a solution or a failure.
return currentNode.isSolution()? SOLUTION: FAILURE;
}
// Puts expanded node to the front of the stack. This is DFS.
stack.addAll(0, expanded);
maxSize = Math.max(maxSize, stackSize());
return UNKNOWN;
}
```
Sign in with Wallet
Connect another wallet