|
一之續(xù)、A*，Dijkstra，雙向BFS算法性能比較及A*算法的應(yīng)用
作者:July 二零一一年三月十日。
出處：http://blog.csdn.net/v_JULY_v
--------------------------------------------------
引言：
最短路徑的各路算法A*算法、Dijkstra 算法、BFS算法，都已在本BLOG內(nèi)有所闡述了。其中，Dijkstra 算法，后又寫了一篇文章繼續(xù)闡述：二（續(xù)）、理解Dijkstra算法。但，想必，還是有部分讀者對(duì)此類最短路徑算法，并非已了然于胸，或者，無(wú)一個(gè)總體大概的印象。 本文，即以演示圖的形式，比較它們各自的尋路過(guò)程，讓各位對(duì)它們有一個(gè)清晰而直觀的印象。
我們比較，以下五種算法：
1. A* (使用曼哈頓距離)
2. A* (采用歐氏距離)
3. A* (利用切比雪夫距離)
4. Dijkstra
5. Bi-Directional Breadth-First-Search(雙向廣度優(yōu)先搜索) 咱們以下圖為例，圖上綠色方塊代表起始點(diǎn)，紅色方塊代表目標(biāo)點(diǎn)，紫色的方塊代表障礙物，白色的方塊代表可以通行的路徑。
下面，咱們隨意擺放起始點(diǎn)綠塊，目標(biāo)點(diǎn)紅塊的位置，然后，在它們中間隨便畫一些障礙物，
最后，運(yùn)行程序，比較使用上述五種算法，得到各自不同的路徑，各自找尋過(guò)程中所覆蓋的范圍，各自的工作流程，并從中可以窺見(jiàn)它們的效率高低。
A*、Dijkstra、BFS算法性能比較演示：
ok，任意擺放綠塊與紅塊的三種狀態(tài)（演示工具來(lái)源：http://code.google.com/p/mycodeplayground/）：
一、起始點(diǎn)綠塊，與目標(biāo)點(diǎn)紅塊在同一條水平線上：
各自的搜尋路徑為：
1. A* (使用曼哈頓距離)
2. A* (采用歐氏距離) 
3. A* (利用切比雪夫距離) 
4. Dijkstra 算法.//很明顯，Dijkstra 搜尋效率明顯差于上述A* 算法。（看它最后找到目標(biāo)點(diǎn)紅塊所走過(guò)的路徑，和覆蓋的范圍，即能輕易看出來(lái)，下面的比較，也是基于同一個(gè)道理。看路徑，看覆蓋的范圍，評(píng)價(jià)一個(gè)算法的效率）。 
5. Bi-Directional Breadth-First-Search(雙向廣度優(yōu)先搜索)  二、起始點(diǎn)綠塊，目標(biāo)點(diǎn)紅塊在一斜線上： 
各自的搜尋路徑為：
1. A* (使用曼哈頓距離) 
2. A* (采用歐氏距離) 
3. A* (利用切比雪夫距離) 
4. Dijkstra 算法。 //與上述A* 算法比較，覆蓋范圍大，搜尋效率較低。  5. Bi-Directional Breadth-First-Search(雙向廣度優(yōu)先搜索)
三、起始點(diǎn)綠塊，目標(biāo)點(diǎn)紅塊被多重障礙物阻擋：
各自的搜尋路徑為（同樣，還是從綠塊到紅塊）：
1. A* (使用曼哈頓距離)
2. A* (采用歐氏距離)..
3. A* (利用切比雪夫距離)
4. Dijkstra....
5. Bi-Directional Breadth-First-Search(雙向廣度優(yōu)先搜索) //覆蓋范圍同上述Dijkstra 算法一樣很大，效率低下。
A*搜尋算法的高效之處
如上，是不是對(duì)A*、Dijkstra、雙向BFS算法各自的性能有了個(gè)總體大概的印象列?由上述演示，我們可以看出，在最短路徑搜尋效率上，一般有A*>Dijkstra、雙向BFS，其中Dijkstra、雙向BFS到底哪個(gè)算法更優(yōu)，還得看具體情況。
由上，我們也可以看出，A*搜尋算法的確是一種比較高效的尋路算法。
A*算法最為核心的過(guò)程，就在每次選擇下一個(gè)當(dāng)前搜索點(diǎn)時(shí)，是從所有已探知的但未搜索過(guò)點(diǎn)中(可能是不同層，亦可不在同一條支路上)，選取f值最小的結(jié)點(diǎn)進(jìn)行展開(kāi)。
而所有“已探知的但未搜索過(guò)點(diǎn)”可以通過(guò)一個(gè)按f值升序的隊(duì)列(即優(yōu)先隊(duì)列)進(jìn)行排列。
這樣，在整體的搜索過(guò)程中，只要按照類似廣度優(yōu)先的算法框架，從優(yōu)先隊(duì)列中彈出隊(duì)首元素（f值），對(duì)其可能子結(jié)點(diǎn)計(jì)算g、h和f值，直到優(yōu)先隊(duì)列為空(無(wú)解)或找到終止點(diǎn)為止。 A*算法與廣度、深度優(yōu)先和Dijkstra 算法的聯(lián)系就在于：當(dāng)g(n)=0時(shí)，該算法類似于DFS，當(dāng)h(n)=0時(shí)，該算法類似于BFS。且同時(shí)，如果h(n)為0，只需求出g(n)，即求出起點(diǎn)到任意頂點(diǎn)n的最短路徑，則轉(zhuǎn)化為單源最短路徑問(wèn)題，即Dijkstra算法。這一點(diǎn)，可以通過(guò)上面的A*搜索樹(shù)的具體過(guò)程中將h(n)設(shè)為0或?qū)(n)設(shè)為0而得到。 BFS、DFS與A*搜尋算法的比較
參考了算法驛站上的部分內(nèi)容：
不管以下論述哪一種搜索，都統(tǒng)一用這樣的形式表示：搜索的對(duì)象是一個(gè)圖，它面向一個(gè)問(wèn)題，不一定有明確的存儲(chǔ)形式，但它里面的一個(gè)結(jié)點(diǎn)都有可能是一個(gè)解（可行解），搜索的目的有兩個(gè)方面，或者求可行解，或者從可行解集中求最優(yōu)解。
我們用兩張表來(lái)進(jìn)行搜索，一個(gè)叫OPEN表，表示那些已經(jīng)展開(kāi)但還沒(méi)有訪問(wèn)的結(jié)點(diǎn)集，另一個(gè)叫CLOSE表，表示那些已經(jīng)訪問(wèn)的結(jié)點(diǎn)集。 蠻力搜索（BFS，DFS）
BFS（Breadth-First-Search 寬度優(yōu)先搜索）
首先將起始結(jié)點(diǎn)放入OPEN表，CLOSE表置空，算法開(kāi)始時(shí)：
1、如果OPEN表不為空，從表中開(kāi)始取一個(gè)結(jié)點(diǎn)S，如果為空算法失敗
2、S是目標(biāo)解嗎？是，找到一個(gè)解（繼續(xù)尋找，或終止算法）；不是到3
3、將S的所有后繼結(jié)點(diǎn)展開(kāi)，就是從S可以直接關(guān)聯(lián)的結(jié)點(diǎn)（子結(jié)點(diǎn)），如果不在CLOSE表中，就將它們放入OPEN表末尾，而把S放入CLOSE表，重復(fù)算法到1。 DFS（Depth-First-Search 深度優(yōu)先搜索）
首先將起始結(jié)點(diǎn)放入OPEN表，CLOSE表置空，算法開(kāi)始時(shí)：
1、如果OPEN表不為空，從表中開(kāi)始取一個(gè)結(jié)點(diǎn)S，如果為空算法失敗
2、S是目標(biāo)解嗎？是，找到一個(gè)解（繼續(xù)尋找，或終止算法）；不是到3
3、將S的所有后繼結(jié)點(diǎn)展開(kāi)，就是從S可以直接關(guān)聯(lián)的結(jié)點(diǎn)（子結(jié)點(diǎn)），如果不在CLOSE表中，就將它們放入OPEN表開(kāi)始，而把S放入CLOSE表，重復(fù)算法到1。 是否有看出：上述的BFS和DFS有什么不同？
仔細(xì)觀察OPEN表中待訪問(wèn)的結(jié)點(diǎn)的組織形式，BFS是從表頭取結(jié)點(diǎn)，從表尾添加結(jié)點(diǎn)，也就是說(shuō)OPEN表是一個(gè)隊(duì)列，是的，BFS首先讓你想到‘隊(duì)列’；而DFS，它是從OPEN表頭取結(jié)點(diǎn)，也從表頭添加結(jié)點(diǎn)，也就是說(shuō)OPEN表是一個(gè)棧！ DFS用到了棧，所以有一個(gè)很好的實(shí)現(xiàn)方法，那就是遞歸，系統(tǒng)棧是計(jì)算機(jī)程序中極重要的部分之一。用遞歸也有個(gè)好處就是，在系統(tǒng)棧中只需要存結(jié)點(diǎn)最大深度那么大的空間，也就是在展開(kāi)一個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)時(shí)可以不用一次全部展開(kāi)，用一些環(huán)境變量記錄當(dāng)前的狀態(tài)，在遞歸調(diào)用結(jié)束后繼續(xù)展開(kāi)。 利用系統(tǒng)棧實(shí)現(xiàn)的DFS
函數(shù) dfs(結(jié)點(diǎn) s)
{
s超過(guò)最大深度了嗎？是：相應(yīng)處理，返回；
s是目標(biāo)結(jié)點(diǎn)嗎？是：相應(yīng)處理；否則：
{
s放入CLOSE表；
for(c=s.第一個(gè)子結(jié)點(diǎn) ；c不為空 ；c=c.下一個(gè)子結(jié)點(diǎn)() )
if(c不在CLOSE表中)
dfs(c)；遞歸
}
} 如果指定最大搜索深度為n，那系統(tǒng)棧最多使用n個(gè)單位，它相當(dāng)于有狀態(tài)指示的OPEN表，狀態(tài)就是c，在棧里存了前面搜索時(shí)的中間變量c，在后面的遞歸結(jié)束后，c繼續(xù)后移。在象棋等棋類程序中，就是用這樣的DFS的基本模式搜索棋局局面樹(shù)的，因?yàn)槿绻肙PEN表，有可能還沒(méi)完成搜索OPEN表就暴滿了，這是難于控制的情況。 我們說(shuō)DFS和BFS都是蠻力搜索，因?yàn)樗鼈冊(cè)谒阉鞯揭粋€(gè)結(jié)點(diǎn)時(shí)，在展開(kāi)它的后續(xù)結(jié)點(diǎn)時(shí)，是對(duì)它們沒(méi)有任何‘認(rèn)識(shí)’的，它認(rèn)為它的孩子們都是一樣的‘優(yōu)秀’，但事實(shí)并非如此，后續(xù)結(jié)點(diǎn)是有好有壞的。好，就是說(shuō)它離目標(biāo)結(jié)點(diǎn)‘近’，如果優(yōu)先處理它，就會(huì)更快的找到目標(biāo)結(jié)點(diǎn)，從而整體上提高搜索性能。 啟發(fā)式搜索
為了改善上面的算法，我們需要對(duì)展開(kāi)后續(xù)結(jié)點(diǎn)時(shí)對(duì)子結(jié)點(diǎn)有所了解，這里需要一個(gè)估值函數(shù)，估值函數(shù)就是評(píng)價(jià)函數(shù)，它用來(lái)評(píng)價(jià)子結(jié)點(diǎn)的好壞，因?yàn)闇?zhǔn)確評(píng)價(jià)是不可能的，所以稱為估值。打個(gè)比方，估值函數(shù)就像一臺(tái)顯微鏡，一雙‘慧眼’，它能分辨出看上去一樣的孩子們的手，哪個(gè)很臟，有細(xì)菌，哪個(gè)沒(méi)有，很干凈，然后對(duì)那些干凈的孩子進(jìn)行獎(jiǎng)勵(lì)。這里相當(dāng)于是需要‘排序’，排序是要有代價(jià)的，而花時(shí)間做這樣的工作會(huì)不會(huì)對(duì)整體搜索效率有所幫助呢，這完全取決于估值函數(shù)。 排序，怎么排？用哪一個(gè)？快排吧，qsort！不一定，要看要排多少結(jié)點(diǎn)，如果很少，簡(jiǎn)單排序法就很OK了?？淳唧w情況了。
排序可能是對(duì)OPEN表整體進(jìn)行排序，也可以是對(duì)后續(xù)展開(kāi)的子結(jié)點(diǎn)排序，排序的目的就是要使程序有啟發(fā)性，更快的搜出目標(biāo)解。 如果估值函數(shù)只考慮結(jié)點(diǎn)的某種性能上的價(jià)值，而不考慮深度，比較有名的就是有序搜索（Ordered-Search），它著重看好能否找出解，而不看解離起始結(jié)點(diǎn)的距離（深度）。
如果估值函數(shù)考慮了深度，或者是帶權(quán)距離（從起始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的距離加權(quán)和），那就是A*，舉個(gè)問(wèn)題例子，八數(shù)碼問(wèn)題，如果不考慮深度，就是說(shuō)不要求最少步數(shù)，移動(dòng)一步就相當(dāng)于向后多展開(kāi)一層結(jié)點(diǎn)，深度多算一層，如果要求最少步數(shù)，那就需要用A*。
簡(jiǎn)單的來(lái)說(shuō)A*就是將估值函數(shù)分成兩個(gè)部分，一個(gè)部分是路徑價(jià)值，另一個(gè)部分是一般性啟發(fā)價(jià)值，合在一起算估整個(gè)結(jié)點(diǎn)的價(jià)值。 從A*的角度看前面的搜索方法，如果路徑價(jià)值為0就是有序搜索，如果路徑價(jià)值就用所在結(jié)點(diǎn)到起始結(jié)點(diǎn)的距離（深度）表示，而啟發(fā)值為0，那就是BFS或者DFS，它們兩剛好是個(gè)反的，BFS是從OPEN表中選一個(gè)深度最小的進(jìn)行展開(kāi)，
而DFS是從OPEN表中選一個(gè)深度最大的進(jìn)行展開(kāi)。當(dāng)然只有BFS才算是特殊的A*，所以BFS可以求要求路徑最短的問(wèn)題，只是沒(méi)有任何啟發(fā)性。 下文稍后，會(huì)具體談A*搜尋算法思想。 BFS、DFS、Kruskal、Prim、Dijkstra算法時(shí)間復(fù)雜度
上面，既然提到了A*算法與廣度、深度優(yōu)先搜索算法的聯(lián)系，那么，下面，也順便再比較下BFS、DFS、Kruskal、Prim、Dijkstra算法時(shí)間復(fù)雜度吧：
一般說(shuō)來(lái)，我們知道，BFS，DFS算法的時(shí)間復(fù)雜度為O（V+E），
最小生成樹(shù)算法Kruskal、Prim算法的時(shí)間復(fù)雜度為O（E*lgV）。
而Prim算法若采用斐波那契堆實(shí)現(xiàn)的話，算法時(shí)間復(fù)雜度為O（E+V*lgV），當(dāng)|V|<<|E|時(shí)，E+V*lgV是一個(gè)較大的改進(jìn)。
//|V|<<|E|，=>O（E+V*lgV） << O（E*lgV），對(duì)吧。:D
Dijkstra 算法，斐波納契堆用作優(yōu)先隊(duì)列時(shí)，算法時(shí)間復(fù)雜度為O（V*lgV + E）。
//看到了吧，與Prim算法采用斐波那契堆實(shí)現(xiàn)時(shí)，的算法時(shí)間復(fù)雜度是一樣的。 所以我們，說(shuō)，BFS、Prime、Dijkstra 算法是有相似之處的，單從各算法的時(shí)間復(fù)雜度比較看，就可窺之一二。
A*搜尋算法的思想
ok，既然，A*搜尋算法作為是一種好的、高效的尋路算法，咱們就來(lái)想辦法實(shí)現(xiàn)它吧。
實(shí)現(xiàn)一個(gè)算法，首先得明確它的算法思想，以及算法的步驟與流程，從我之前的一篇文章中，可以了解到：
A*算法，作為啟發(fā)式算法中很重要的一種，被廣泛應(yīng)用在最優(yōu)路徑求解和一些策略設(shè)計(jì)的問(wèn)題中。
而A*算法最為核心的部分，就在于它的一個(gè)估值函數(shù)的設(shè)計(jì)上：
f(n)=g(n)+h(n) 其中f(n)是每個(gè)可能試探點(diǎn)的估值，它有兩部分組成：
一部分，為g(n)，它表示從起始搜索點(diǎn)到當(dāng)前點(diǎn)的代價(jià)（通常用某結(jié)點(diǎn)在搜索樹(shù)中的深度來(lái)表示）。
另一部分，即h(n)，它表示啟發(fā)式搜索中最為重要的一部分，即當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估值， h(n)設(shè)計(jì)的好壞，直接影響著具有此種啟發(fā)式函數(shù)的啟發(fā)式算法的是否能稱為A*算法。 一種具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是： 1、搜索樹(shù)上存在著從起始點(diǎn)到終了點(diǎn)的最優(yōu)路徑。
2、問(wèn)題域是有限的。
3、所有結(jié)點(diǎn)的子結(jié)點(diǎn)的搜索代價(jià)值>0。
4、h(n)=<h*(n) （h*(n)為實(shí)際問(wèn)題的代價(jià)值）。 當(dāng)此四個(gè)條件都滿足時(shí)，一個(gè)具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法，并一定能找到最優(yōu)解。
對(duì)于一個(gè)搜索問(wèn)題，顯然，條件1,2,3都是很容易滿足的，而條件4： h(n)<=h*(n)是需要精心設(shè)計(jì)的，由于h*(n)顯然是無(wú)法知道的，所以，一個(gè)滿足條件4的啟發(fā)策略h(n)就來(lái)的難能可貴了。 不過(guò)，對(duì)于圖的最優(yōu)路徑搜索和八數(shù)碼問(wèn)題，有些相關(guān)策略h(n)不僅很好理解，而且已經(jīng)在理論上證明是滿足條件4的，從而為這個(gè)算法的推廣起到了決定性的作用。
A*搜尋算法的應(yīng)用
ok，咱們就來(lái)應(yīng)用A*搜尋算法實(shí)現(xiàn)八數(shù)碼問(wèn)題，下面，就是其主體代碼，由于給的注釋很詳盡，就不再啰嗦了，有任何問(wèn)題，請(qǐng)不吝指正：
//節(jié)點(diǎn)結(jié)構(gòu)體
typedef struct Node
{
int data[9];
double f,g;
struct Node * parent;
}Node,*Lnode; //OPEN CLOSED 表結(jié)構(gòu)體
typedef struct Stack
{
Node * npoint;
struct Stack * next;
}Stack,* Lstack; //選取OPEN表上f值最小的節(jié)點(diǎn)，返回該節(jié)點(diǎn)地址
Node * Minf(Lstack * Open)
{
Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open);
Node * minx;
while(temp->next != NULL)
{
if((temp->next ->npoint->f) < (min->npoint->f))
{
min = temp->next;
minp = temp;
}
temp = temp->next;
}
minx = min->npoint;
temp = minp->next;
minp->next = minp->next->next;
free(temp);
return minx;
} //判斷是否可解
int Canslove(Node * suc, Node * goal)
{
int a = 0,b = 0,i,j;
for(i = 1; i< 9;i++)
for(j = 0;j < i;j++)
{
if((suc->data[i] > suc->data[j]) && suc->data[j] != 0)
a++;
if((goal->data[i] > goal->data[j]) && goal->data[j] != 0)
b++;
}
if(a%2 == b%2)
return 1;
else
return 0;
} //判斷節(jié)點(diǎn)是否相等 ，1相等，0不相等
int Equal(Node * suc,Node * goal)
{
for(int i = 0; i < 9; i ++ )
if(suc->data[i] != goal->data[i])return 0;
return 1;
} //判斷節(jié)點(diǎn)是否屬于OPEN表 或 CLOSED表，是則返回節(jié)點(diǎn)地址，否則返回空地址
Node * Belong(Node * suc,Lstack * list)
{
Lstack temp = (*list) -> next ;
if(temp == NULL)return NULL;
while(temp != NULL)
{
if(Equal(suc,temp->npoint))return temp -> npoint;
temp = temp->next;
}
return NULL;
} //把節(jié)點(diǎn)放入OPEN 或CLOSED 表中
void Putinto(Node * suc,Lstack * list)
{
Stack * temp;
temp =(Stack *) malloc(sizeof(Stack));
temp->npoint = suc;
temp->next = (*list)->next;
(*list)->next = temp;
} ///////////////計(jì)算f值部分-開(kāi)始//////////////////////////////
double Fvalue(Node suc, Node goal, float speed)
{//計(jì)算f值
double Distance(Node,Node,int);
double h = 0;
for(int i = 1; i <= 8; i++)
h = h + Distance(suc, goal, i);
return h*speed + suc.g; //f = h + g（speed值增加時(shí)搜索過(guò)程以找到目標(biāo)為優(yōu)先因此可能不會(huì)返 回最優(yōu)解）
}
double Distance(Node suc, Node goal, int i)
{//計(jì)算方格的錯(cuò)位距離
int k,h1,h2;
for(k = 0; k < 9; k++)
{
if(suc.data[k] == i)h1 = k;
if(goal.data[k] == i)h2 = k;
}
return double(fabs(h1/3 - h2/3) + fabs(h1%3 - h2%3));
}
///////////////計(jì)算f值部分-結(jié)束////////////////////////////// ///////////////////////擴(kuò)展后繼節(jié)點(diǎn)部分的函數(shù)-開(kāi)始/////////////////
int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed)
{//判斷子節(jié)點(diǎn)是否屬于OPEN或CLOSED表 并作出相應(yīng)的處理
Node * temp = NULL;
int flag = 0;
if((Belong(*suc,Open) != NULL) || (Belong(*suc,Closed) != NULL))
{
if(Belong(*suc,Open) != NULL) temp = Belong(*suc,Open);
else temp = Belong(*suc,Closed);
if(((*suc)->g) < (temp->g))
{
temp->parent = (*suc)->parent;
temp->g = (*suc)->g;
temp->f = (*suc)->f;
flag = 1;
}
}
else
{
Putinto(* suc, Open);
(*suc)->f = Fvalue(**suc, goal, speed);
}
return flag;
} void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, float speed)
{//擴(kuò)展后繼節(jié)點(diǎn)總函數(shù)
int i;
Node * child;
for(i = 0; i < 4; i++)
{
if(Canspread(**suc, i+1)) //判斷某個(gè)方向上的子節(jié)點(diǎn)可否擴(kuò)展
{
child = (Node *) malloc(sizeof(Node)); //擴(kuò)展子節(jié)點(diǎn)
child->g = (*suc)->g +1; //算子節(jié)點(diǎn)的g值
child->parent = (*suc); //子節(jié)點(diǎn)父指針指向父節(jié)點(diǎn)
Spreadchild(child, i); //向該方向移動(dòng)空格生成子節(jié)點(diǎn)
if(BelongProgram(&child, Open, Closed, goal, speed)) // 判斷子節(jié)點(diǎn)是否屬 于OPEN或CLOSED表 并作出相應(yīng)的處理
free(child);
}
}
}
///////////////////////擴(kuò)展后繼節(jié)點(diǎn)部分的函數(shù)-結(jié)束////////////////////////////////// Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, float speed)
{//總執(zhí)行函數(shù)
while(1)
{
if((*Open)->next == NULL)return NULL; //判斷OPEN表是否為空，為空則失敗退出
Node * minf = Minf(Open); //從OPEN表中取出f值最小的節(jié)點(diǎn)
Putinto(minf, Closed); //將節(jié)點(diǎn)放入CLOSED表中
if(Equal(minf, *goal))return minf; //如果當(dāng)前節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則成功退出
Spread(&minf, Open, Closed, **goal, speed); //當(dāng)前節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)時(shí)擴(kuò)展當(dāng)前節(jié)點(diǎn)的后繼 節(jié)點(diǎn)
}
} int Shownum(Node * result)
{//遞歸顯示從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的移動(dòng)方法
if(result == NULL)return 0;
else
{
int n = Shownum(result->parent);
for(int i = 0; i < 3; i++)
{
printf("/n");
for(int j = 0; j < 3; j++)
{
if(result->data[i*3+j] != 0)
printf(" %d ",result->data[i*3+j]);
else printf(" ");
}
}
printf("/n");
return n+1;
}
} 完。July、二零一一年三月十日。
|
