搬運工的計算機求解 - Delphi K.Top 討論區

發表時間：2003-02-25 21:03:51

IP:61.218.xxx.xxx 未訂閱

搬運工的計算機求解原文: http://vip.6to23.com/NowCan1/tech/box.txt 前言 "搬運工"是一個十分流行的單人智力遊戲，玩家的任務是在一個倉庫中操縱一個搬運工人將N個相同的箱子推到N個相同的目的地。不清楚規則不要緊，玩一玩附件裡的SokoMind就知道了。我在裡面加上了標準的測試關卡90關，幼兒關卡61關和文曲星170關，在以後的介紹中，我們就用這些關來測試我們的程序，因此我建議你自己先試一試，看看你能過多少關：）因為本文內容不算少，在這裡我先給大家提供一個小小的閱讀建議。初學的朋友或者不知道IDA*算法的朋友一定要從第一章開始閱讀並弄懂，因為它是全文的基礎。第二章很好懂，大家只需要做一個瞭解，知道搬運工問題的難點在哪裡，為什麼我們選擇了IDA*算法。急於看程序的朋友可以先看看第三章，我們的第一個版本S4-Baby誕生了，接著是一系列的改進措施，喜歡人工智能的朋友不妨認真看看，也許會找到靈感哦！最後是總結，和第一章一樣的重要，不要錯過了。我假定本文的讀者已經對相關知識有一定瞭解，所以一般不給出很嚴格的定義或者論證，只是粗略的提一下，語言盡量做到通俗易懂。但由於我的水平實在有限，錯誤之處一定不少，懇請大家批評指正：）一狀態空間搜索基本知識 1.狀態空間(state space) 對於一個實際的問題，我們可以把它進行一定的抽像。通俗的說，狀態(state)是對問題在某一時刻的進展情況的數學描述，狀態轉移(state-transition)就是問題從一種狀態轉移到另一種（或幾種）狀態的操作。如果只有一個智能體(Agent)可以實施這種狀態轉移，則我們的目的是單一的，也就是從確定的起始狀態(start state)經過一系列狀態轉移而到達一個（或多個）目標狀態(goal state)。如果不止一個智能體可以操縱狀態轉移(例如下棋)，那麼它們可能會朝不同的，甚至是對立的目標進行狀態轉移。這樣的題目不在本文討論範圍之內。我們知道，搜索的過程實際是在遍歷一個隱式圖，它的結點是所有的狀態，有向邊對應於狀態轉移。一個可行解就是一條從起始結點出發到目標狀態集中任意一個結點的路徑。這個圖稱為狀態空間(state space)，這樣的搜索就是狀態空間搜索(Single-Agent Search) 2.盲目搜索(Uninformed Search) 盲目搜索主要包括以下幾種：純隨機搜索(Random Generation and Random Walk) 聽起來比較"傻"，但是當深度很大，可行解比較多，解的深度又不重要的時候還是有用的，而且改進後的隨機搜索可以對付解分佈比較有規律（相對密集或平均，或按黃金分割比例分佈等）的題目。一個典型的例子是：你在慌亂中找東西的時候，往往都是進行隨機搜索。廣度優先搜索(BFS)和深度優先搜索(DFS) 大家都很熟悉它們的時間效率，空間效率和特點了吧。廣度優先搜索的例子是你的眼鏡掉在地上以後，你趴在地板上找：）- 你總是先摸最接近你的地方，如果沒有，在摸遠一點的地方…深度優先搜索的典型例子是走迷宮。它們還有逆向和雙向的搜索方式，但是不再本文討論範圍之內。重複式搜索這些搜索通過對搜索樹擴展式做一些限制，用逐步放寬條件的方式進行重複搜索。這些方法包括：重複式深度優先(Iterative Deepening) 限制搜索樹的最大深度Dmax,然後進行搜索。如果沒有解就加大Dmax再搜索。雖然這樣進行了很多重複工作，但是因為搜索的工作量與深度成指數關係，因此上一次（重複的）工作量比起當前的搜索量來是比較小的。這種方法適合搜索樹總的來說又寬又深，但是可行解卻不是很深的題目（一般的深度優先可能陷入很深的又沒有解的地方，廣度優先的話空間又不夠）重複式廣度優先(Iterative Broadening) 它限制的是從一個結點擴展出來的子節點的最大值Bmax,但是因為優點不是很明顯，應用並不多，研究得也比較少。柱型搜索(Beam Search) 它限制的是每層搜索樹節點總數的最大值Wmax。顯然這樣搜索樹大小與深度成正比，但是可能錯過很接近起點的解，而增加Wmax的時候保留哪些節點，Wmax增加多少是當前正在研究的問題。 3.啟髮式搜索(Informed Search) 我們覺得一些問題很有"想頭"，主要是因為啟發信息比較多，思考起來容易入手，但是卻不容易找到解。我們不願意手工一個一個盲目的試驗，同樣也不願意我們的程序機械的搜索。也就是說，我們希望盡可能的挖掘題目自身的特點，讓搜索智能化。下面介紹的啟發式搜索就是這樣的一種智能化搜索方法。在剛才的那些算法中，我們沒有利用狀態本身的信息，只是利用了狀態轉移來進行搜索。事實上，我們自己在解決問題的時候常常會估計狀態離目標到底有多接近，進而對多種方案進行選擇。把這種方法用到搜索中來，我們可以用一個狀態的估價函數來估計它到目標狀態的距離。這個估價函數是和問題息息相關的，體現了一定的智能。為了以後敘述方便，我們先介紹一些記號： S 問題的任何一種狀態 H*(s) s到目標的實際（最短）距離 - 可惜事先不知道：） H(s) s的啟發函數 - s到目標距離的下界，也就是h(s)<=h*(s),如果h函數對任意狀態s1和 s2,還滿足h(s1)<=h(s2)+c(s1,s2)（其中c(s1,s2)代表狀態s1轉移到s2的代價）,也就是狀態轉移時，下界h的減少值最多等於狀態轉移的實際代價，我們說h函數是相容(consisten t)的。(其實就是要求h不能減少得太快) G(s) 到達s狀態之前的代價，一般就採用s在搜索樹中的深度。 F(s) s的估價函數，也就是到達目標的總代價的估計。直觀上，應該有f(s)=g(s)+h(s)，即已經付出的和將要付出的代價之和。如果g 是相容的，對於s1和它的後輩節點，有h(s1)<=h(s2)+c(s1,s2) 兩邊同時加上g(s1),有h(s1)+g(s1)<=h(s2)+g(s1)+c(s1,s2),也就是 f(s1)<=f(s2)。因此f函數單調遞增。表1 啟髮式搜索用到的符號貪心搜索(Best-First Search) 象廣度優先搜索一樣用一個隊列儲存待擴展，但是按照h函數值從小到大排序(其實就是優先隊列)。顯然由於h估計的不精確性，貪心搜索不能保證得到的第一個解最優，而且可能很久都找不到一個解。 A*算法和貪心搜索很類似，不過是按照f函數值進行排序。但是這樣會多出一個問題：新生成的狀態可能已經遇到過了的。為什麼會這樣呢？由於貪心搜索是按照h函數值排序，而h只與狀態有關，因此不會出現重複，而f值不僅狀態有關，還與狀態轉移到s的方式有關，因此可能出現同一個狀態有不同的f值。解決方式也很簡單，如果新狀態s1與已經遇到的狀態s2相同，保留f值比較小的一個就可以了。(如果s2是待擴展結點，是有可能出現f(s2)>f(s1)的情況的，只有已擴展結點才保證f值遞增)。A*算法保證得到最優解，但是所用的空間是很大的，難以適應我們的搬運工問題。 IDA*算法既然A*算法存在空間問題，那麼我們能不能借用深度優先搜索的空間優勢，用重複式搜索的方式來緩解危機呢？經過研究，Korf於1985年提出了一個Iternative Deepening A*( IDA*)算法，比較好的解決了這一問題。一開始，我們把深度最大值Dmax設為起始結點的h 值，開始進行深度優先搜索，忽略所有f值大於Dmax的結點，減少了很多搜索量。如果沒有解，再加大Dmax的值，直到找到一個解。容易證明這個解一定是最優的。由於改成了深度優先的方式，與A*比較起來，IDA*更加實用： 1. 不需要判重，不需要排序，只用棧就可以了。操作簡單。 2. 空間需求大大減少，與搜索樹大小成對數關係。其他的啟髮式搜索這些方法包括深度優先+最優剪枝式的A*，雙向A*,但是由於很不成熟或者用處並不大，這裡就不介紹了。A*算法有一個加權的形式，由於在搬運工問題中效果不明顯，這裡從略。二搬運工問題及其特點在對狀態空間搜索算法有一定瞭解之後，我們來看看我們的搬運工問題。究竟用什麼方法比較好呢？讓我們先來看看該問題的特點。 1. 搬運工問題我們在前面已經介紹過搬運工問題，這裡我只是想提一些和解題有關的注意事項。首先，我們考慮的搬運工問題的地圖規模最大是20*20，這已經可以滿足大部分關卡了。為了以後討論方便，我們把地圖加以編號。從左往右各列稱為A，B，C…，而從上往下各行叫a,b,c …。而由於不推箱子時的走路並不重要，我們在記錄解的時候忽略了人的位置和移動，只記錄箱子的移動。人的動作很容易根據箱子的動作推出來。下面是包含解答的標準關卡第一關。呵呵，怎麼樣，第一關都要那麼多步啊…以後的各關，可是越來越難。 2. 搬運工問題的特點我在前言裡吹了這麼半天，我想你即使以前沒有玩，現在也已經玩過了吧：）。有什麼感覺呢？是不是變化太多了，不好把握？不僅人不好把握，連編程序也變得困難了很多。我們不妨拿它與經典的8數碼問題作一個比較。 1.死鎖！初學者很快就會學到什麼是死鎖 - 一旦他（她）把一個箱子推到角上。顯然，這樣的佈局再繼續玩下去是沒戲了，不管以後怎麼推都不可能把這個箱子推離那個角。不少玩家都總結了不少死鎖的經驗，但是要比較系統的解決這個問題並不是一件容易的事。我們將用整整一章（其實也不長啦）的篇幅來分析這個問題。典型的死鎖。想一想，為什麼：）我們再看一下8數碼問題。它沒有死鎖，因為每一步都是可逆的。在這一點上，搬運工問題要令人頭疼得多了。容易看出，這樣的狀態空間不是無向圖，而是有向圖。 2.狀態空間。 8數碼問題每次最多有4中移動方法，最多的步數也只有幾十步。而搬運工問題呢？困難一點的關卡可以是一步有100多種選擇，整個解答包括600多次推箱子動作。分支因子和解答樹深度都這麼大，狀態空間自然就非同小可了。 3.下界估計在啟髮式搜索中，我們需要計算h值，也就是需要對下界進行估計。8數碼問題有很多不錯的下界函數（如"離家"距離和），但是搬運工問題又怎麼樣呢？我們不能直接計算"離家" 距離，因為誰的家是哪兒都不清楚。很自然，我們可以做一個二分圖的最佳匹配，但是這個下界怎麼樣呢？ a.準確性對於A*及其變種來說，下界與實際代價越接近，一般來說算法效率就越高。我們這個最佳匹配只是"理想情況"，但是事實上，在很多情況下箱子相互制約，不得已離開目標路線來為其他箱子騰位置的事情是非常普遍的。例如我們的標準關卡第50關，有的箱子需要從目標格子穿過並離開它來為其它箱子讓路。我們的下界函數返回值是100，但是目前的最好結果是370。多麼大的差別！ b.效率由於下界函數是一個調用非常頻繁的函數，其效率不容忽視。最佳匹配的時間漸進複雜度大約是O(N^3),比8數碼的下界函數不知大了多少…我們將會在後面給出一些改進方法，但是其本質不會改變。 3. 如何解決搬運工問題已經有人證明了搬運工問題是NP-Hard，看來我們還是考慮搜索吧。回想一下上一節提到過的狀態空間搜索，用哪一種比較好呢？既然是智力遊戲，可用的啟髮式信息是非常豐富了，我們不僅是要用，而且要用得盡量充分,所以應該用啟髮式搜索。而前面已經提到了，搬運工問題的狀態空間是非常大的，A*是沒有辦法了，因此我們選擇了IDA*算法：實現簡單，空間需求也少。既然搬運工問題這麼難，為什麼有那麼多人都解決了相當數量的關卡呢（標準的90N年以前就被人們模透了）。因為人聰明嘛。他們會預測，會安排，會學習，有直覺的幫助，還有一定的冒險精神。他們（也包括我啦，呵呵）常用的是一些"高層次"的解題策略，既有效，又靈活。(Srbga:想學嗎? Readers:當然想!!)可惜這些策略不是那麼簡單易學，也不是很有規律的。在後面的章節中，我將盡力模仿人的思維方式給我們的程序加入盡量多的智能。三用IDA*算法解搬運工問題實現與改進在上一節中，我們知道了IDA*算法是我們解決搬運工問題的核心算法。在這一節裡，我們將用IDA*算法來做一個解決搬運工問題的程序 - 雖然是我們的最初版本(我們稱做S4-Bab y)，但是不要小看它哦！ 1 IDA*算法框架由前所述，IDA*算法是基於重複式深度優先的A*算法，忽略所有f值大於深度限制的結點。那麼，我們不難寫出IDA*算法框架的偽代碼偽代碼1 - IDA*算法框架

procedure IDA_STAR(StartState)
begin
  PathLimit := H( StartState ) - 1;
  Success := False;
repeat
inc(PathLimit);
StartState.g:= 0;
Push(OpenStack,StartState);
repeat
  CurrentState:=Pop(OpenStack);
  If Solution(CurrentState) then
    Success = True
  Else if PathLimit >= CurrentState.g   H(CurrentState) then
    Foreach Child(CurrentState) do
      Push(OpenStack, Child(CurrentState));
until Success or empty(OpenStack);
until Success or ResourceLimitsReached;
end;

這只是一個很粗略的框架，什麼事情都不能做。不過我想大家可能比較急於試驗一下IDA* 的威力，因此我們不妨就做一個最最基本的程序。 2. 第一個程序要從框架做一個程序需要填充一些東西。在這裡我們就展開一些討論。輸入輸出文件格式輸入文件是一個文本文件，它由N行構成，每行是一些字符。各種字符的含義是：

SPACE   空地
.       目標格子
$       箱子
*       目標格子中的箱子
@       搬運工
        目標格子中的搬運工
#       牆

表2 輸入文件格式這種格式和Xsokoban, SokoMind和Rolling Stone的格式是一致的，因此會比較方便一些。輸出文件第一行是推箱子的次數M，以下M行，每行的格式是：x y direction,代表把第x行第y列的箱子往direction的方向推一步。Direction可以是left,right,up,down之中的一個 ,1<=x,y<=20 數據結構由於是最初的版本，我們不必考慮這麼多：只需要可行，編程方便就可以了，暫時不管它的效率和其他東西。優化是以後的事。我們定義新的數據類型BitString,MazeType,MoveType,StateType和IDAType。請大家看附錄中的程序，不難猜出它們的含義和用途。唯一需要說明的BitString類型。記錄狀態時，我們把地圖看成一個大數，一個格子是一個bit。那麼所有箱子構成一個BitString,檢查某一個是否有箱子（或者目標，牆）時只需要檢測對應位置上的bit是否為1。這樣雖然會浪費一些空間，但是判斷會比較快，操作也比較簡單。我們把x,y坐標合併成一個"position"變量。其中Position=(x-1)*width (y-1)。我們用常量數組DeltaPos:array[0..3]表示上，下，左，右的Position增量。算法為了簡單起見，我們連最佳匹配也不做了，用所有箱子離最近目標的距離和作為下界函數。不過，這裡的"距離"是指推的次數，計算的時候（MinPush函數），只要忽略其它所有箱子，然後用一次BFS就可以了。效果嘿嘿，這個效果嘛，不說你也知道的，就是標準關一個也過不了啦。不過為了說明我的程序是正確的，你可以試驗一下幼兒關卡(共61關)嘛！什麼！第一關都就沒有動靜了…55555，生成了18萬個結點???不過很多關都很快就過了的。我們用1,000,000個結點為上限(在我的Celeron 300A上要運行十多分鐘),得到以下的測試結果：

No.     步數    結點數  No.     步數    結點數  No.     步數    結點數
1       15      186476  21      8       102     41      11      145
2       6       24      22      7       110     42      10      118
3       5       14      23      10      192     43      12      223
4       6       24      24      10      432     44      8       63
5       9       31      25      4       23      45      12      138
6       5       8       26      11      846     46      14      178
7       6       35      27      3       18      47      8       296
8       11      39      28      9       38      48      8       156
9       4       12      29      10      142     49      5       60
10      5       14      30      8       641     50      11      14451
11      5       13      31      7       192     51      N/A     >1M
12      4       19      32      3       12      52      N/A     >1M
13      4       14      33      11      51      53      8       470
14      6       20      34      11      332     54      16      24270
15      6       57      35      16      11118   55      N/A     >1M
16      12      3947    36      10      242     56      14      3318
17      6       63      37      9       1171    57      N/A     >1M
18      11      5108    38      11      556     58      N/A     >1M
19      10      467     39      10      72      59      11      328
20      10      1681    40      9       203     60      N/A     >1M
                                                61      N/A     >1M

沒有解決的幾關是：51,52,55,57,,58,60,61 比較困難的幾關是1,16,18,20,26,30,35,37,38,50,53,54,56 下面，我們來看看"困難關卡"的下界估計的情況，看看"偷懶"付出的代價。

關卡    最優步數        初始深度        結點總數        頂層結點數
1       15              11              186476          7416
16      12              7               3947            844
18      11              10              5108            49
20      10              6               1681            42
26      11              5               846             394
30      8               6               641             200
35      16              3               11118           3464
37      9               4               1171            493
38      11              5               556             250
50      11              6               14451           51
53      8               5               470             48
54      16              9               24270           2562
56      14              4               3318            460

由此可見，下界估計對於搜索樹的大小是很有關係的。看看第18,20,35,50,54,56關吧。頂層結點多麼少！如果一開始就從這一層搜索不就…看來我們真的需要用最佳匹配算法了。 3.試驗最佳匹配算法的威力好，下面我們來使用最佳匹配算法。最佳匹配算法可以用網絡流來實現，但是這裡我們采用修改頂標算法，我是抄的書上的程序（偷個懶嘛，呵呵）。現在，程序改叫Baby2了^_^ 下面是剛才的"難題"的測試情況。

關卡    實際步數        初始深度        Baby-1結點總數  Baby-2結點總數
1       15      15      186476  60
16      12      10      3947    304
18      11      11      5108    46
20      10      8       1681    76
26      11      5       846     552
30      8       8       641     153
35      16      4       11118   6504
37      9       5       1171    438
38      11      5       556     546
50      11      7       14451   98
53      8       8       470     37
54      16      12      24270   273
56      14      4       3318    2225

哇！有的比剛才的頂層結點還要少！當然了，下界估計好了，當前層的深度剪枝也更準確了嘛。另外，現在我們來看看文曲星的前12關，第1,2,4,6,8,9,11關已經可以在50000個結點之內出解。

關卡    實際步數        初始深度        結點總數        頂層結點數
1       31      31      75      75
2       11      11      142     142
4       26      18      33923   159
6       16      16      47      47
8       27      21      239     213
9       12      6       4806    2778
11      14      14      73      73

那麼下一步幹什麼呢？打印出每個狀態來分析，我們不難發現大量重複結點。所以下一個問題自然就是：怎麼避免重複呢？ 4.試驗HASH表的威力判重嘛，當然就需要HASH表了。不過一個很棘手的問題是：如何表示狀態？在結點擴展中，我們用比特流的方式定義了箱子的狀態，但是在這裡我們需要的是合適的數組的下標。這種表示法不爽吧。所以在構造HASH表的時候我們就用箱子的坐標來表示狀態，也就是N元組(p[1],p[2],p[3]..p[n])。至於散列函數嘛，我們根據HASH表的項數來考慮。這裡，如果箱子最多100個，我們就用10000項試試看。一種方案是把所有的坐標加起來，但是這樣做衝突很多！因為一個箱子A右移一格，另一個箱子B左移一格，散列函數值不變。考慮到必須使衝突變少，函數又不宜太複雜，我們採用坐標的加權和來作為散列函數值，也就是 Sum{k*Position[k]},當然，最後要對10000取餘數，其實這個函數也不好，不過我比較懶了，以後再改進吧。至於衝突處理嗎，為了簡單起見，我們用開鏈法設立鏈表來保存所有元素。值得注意的是，箱子坐標相同而人的坐標不能互通的狀態是不同的，應該一起保存

。下面是剛才那些關的測試結果：
關卡    實際步數        初始深度        Baby2結點數     Baby3結點數
Kid 1   15      15      60      52
Kid 16  12      10      304     189
Kid 18  11      11      46      41
Kid 20  10      8       76      67
Kid 26  11      5       552     192
Kid 30  8       8       153     145
Kid 35  16      4       6504    704
Kid 37  9       5       438     136
Kid 38  11      5       546     152
Kid 50  11      7       98      96
Kid 53  8       8       37      24
Kid 54  16      12      273     258
Kid 56  14      4       2225    1518
Wqx 1   31      31      75      75
Wqx 2   11      11      142     107
Wqx 4   26      18      33923   33916
Wqx 6   16      16      47      46
Wqx 8   27      21      239     226
Wqx 9   12      6       4806    968
Wqx 11  14      14      73      67
新完成的關卡有：
關卡    實際步數        初始深度        結點總數        頂層結點數
Kid 51  13      13      629     629
Kid 52  18      18      39841   39841
Ki d55  14      4       4886    1919
Kid 60  15      9       6916    916

需要注意的是，在保護模式下運行kid57的時候出現的heap overflow，說明完全保存結點沒有必要(費空間，費時間)，也不大可能。那麼，我們應該怎樣做呢？我們知道，評價一個HASH表的優劣，一般是從兩個方面：查表成功的頻率和查表成功以後節省的工作。因此，我們可以設置兩個Hash表，一個保存最近的結點（查到的可能性比較大）和深度大的結點（一旦找到，節省很多工作）。這樣做不會增加多少結點數，但是是程序效率有所提高，求解能力（空間承受能力）也有較大改善。但是為了方便，我們的程序暫時只使用第一個表。 5.結點擴展順序的優化在這一節中，我們的最後一個改進是優化結點擴展的順序，不是想修剪搜索樹，而是希望早一點得到解。具體的改進方法是這樣的： 1.優先推剛剛推過的箱子 2.然後試所有的能夠減少下界的方案，減少得越多越先試。如果減少得一樣多，就先推離目標最近的。 3.最後試其他的，也像2一樣按順序考慮。可以預料，這樣處理以後，"比較容易"先找到解，但是因為下界估計不准所花費的代價是無法減小的（也就是說只能減少頂層結點數）。不過作為IDA*的標準改進方法之一，我們有必要把它加入我們的程序中試試。 (需要注意的是，我們使用的是棧，應該把比較差的方案先壓棧) 實際測試結果，1的效果比較好，2和3的效果不佳，甚至產生了更多的結點。可能主要是我們的下界估計不準確，而2和3用到了下界函數的緣故。這一個版本Baby-4中，我們屏蔽了第2，3項措施。好了，寫了四個Baby版程序，想不想比較一下呢？不過我只對幾個困難一點的數據感興趣。

關卡 實際步數 Baby-1 Baby-2 Baby-3 Baby-4
Kid 1  11     186476 60 52 38
Kid 16 7 3947 304 189 149
Kid 18 10 5108 46 41 31
Kid 35 16 11118 6504 704 462
Kid 50 11 14451 98 96 152
Kid 51 13 Too many Too many 629 54
Kid 52 18 Too many Too many 39841 97
Kid 54 16 24270 273 258 140
Kid 55 14 Too many Too many 4886 3390
Kid 56 14 3318 2225 1518 1069
Kid 60 15 Too many Too many 6916 5022
Wqx 4 26 97855 33923 33916 24251
Wqx 9 12 116927 4806 968 350

從上表可以看出，我們的優化總的來說是有效的，而且直觀的看，那些改進不明顯的很多是因為下界估計比較差，這一點我們以後會繼續討論。不管怎樣，這61關"幼兒關"過了58 關倒是挺不錯的，至少可以說明我們程序的Baby版已經具有普通兒童的"智力"了^_^。不過這只是個開頭，好戲還在後頭！ 6.Baby-4源程序程序S4BABY4.PAS在附件中，這裡只是加了少量的註釋。大家可以試試它的效果，但是沒有必要看得太仔細，因為在以後的章節中，我會改動很多東西，甚至連IDA*主程序框架都會變得不一樣。常量定義：

const
  {Version}
  VerStr='S4 - SRbGa Super Sokoban Solver (Baby Version 4)';
  Author='Written by Liu Rujia(SrbGa), 2001.2, Chongqing, China';
  {Files}
  InFile='soko.in';
  OutFile='soko.out';
  {Charactors}
  Char_Soko='@';
  Char_SokoInTarget=' ';
  Char_Box='$';
  Char_BoxInTarget='*';
  Char_Target='.';
  Char_Wall='#';
  Char_Empty=' ';
  {Dimentions}
  Maxx=21;
  Maxy=21;
  MaxBox=50;
  {Directions}
  Up=0;
  Down=1;
  Left=2;
  Right=3;
  DirectionWords:array[0..3] of string=('UP','DOWN','LEFT','RIGHT');
  {Movement}
  MaxPosition:integer=Maxx*Maxy;
  Opposite:array[0..3] of integer=(1,0,3,2);
  DeltaPos:array[0..3] of integer=(-Maxy,Maxy,-1,1);

我們把x,y坐標合成一個值position，其中position=(x-1)*maxy (y-1)。這裡用類型常量是因為以後會根據地圖的尺寸改變MaxPosition的值。Opposite就是相反方向例如Opposit e[UP]:=DOWN;DeltaPos也是會重新設定的。我們在進行移動的時候只需要用：NewPos:=Ol dPos DeltaPos[Direction]就可以了，很方便。


  {IDA Related}
  MaxNode=1000000;
  MaxDepth=100;
  MaxStack=150;
  DispNode=1000;
每生成多少個結點報告一次。
  {HashTable}
  MaxHashEntry=10000;
  HashMask=10000;
  MaxSubEntry=100;
  {BitString}
  BitMask:array[0..7] of byte=(1,2,4,8,16,32,64,128);
  Infinite=Maxint;    類型定義：
type
  PositionType=integer;
  BitString=array[0..Maxx*Maxy div 8-1] of byte;
整個地圖就是一個BitString。第position位為1當且僅當position位置有東西（如箱子，
目標，牆）。
  MapType=array[1..Maxx] of string[Maxy];
  BiGraph=array[1..MaxBox,1..MaxBox] of integer;
  MazeType=
  record
    X,Y:integer;
    Map:MapType;
    GoalPosition:array[1..MaxBox] of integer;
    BoxCount:integer;
    Goals:BitString;
    Walls:BitString;
  end;
尺寸，原始數據（用來顯示狀態的），目標的BitString，箱子總數，目標位置（BitStri
ng和位置數組都用是為了加快速度）和Walls的BitString。
  MoveType=
  record
    Position:integer;
    Direction:0..3;
  end;
Direction是箱子被推向的方向。
  StateType=
  record
    Boxes:BitString;
    ManPosition:PositionType;
    MoveCount:integer;
    Move:array[1..MaxDepth] of MoveType;
    g,h:integer;
  end;
  IDAType=
  record
    TopLevelNodeCount:longint;
    NodeCount:longint;
    StartState:StateType;
    PathLimit:integer;
    Top:integer;
    Stack:array[1..MaxStack] of StateType;
  end;
Top是棧頂指針。
  PHashTableEntry=^HashTableEntry;
  HashTableEntry=
  record
    Next:PHashTableEntry;
    State:StateType;
  end;
  PHashTableType=^HashTableType;
  HashTableType=
  record
    FirstEntry:array[0..MaxHashEntry] of PHashTableEntry;
    Count:array[0..MaxHashEntry] of byte;
  end;
這些是Hash表相關類型。我們採用的是拉鏈法，這樣可以利用指針申請到堆空間，結合保
護模式使用，效果更好。
var
  HashTable:PHashTableType;
  SokoMaze:MazeType;
  IDA:IDAType;
procedure SetBit(var BS:BitString; p:integer);
begin
  BS[p div 8]:=BS[p div 8] or BitMask[p mod 8];
end;
procedure ClearBit(var BS:BitString; p:integer);
begin
  BS[p div 8]:=BS[p div 8] xor BitMask[p mod 8];
end;
function GetBit(var BS:BitString; p:integer):byte;
begin
  if BS[p div 8] and BitMask[p mod 8]>0 then GetBit:=1 else GetBit:=0;
end;
這些是位操作，設置，清除和得到一個BitString的某一項。
procedure Init;
var
  Lines:MapType;
  procedure ReadInputFile;
  var
    f:text;
    s:string;
  begin
    SokoMaze.X:=0;
    SokoMaze.Y:=0;
    SokoMaze.BoxCount:=0;
    assign(f,infile);
    reset(f);
    while not eof(f) do
    begin
      readln(f,s);
      if length(s)>SokoMaze.Y then
        SokoMaze.Y:=length(s);
      inc(SokoMaze.X);
      Lines[SokoMaze.X]:=s;
    end;
    close(f);
  end;
procedure AdjustData;
  var
    i,j:integer;
  begin
    for i:=1 to SokoMaze.X do
      while length(Lines[i])Char_Wall then
          SokoMaze.Map[i,j]:=Char_Empty;
調整Map數組，把箱子和搬運工去掉。
    for i:=1 to SokoMaze.X do
      for j:=1 to SokoMaze.Y do
        if Lines[i,j] in [Char_Target,Char_BoxInTarget,Char_SokoInTarget] then
        begin
          inc(SokoMaze.BoxCount);
          SokoMaze.GoalPosition[SokoMaze.BoxCount]:=(i-1)*SokoMaze.Y j-1;
        end;
統計Goal的個數和GoalPosition。
    DeltaPos[Up]:=-SokoMaze.Y;
    DeltaPos[Down]:=SokoMaze.Y;
    MaxPosition:=SokoMaze.X*SokoMaze.Y;
根據地圖尺寸調整DeltaPos和MaxPosition
  end;
  procedure ConstructMaze;
  var
    i,j:integer;
  begin
    fillchar(SokoMaze.Goals,sizeof(SokoMaze.Goals),0);
    fillchar(SokoMaze.Walls,sizeof(SokoMaze.Walls),0);
    for i:=1 to SokoMaze.X do
      for j:=1 to SokoMaze.Y do
        case Lines[i,j] of
          Char_SokoInTarget, Char_BoxInTarget, Char_Target:
            SetBit(SokoMaze.Goals,(i-1)*SokoMaze.Y j-1);
          Char_Wall:
            SetBit(SokoMaze.Walls,(i-1)*SokoMaze.Y j-1);
        end;
  end;
  procedure InitIDA;
  var
    i,j:integer;
    StartState:StateType;
  begin
    IDA.NodeCount:=0;
    IDA.TopLevelNodeCount:=0;
    fillchar(StartState,sizeof(StartState),0);
    for i:=1 to SokoMaze.X do
      for j:=1 to SokoMaze.Y do
        case Lines[i,j] of
          Char_Soko, Char_SokoInTarget:
            StartState.ManPosition:=(i-1)*SokoMaze.Y j-1;
          Char_Box, Char_BoxInTarget:
            SetBit(StartState.Boxes,(i-1)*SokoMaze.Y j-1);
        end;
    StartState.g:=0;
    IDA.StartState:=StartState;
    new(HashTable);
    for i:=1 to MaxHashEntry do
    begin
      HashTable^.FirstEntry[i]:=nil;
      HashTable^.Count[i]:=0;
    end;
  end;
begin
  ReadInputFile;
  AdjustData;
  ConstructMaze;
  InitIDA;
end;
procedure PrintState(State:StateType);
var
  i,x,y:integer;
  Map:MapType;
begin
  Map:=SokoMaze.Map;
  x:=State.ManPosition div SokoMaze.Y 1;
  y:=State.ManPosition mod SokoMaze.Y 1;
  if Map[x,y]=Char_Target then
    Map[x,y]:=Char_SokoInTarget
  else
    Map[x,y]:=Char_Soko;
  for i:=1 to MaxPosition do
    if GetBit(State.Boxes,i)>0 then
    begin
      x:=i div SokoMaze.Y 1;
      y:=i mod SokoMaze.Y 1;
      if Map[x,y]=Char_Target then
        Map[x,y]:=Char_BoxInTarget
      else
        Map[x,y]:=Char_Box;
    end;
  for i:=1 to SokoMaze.X do
    Writeln(Map[i]);
end;
function Solution(State:StateType):boolean;
var
  i:integer;
begin
  Solution:=false;
  for i:=1 to MaxPosition do
    if (GetBit(State.Boxes,i)>0) and (GetBit(SokoMaze.Goals,i)=0) then
      exit;
  Solution:=true;
end;    function CanReach(State:StateType; Position:integer):boolean;
用BFS判斷在狀態State中，搬運工是否可以到達Position
var
  Direction:integer;
  Pos,NewPos:integer;
  Get,Put:integer;
  Queue:array[0..Maxx*Maxy] of integer;
  Reached:Array[0..Maxx*Maxy] of boolean;
begin
  fillchar(Reached,sizeof(Reached),0);
  Pos:=State.ManPosition;
  Get:=0; Put:=1;
  Queue[0]:=Pos;
  Reached[Pos]:=true;
  CanReach:=true;
  while Get<>Put do
  begin
    Pos:=Queue[Get];
    inc(Get);
    if Pos=Position then
      exit;
    for Direction:=0 to 3 do
    begin
      NewPos:=Pos DeltaPos[Direction];
      if Reached[NewPos] then continue;
      if GetBit(State.Boxes,NewPos)>0 then continue;
      if GetBit(SokoMaze.Walls,NewPos)>0 then continue;
      Reached[NewPos]:=true;
      Queue[Put]:=NewPos;
      inc(Put);
    end;
  end;
  CanReach:=false;
end;
function MinPush(BoxPosition,GoalPosition:integer):integer;
在沒有其他箱子的情況下，從BoxPosition推到GoalPosition至少要多少步。
var
  i:integer;
  Direction:integer;
  Pos,NewPos,ManPos:integer;
  Get,Put:integer;
  Queue:array[0..Maxx*Maxy] of integer;
  Distance:Array[0..Maxx*Maxy] of integer;
begin
  for i:=0 to Maxx*Maxy do
    Distance[i]:=Infinite;
  Pos:=BoxPosition;
  Get:=0; Put:=1;
  Queue[0]:=Pos;
  Distance[Pos]:=0;
  while Get<>Put do
  begin
    Pos:=Queue[Get];
    inc(Get);
    if Pos=GoalPosition then
    begin
      MinPush:=Distance[Pos];
      exit;
    end;
    for Direction:=0 to 3 do
    begin
      NewPos:=Pos DeltaPos[Direction];
      ManPos:=Pos DeltaPos[Opposite[Direction]];
      人應該站在後面
if Distance[NewPos]0 then continue;
      推不動
      if GetBit(SokoMaze.Walls,ManPos)>0 then continue;
      人沒有站的地方
      Distance[NewPos]:=Distance[Pos] 1;
      Queue[Put]:=NewPos;
      inc(Put);
    end;
  end;
  MinPush:=Infinite;
end;
procedure DoMove(State:StateType; Position,Direction:integer; var NewState:Sta
teType);
var
  NewPos:integer;
begin
  NewState:=State;
  NewPos:=Position DeltaPos[Direction];
  NewState.ManPosition:=Position;
  SetBit(NewState.Boxes,NewPos);
  ClearBit(NewState.Boxes,Position);
end;
function MinMatch(BoxCount:integer;Gr:BiGraph):integer;
這個是標準算法，抄的書上的程序，不用看了。
var
  VeryBig:integer;
  TempGr:BiGraph;
  L:array[1..MaxBox*2] of integer;
  SetX,SetY,MatchedX,MatchedY:Set of 1..MaxBox;
procedure MaxMatch(n,m:integer);
function Path(x:integer):boolean;
var
  i,j:integer;
begin
  Path:=false;
  for i:=1 to m do
    if not (i in SetY)and(Gr[x,i]<>0) then
    begin
      SetY:=SetY [i];
      if not (i in MatchedY) then
      begin
        Gr[x,i]:=-Gr[x,i];
        MatchedY:=MatchedY [i];
        Path:=true;
        exit;
      end;
      j:=1;
      while (j<=m)and not (j in SetX) and (Gr[j,i]>=0) do inc(j);
      if j<=m then
      begin
        SetX:=SetX [j];
        if Path(j) then
        begin
          Gr[x,i]:=-Gr[x,i];
          Gr[j,i]:=-Gr[j,i];
          Path:=true;
          exit;
        end;
      end;
    end;
end;
var
  u,i,j,al:integer;
begin
  Fillchar(L,sizeof(L),0);
  TempGr:=Gr;
  for i:=1 to n do
    for j:=1 to m do
      if L[i]VeryBig) then
        VeryBig:=Gr[i,j];
  inc(VeryBig);
  for i:=1 to BoxCount do
    for j:=1 to BoxCount do
      if Gr[i,j]=0 then
    begin
      MinMatch:=Infinite;
      exit;
    end;
  end;
  MinMatch:=Tot