使用VB求解華容道問題
2024-07-21 02:18:48
供稿：網友
1、問題的提出
1.1“華容道”簡介
“華容道”是一種中國古代的智力游戲玩具，在一個寬為4，長為5的矩形框中，有10個棋子，包括一個曹操，五虎上將，四個小卒，要求在各個棋子不重疊的情況下進行移動，最有將曹操從棋盤上方移動到下邊中央為成功。由于五員大將可以橫放也可以豎放，有許多種排列方法，因而可以形成非常復雜的棋局，人們還給常用的棋局起了很多好聽的名字，例如下圖就是“橫刀立馬”的布局圖。
圖1.1 “橫刀立馬”的布局
關于此問題的求解方法，現在已經有許多文章詳細描述，本文不再一一描述，專門針對“廣度優先算法”方式解題進行討論。
1.2廣度優先算法的討論
我們知道，對于類似于“華容道”的問題，例如迷宮問題等，都可以歸結為圖論中圖的遍歷和最短路徑問題。也就是說，從某一個具體狀態開始作為圖的起點，每走出任意一步以后得到的狀態作為這個節點的延伸，只要保證每次走出的狀態不和原來已經走過的狀態相重復，那么就可以遍歷所有由此原始狀態可能到達的所有狀態，從而形成一張完整的倒立放置的樹圖，如下圖所示意。
圖1.2 狀態轉化示意圖
針對“華容道”問題，其實質在于如何快速構建這樣一張狀態樹圖，在數據量未知的情況下，保證快速找到最終的結果。要做到這一點，有許多算法，廣度優先是其中比較流行的一種算法。其具體思路是：
由起點出發，先構建第一層的節點，然后依次構建第二層，第三層節點，在構建的過程中，為了保證數據不重復出現，需要對每一個新節點都和原來已經生成的所有節點進行比較，保證其不重復出現在圖中。
問題則由此而產生，由于在每次增加新節點時，都需要和原來所有的節點進行比較以保證此節點不重復出現，隨著節點數量的增加，每次需要進行的比較也不斷增加，這樣就需要進行大量的時間用于比較狀態是否重復，從而形成算法效率的一個瓶頸。這也是有人認為廣度優先算法效率低下的一個重要原因。
下面將討論如何優化廣度優先算法以提高效率。
2、廣度優先算法的優化
我們現在假設已經找到了一條從起始點狀態到最終結果狀態的一條最短路徑，那么我們顯然可以得到如下的推論：
從起始點到此最短路徑上的每一個具體狀態，所走的路徑都是針對此節點狀態的最短路徑。
也就是說，我們要找到從起點到終點的最短路徑，只能夠通過行走每個節點的最短路徑來得到。
我們現在給圖中的每一個節點，都標示上其對應的最短路徑步數，形成如同下圖的一張帶有路徑步數的節點狀態樹圖。
圖2.1 帶有最短路徑步數的狀態樹圖
結合上圖，我們可以很容易得到如下的結論：
在最短路徑樹圖中，與任何級別為n的節點相連的節點，其級別必然在[n-1,n+1]之間。（結論1）
那么，從一個級別為n的節點出發，得到的所有節點，其級別也只能在(n-1,n+1)之間。因此，得到如下的結論：
要判斷從一個原始級別為n的節點產生的節點是否在圖中已經存在，僅需要判斷圖中[n-1,n+1]級別的節點集合中是否有此節點即可，如果沒有，那么此節點就是新節點。（結論2）
請注意上面所描述的結論2，根據結論2，在對于新產生節點是否重復的判斷問題上，僅需要由本級節點上溯到上二極即可，而不需要一直上溯到最開始的節點。
這樣，通過縮小對于新產生節點是否存在的判斷范圍，我們達到了對于廣度優先算法的優化目的。
3、結論
在廣度優先算法的搜索過程中，如果按照最短路徑的規則進行搜索，那么對于每次搜索產生的新節點狀態，只需要在其上兩層進行回溯判斷，就可以判斷新節點狀態是否重復，從而達到快速搜索的目的。這種對于廣度優先算法的優化同樣可以用于其它類似問題的求解，例如“八皇后問題”，迷宮行走問題，最短交通路線問題等等。
本文來源于網頁設計愛好者web開發社區http://www.html.org.cn收集整理，歡迎訪問。
