人工智能

九宮格重移一一搜索

成員：趙春杰

羊森

黃鑫2023210

周成兵

王素娟

1.問題描述:

八數(shù)碼問題也稱為九宮問題。在3義3的棋盤，擺有八個棋子，每個棋子上標有1至8

的某一數(shù)字，不同棋子上標的數(shù)字不相同。棋盤上尚有一個空格，與空格相鄰的棋子可以移

到空格中。規(guī)定解決的問題是:給出一個初始狀態(tài)和一個目的狀態(tài)，找出一種從初始轉(zhuǎn)變成

目的狀態(tài)的移動棋子步數(shù)最少的移動環(huán)節(jié)。所謂問題的一個狀態(tài)就是棋子在棋盤上的一種擺

法。棋子移動后，狀態(tài)就會發(fā)生改變。解八數(shù)碼問題事實上就是找出從初始狀態(tài)到達目的狀

態(tài)所通過的一系列中間過渡狀態(tài)。

2.九宮重移有無答案檢查(逆序數(shù))

我們把每個9宮格橫向展開，如第一個,我們把左邊數(shù)大于右邊數(shù)的組數(shù)稱

為這個九宮格的逆序數(shù)，顯然的逆序數(shù)為0；考慮橫向平移，那么逆序數(shù)的增量

為2或0或-2；縱向平移，逆序數(shù)的增量為4或0或-4;但的逆序數(shù)為奇數(shù)。所以

是無解的情況。由此也可以類推當將9宮格展開后，假如數(shù)據(jù)序列的逆序數(shù)為奇

數(shù),則此數(shù)據(jù)序列相應(yīng)的九宮格是無解的。

4.BFS算法

隊列：Queueopen=newQueue();存放待擴展的節(jié)點

List:List<Bfstr>c1osed=newList<Bfstr>();存放已被擴展過

的節(jié)點

ArrayListmap=newArrayList();//存放答案

HashTale：Hashtabletable=newHashtab1e();構(gòu)造哈希表以方便

查找

3.1.BFS算法介紹

廣度優(yōu)先搜索算法BFS基本思想:從圖中某頂點v出發(fā),逐層對節(jié)點進行拓展,并考察是

否為目的節(jié)點,在第n層節(jié)點沒有所有擴展并考察前,不對第n+1層節(jié)點進行擴展。

對九宮重排問題，即構(gòu)造廣度優(yōu)先搜索樹，從初始狀態(tài)，運用廣度優(yōu)先搜索算法逐步找

到目的狀態(tài)的節(jié)點。

3.2.狀態(tài)空間表達

狀態(tài)空間用一維數(shù)組表達，每個節(jié)點存放在Bfstr結(jié)構(gòu)體中的字符now中，從第一行

開始從左往右給九宮格標號0……8,字符串now元素下標代表格子位置,而now數(shù)組中相應(yīng)

數(shù)組的值代表九宮格中存放的數(shù)碼，用數(shù)值9代表空格。

3.3.搜索樹

3.4.算法環(huán)節(jié)

搜索：

(1)把初始節(jié)點so放入OPEN表。

(2)假如OPEN表為空，則問題無解,退出。

(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出放入CLOSE表。

(4)考察節(jié)點n是否為目的節(jié)點。若是,則求得了問題的解，退出。

(5)若節(jié)點n不可擴展，則轉(zhuǎn)第2步。

(6)擴展節(jié)點n,將其子節(jié)點放入OPEN表的尾部,并為每一個子節(jié)點都配置指向父節(jié)

點的指針，然后轉(zhuǎn)第2步。

擴展fun()：

(1)取open中第一個節(jié)點a加入到closed中

(2)找到a[9]中值為9(空格)的位置i;

(3)當。pen中元素個數(shù)不為0時，循環(huán)執(zhí)行(3)到()

3.1從open中取出一個元素(狀態(tài))，并加入到closed中，對這個狀態(tài)擴展;

3.2若空格在第2、3歹％向左移動得到新狀態(tài)；

新狀態(tài)不是目的狀態(tài)，就加入open中；

新狀態(tài)是目的狀態(tài)，就加入closed中，編號加1,結(jié)束算法；

3.3若空格在第2、3行，向上移動得到新狀態(tài)

新狀態(tài)不是目的狀態(tài),就加入open中，

新狀態(tài)是目的狀態(tài),就加入cI。sed中,編號加1,結(jié)束算法；

3.4若空格在第1、2歹IJ,向右移動得到新狀態(tài)

新狀態(tài)不是目的狀態(tài)，就加入open中，

新狀態(tài)是目的狀態(tài),就加入closed中,編號加1,結(jié)束算法；

3.5若空格在第1行，向下移動得到新狀態(tài)

新狀態(tài)不是目的狀態(tài)，就加入。Pen中，

新狀態(tài)是目的狀態(tài)，就加入closed中,編號加1,結(jié)束算法；

3.5.算法流程圖

4.啟發(fā)式A*算法

隊列：Queueopen=newQueue();存放待擴展的節(jié)點

List:List<Bfstr>closed=newList<Bfstr>();存放已被擴展過的節(jié)

點

ArrayListmap=newArrayList();//存放答案

HashTaie:Hashtabletab1e=newHashtable();構(gòu)造哈希表以方便查找

sort排序

4.1.算法介紹

算法A不能保證當圖中存在從起始節(jié)點到目的節(jié)點的最短途徑時,一定能找到它，

而A*中評估函數(shù)f*(n)=g*(n)+f*(n)保證途徑存在時，一定能找到。算法A中，

g(n)和h(n)是g*(n)和f*(n)的近似估價。假如對于所有節(jié)點h(n)<g*(n),則它

就稱為A*算法：

4.2.狀態(tài)空間表達

狀態(tài)空間用一維數(shù)組表達，每個節(jié)點存放在Bfstr結(jié)構(gòu)體中的字符now中，從第

一行開始從左往右給九宮格標號0……8,字符串now元素下標代表格子位置，而now

數(shù)組中相應(yīng)數(shù)組的值代表九宮格中存放的數(shù)碼,用數(shù)值9代表空格。

4.3.搜索樹

4.4.算法環(huán)節(jié)

算法描述:

3.1把初始節(jié)點SO放入OPEN表，并建立目前只包含SO的圖，記為G；

3.2檢查OPEN表是否為空,若為空則問題無解,退出；

3.3把OPEN表的第一個節(jié)點取出放入CLOSE表，并計該節(jié)點為n;

3.4考察節(jié)點n是否為目的節(jié)點。若是，則求得了問題的解,退出；

3.5擴展節(jié)點n,生成一組子節(jié)點。把其中不是節(jié)點n先輩的那些子節(jié)點記做集合M,

并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中：

3.6針對M中子節(jié)點的不同情況，分別進行如下解決：

3.6.1對于那些未曾在G中出現(xiàn)過的M成員設(shè)立一個指向父節(jié)點（即節(jié)點n）的指針,

并把它們放入OPEN表；（不在OPEN表）

3.6.2對于那些先前已經(jīng)在G中出現(xiàn)過的M成員，擬定是否需要修改它指向父節(jié)點的

指針；（在OPEN表中，對g（x）進行更新）

3.6.3對于那些先前已在G中出現(xiàn)并且已經(jīng)擴展了的M成員，擬定是否需要修改其后

繼節(jié)點指向父節(jié)點的指針；（在CLOSE表中，對節(jié)點n子節(jié)點的子節(jié)點更新g

（x））

3.7對OPEN表中的節(jié)點按估價函數(shù)進行排序；

3.8轉(zhuǎn)第2步。

4.5.算法流程圖

開始

5.啟發(fā)式A算法

隊列：Queueop6n=newQueue();存放待擴展的節(jié)點

List:List<Bfstr>closed=newList<Bfstr>();存放已被擴展過的節(jié)

點

ArrayListmap=newArrayLis10;〃存放答案

HashTa1e:Hashtabletable=newHashtable();構(gòu)造哈希表以方便查找sor

t排序

5.1算法介紹

啟發(fā)式搜索算法A,一般簡稱為A算法,是一種典型的啟發(fā)式搜索算法。其基本

思想是:定義一個評價函數(shù)f,對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來

擴展。

評價函數(shù)的形式如下：Af(n)=g(n)+h(n);其中n是被評價的節(jié)點。為說明：

g*(n):表達從初始節(jié)點s到節(jié)點n的最短途徑的耗散值；4*(n):表達從節(jié)點n

到目的節(jié)點g的最短途徑的耗散值；

f*(n)=g*(n)+h*(n):表達從初始節(jié)點s通過節(jié)點n到目的節(jié)點g的最短途徑

的耗散值。而f(n)>g(n)和h(n)則分別表達是對f*(n)、g*(n)和h*(n)三

個函數(shù)值的的估計值。是一種預測。A算法就是運用這種預測，來達成有效搜索的

目的的。它每次按照f(n)值的大小對OPEN表中的元素進行排序,f值小的節(jié)點放

在前面,而f值大的節(jié)點則被放在0PEN表的后面,這樣每次擴展節(jié)點時,都是選擇

當前f值最小的節(jié)點來優(yōu)先擴展。

5.2.狀態(tài)空間表達

狀態(tài)空間用一維數(shù)組表達,每個節(jié)點存放在Bfstr結(jié)構(gòu)體中的字符now中,從第一行開

始從左往右給九宮格標號0……8,字符串now元素下標代表格子位置,而now數(shù)組

中相應(yīng)數(shù)組的值代表九宮格中存放的數(shù)碼,用數(shù)值9代表空格。

5.3.搜索樹

K(5)

5.4.算法環(huán)節(jié)

5.1建立一個只含初始節(jié)點So的搜索圖G,把So放入Open表，并計算f(So)的值;

5.2假如Open表是空的，則失敗，否則，繼續(xù)下一步；

5.3從Open表中取出f值為最小的結(jié)點,置于C1。se表,給這個結(jié)點編號為n；

5.4假如n是目的結(jié)點，則得解，算法成功退出。此解可從目的結(jié)點開始到初始節(jié)點的

返回指針中得到。否則，繼續(xù)下一步；

5.5擴展結(jié)點n。生成一組子節(jié)點。把其中不是節(jié)點n先輩的那些子節(jié)點記做集合M,

并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中；

5.6對于那些未曾在G中出現(xiàn)過的M成員設(shè)立一個指向父節(jié)點(即節(jié)點n)的指針，并把

它們放入OPEN表；

5.7對于那些先前已經(jīng)在G中出現(xiàn)過的M成員，擬定是否需要修改它指向父節(jié)點的指

針；(在OPEN表中，對g(x)進行更新)

5.8對于那些先前已在G中出現(xiàn)并且已經(jīng)擴展了的M成員，擬定是否需要修改其后繼節(jié)

點指向父節(jié)點的指針；(在CLOSE表中，對節(jié)點n子節(jié)點的子節(jié)點更新g(x))

5.9按f值從大至小的順序,對0pen表中的結(jié)點重新排序；

5.10返回環(huán)節(jié)2。

5.5算法流程圖

開始

V

v

6.數(shù)生成算法

6.1.算法介紹

在數(shù)據(jù)結(jié)構(gòu)、算法分析與設(shè)計、科學模擬等方面都需要用到數(shù)。由于在數(shù)學上，整數(shù)是

離散型的,實數(shù)是連續(xù)型的,而在某一具體的工程技術(shù)應(yīng)用中，也許尚有數(shù)據(jù)值的范圍性和是

否可反復性的規(guī)定。因此，我們就整數(shù)數(shù)和實數(shù)數(shù)，以及它們的數(shù)據(jù)值的范圍性和是否可反

復性，分別對其算法加以分析和設(shè)計。

1>MicrosoftVC++產(chǎn)生數(shù)的原理：

Srand()和Rand()函數(shù)。它本質(zhì)上是運用線性同余法，y=ax+b(modm)(,其中

a,b,m都是常數(shù)。因此rand的產(chǎn)生決定于x,x被稱為Seed。Seed需要程序中設(shè)定,一般

情況下取系統(tǒng)時間作為種子。它產(chǎn)生的數(shù)之間的相關(guān)性很小，取值范圍是0—32767(i

nt),即雙字節(jié)(16位數(shù))，若用unsignedint雙字節(jié)是65535,四字節(jié)是，一般

可以滿足規(guī)定。

根據(jù)整數(shù)數(shù)范圍性和是否可反復性，可分為：

(1)某范圍內(nèi)可反復。

(2)某范圍內(nèi)不可反復。

(3)枚舉可反復。

(4)枚舉不可反復。

所謂范圍，是指在兩個數(shù)nl和n2之間。例如,在100和200之間這個范圍，那么，只

要產(chǎn)生的整數(shù)數(shù)n滿足100WnW200,都符合規(guī)定。所謂枚舉，是指有限的、己知的、若

干個不連續(xù)的整數(shù)。例如,34、20、123、5、800這5個整數(shù)就是一種枚舉數(shù)，也就是單

獨可以一個個擬定下來。某范圍內(nèi)可反復

在VisualBasic語言中，有一個數(shù)函數(shù)Rnd。

語法：Rnd[(number)]。

參數(shù)number可選,number的值決定了Rnd生成數(shù)的方式。Rnd函數(shù)返回小

于1但大于或等于0的值。

Number類型Rnd結(jié)果

小于零每次都相同的數(shù)字,并將number用作種子。

大于零序列中的下一個數(shù)。

等于零最近生成的數(shù)字。

未提供序列中的下一個數(shù)。

在調(diào)用Rnd之前，先使用無參數(shù)的Randomize語句初始化數(shù)生成器，該生成

器具有一個基于系記錄時器的種子。

若要生成某給定范圍內(nèi)的整數(shù),可使用以下公式：

Int((upperbound—lowerbound+1)*Rnd+lowerbound)

這里，upperbound是此范圍的上限，而lowerbound是范圍的下限

6.2.程序流程圖：

7.DFS

黃鑫負責部分(請注意與上面的格式搭配一下)

8.效果圖

滑塊問題求解系統(tǒng)

(1)DFS時當顯示只需2、3步時,搜索空間爆棧，內(nèi)存溢出，失敗。

暫時解決辦法:重新生成結(jié)束狀態(tài)或者初始狀態(tài)

(2)BFS、A、A*時顯示32步時,搜索空間太多，內(nèi)存溢出，失敗。

暫時解決辦法:重新生成結(jié)束狀態(tài)或者初始狀態(tài)

(3)不能同時生成結(jié)束狀態(tài)圖和初始狀態(tài)圖。

暫時解決辦法:分步生成結(jié)束狀態(tài)或者初始狀態(tài)

(4)未完畢工作:

1、時間顯示

2、自動演示

8.1初始界面：

8.3.BFS效果圖:

8.3.啟發(fā)式A*效果圖:

震滑塊問題求解系統(tǒng)1.0人工智能實會

狀態(tài)空洵的窮搜索發(fā)搜索給果

I顯示時間］

O簡單深度優(yōu)先搜索O啟發(fā)式搜索算法A搜索結(jié)果為：用啟發(fā)式搜索A*共需要23步

■簡單廣度優(yōu)先搜索O啟發(fā)式搜索篁法A*

「并品捶素T

算法說明

定義e采第生）:江果

一個恬外宣數(shù)可以技㈢

戴三之於任，或G稱之

法仝AW必具考￥夫充

生，"算法是一，、可關(guān)

弟式能好代光算法.

8.4啟發(fā)式A效果圖:

8.5.DFS效果圖:

身滑塊問題求解系統(tǒng)1.0人工智能實險

狀態(tài)空間的窮搜索發(fā)搜索結(jié)果

I顯示時間］

O簡單深度優(yōu)先搜索O啟發(fā)式搜索篁法A搜索結(jié)果為：用BPS共需要25步

＞簡單廣度優(yōu)先搜索O啟發(fā)式搜索篁法A*

『弄捶素|

結(jié)束狀態(tài)

□手動模式菖法說明

定又:以斐近起更FW

K程度常依弊，逐疔逐

I下一步I蕓三展替，點搜索方法

=純.不授索是逐W之

I恢復初始狀I(lǐng)不在，即左封七一里時

任一七點進嚀按森之前

，搜索充女三憶尸

自動演示考中點：一玷曼什什搜

案，但若有鋁￡在，

必轉(zhuǎn)換到它.

當前步數(shù)：

0

9.代碼

共涉及3個工程文獻：CommonRANDYYSEN

工程文獻名類名功能代碼行數(shù)

CommonAse.cs實現(xiàn)A算法約350行

CommonAstr.csA算法的解空間27

CommonBfs.cs實現(xiàn)廣度優(yōu)先算法220

CommonBfstr?cs廣度優(yōu)先算法的解空間15

CommonBse.cs實現(xiàn)A*算法35

Commoncommon,cs公用方法72

CommonDfs.cs實現(xiàn)深度優(yōu)先算法250

CommonDfstr.cs深度優(yōu)先算法解空間15

RANDRandNum.es生成地圖55

YYYSENForml.esWindows功能實現(xiàn)290

YYYSENForml.DesigneWindows界面設(shè)660

r.cs計

YYYSENProgram.csWindows界面入口21

1、classAse實現(xiàn)啟發(fā)式A算法

usingSystem;

usingSystem.Colleclions.Generic;

usingSystem.Text;

usingSystem.Col1ections;

〃約350行

namespaceCommon

(

pub1icclassAse

(

privateint[]SS=newint[9];

privateintE]NN=newint[9];

privatestringS；

privatestringN；

pub1icboolBOOL;//是否有解：

List<Astr>open=newList<Astr>()J/未搜索；

LisKAstr>closed=newList<Astr>()；〃已搜索;

HashtabIetable=newHashtable()；

pubIicAnayListmap=newArrayList();

publicAse(int[]SS,int[]NN)

(

SS.CopyTo(this.SS,0);

NN.CopyTo(this.NN,0)；

S=common.changestring(SS)；

N=common.changestring(NN);

BOOL=common.chcck(this.SS,this.NN,this.SS.Length);

)

publievoidsearch()

{

//呵呵，調(diào)用其他的搜索,不解釋

Bfsansbfs=newBfs(this.SS,this.NN);

ansbfs.search()；

map=ansbfs.map;

return;

if(S!=N)

(

Astrnode=newAstr();

node.now=S;

node.qian=""；

node.gn=0;

node.wn=fwn(S,N)；

node.fn=node.gn+node.wn；

open.Add(node);

table.Add(node.now,node.gn)；

fun();

1

//構(gòu)造最佳答案;

inti0；

Astrp=closed[closed.Count-1]；

closed.Remove(p);

map.Add(p.now);

while(p.now!=S)

(

for(i=0；i<closed.Count;i++)

(

if(closed[i].now==p.qian)

(

map.Add(closed|i].now)；

p=closed[i];

closed.Remove(p);

break;

1

)

)

//互換

intj=0;

fbr(i=0,j=map.Count-1；i<j;i++,j--)

(

stringsss=map[i]asstring;

map[i]=map[j];

map[j]

)

)

//互換值

privatevoidswap(int[]a,intx,inty)

(

intt;

t=a[x];

a[x]=a[y];

a[y]=t;

1

privateintfwn(strings1,strings2)

(

inti；

intsum=0;

for(i=0;i<sl.Length;i++)

(

if(s1[i]!=s2[i])

sum++;

1

returnsum;

}

//

privatevoidfun()

Astrnode_1=newAstr()；

Astrnode_2=newAstr()；

//Astrnode_3=newAstr();

int[]a=newint[9]；

int[]b=newint[9];

strings;

intcount=0;

while(true&&open.Count!=0)

(

if(count++>10000)

retum；

//找最小元素

//list.Sort((x,y)=>y.Age-x.Age);排序

inti=0;

//去open中的fn最小值

node_1=open[i]；

for(i=0;i<open.Count;i++)

(

if(node_1.fn>=openLi],fn)

(

node_l=open[i];

)

)

open.Remove(node—1);

closed.Add(node_l);

if(nodc_l.now==N)

retum；

a=common.changeint(node_1.now);

for(i=0；i<a.Length：i++)

(

if(a[i]==9)

break;

)

intindex=i；

if(i%3!=0)

(

a.CopyTo(b,0);

swap(b,i,i-1)；

s=common.changestring(b);

node_2.now=s;

node_2.qian=node_l.now;

node_2.gn=node_l.gn+1；

node_2.wn=fwn(s,N);

node_2.fn=node_2.gn+node_2.wn;

intj=0;

for(j=0；j<open.Count;j++)

if(open[j].now==node_2.now)

if(open|j].gn>node_2.gn)

(

open.RemoveAt(j)；

open.Add(node_2);

table|node_2.now]=node_2.gn;

)

break;

)

}

intk：

for(k=0;k<closed.Count;k++)

(

if(closed|k].now==node_2.now)

(

if(c1osedEk].gn>node_2.gn)

(

closed.RemoveAt(k);

closed.Add(node_2);

table[node_2.now]=node_2.gn;

)

break；

)

)

if(j==open.Count)

(

if(k==closed.Count)

I

open.Add(node_2);

tabie.Add(node_2.now,node_2.gn);

)

)

)

if(i-3>=0)

(

a.CopyTo(b,0);

swap(b,i,i-3);

s=common.changestring(b)；

node_2.now=s;

node_2.qian=node_l.now;

node_2.gn=node_l.gn+1;

node_2.wn=fwn(s,N);

node_2.fn=node_2.gn+node_2.wn;

intj=0；

for(j=0;j<open.Count;j++)

if(open[j].now==node_2.now)

(

if(open[j].gn>node_2.gn)

(

open.RemoveAt(j)；

open.Add(node_2)；

tab1e[node_2.now]=node_2.gn;

)break；

)

)

intk;

for(k=0;k<closed.Count；k++)

(

if(closed[k].now==node_2.now)

(

if(c1osed[k].gn>node_2.gn)

(

closed.RemoveAt(k)：

closed.Add(node_2)；

table[node_2.now]=node_2.gn；

)break;

)

if(j==open.Count&&k==closed.Count)

(

open.Add(node_2);

tab1e.Add(node_2.now,node_2.gn);

)

}

if(i%3!=2)

a.CopyTo(b,0);

swap(b,i,i+1);

s=common,changestring(b);

node_2.now=s;

node_2.qian=node」.now;

node_2.gn=node_l.gn+1;

node_2.wn=fwn(s,N);

node_2.fn=node_2.gn+node_2.wn；

intj=0;

for(j=0;j<open.Count;j++)

if(opcn|j].now==node_2.now)

if(open[j].gn>node_2.gn)

open.RemoveAt(j);

open.Add(node—2);

tab1e[node_2.now]=node_2.gn；

}break;

)

)

intk;

for(k=0；k<closed.Count;k++)

(

if(closed[k].now==node_2.now)

(

if(closed[k].gn>node_2.gn)

(

closed.RemoveAt(k)；

c1osed.Add(node_2);

tablc[node_2.now]=node_2.gn；

}break；

)

if(j==open.Count&&k==c1osed.Count)

open.Add(node_2);

table.Add(node_2.now,node_2.gn);

)

I

if(i+3<9)

a.CopyTo(b,0);

sw叩(b,i,i+3)；

s=common.changestring(b);

node_2.now=s;

node_2.qian=node_l.now;

node_2.gn=node_l.gn+1；

node_2.wn=fwn(s,N)；

node_2.fn=node_2,gn+node_2.wn;

intj=O;

fbr(j=0;j<open.Count;j++)

(

if(open[j].now==node_2.now)

if(open[j].gn>node_2.gn)

open.RcmoveAt(j);

open.Add(node_2);

tablcfnode_2.now]=node_2.gn;

]break;

)

)

inik;

for(k=0;k<closed.Count;k++)

(

if(closed[k].now==node_2.now)

(

if(closed[k].gn>node_2,gn)

(

closed.RemoveAt(k);

closed.Add(node_2);

table[node_2.now]=node_2.gn;

}break：

)

)

if(j==open.Count&&k==cIosed.Count)

{

open.Add(node_2);

tab1c.Add(node_2.now,node_2.gn);

}

)

)

1

(

2classAstr重要是啟發(fā)式搜索算法A算法的解空間

usingSystem；

usingSystem.Collections.Generic；

usingSystem.Text;

//27

namespaceCommon

(

structAstr

{

publicstringnow{get；set;}

///<summary>

///從起始點到n的途徑長度

///</summary>

pub1icintgn{get;set;}

///〈summary〉

///代表節(jié)點n的格局與目的節(jié)點的格局相比文職不符的數(shù)目

///</sunnnary>

publicintwn{get；set；}

///<summary>

///fn=gn+wn;

///</summary>

publicintfn{get；set;}

///<summary>

///前一個的狀態(tài)；

///</summary>

pub1icstringqian{get；st

)

)

3、BFS重要是完畢廣度優(yōu)先搜索功能

usingSystem;

usingSystem.Co1lections.Generic;

usingSystem.Text;

usingSystem.Co11ections;

//220

namespaceCommon

(

publicclassBfs

(

privateint[]SS=newint[9];

privateint[]NN=newint[9]；

privatestringS;

privatestringN;

pub1icboolBOOL;//是否有解;

Hashtabletab1e=newIIashtab1e()；

Queueopen=newQueue();

List<Bfstr>closed=newList<Bfstr>();

publicArrayListmap=newArrayList();

pub1icBfs(int[]SS,int[]NN)

(

SS.CopyTo(this.SS,0);

NN.CopyTo(this.NN,0);

S=common.changestring(SS);

N=common.changestring(NN);

BOOL=common,check(this.SS,this.NN,this.SS.Le

ngth)；

)

privatevoidswap(inl[]a,intx,inty)

{

intt;

t=a[x]；

a[x]=a[y];

a[y]=t;

publicvoidsearch()

if(S!=N)

Bfstrnode=newBfstr();

node.now=S；

node.qian="”；

node,tol=0；

open.Enqueue(node)；

tabie.Add(S,0);

fun();

)

eIse

(

Bfstrnode=newBfstr();

node.now=S;

node.qian="”；

node.tol=0；

closed.Add(node);

I

inti=0;

//在ck>sed中去尋找答案

Bfstip=newBfstr()；

p=closed[closed.Count-1];

closed.Remove(p)；

map.Add(p.now);

while(p.now!=S)

for(i=0;i<closed.Count;i++)

(

if(closed[i].now==p.qian)

(

map.Add(closed[i].now);

p=closed[i]；

closed.Remove(p);

break;

)

)

)

intj=0;

for(i=0,j=map.Count—1;i<j;i++,j--)

(

stringsss=map[i]asstring;

map[i]=map[j];

mapLj]=sss;

privatevoidfun()

Bfstrnode_0=newBfstr()；

Bfstrnode_l=newBfstr()；

int[]a=newint[9];

int[]b=newint[9J;

strings;

while(open.Count!=0)

(

//取open中的第一個節(jié)點；

node_0=(Bfstr)(open.Dequeue());

closed.Add(node_0);

//

a=conunon.changeint(node_0.now);

inti=0;

for(i=0;i<a.Length;i++)

(

if(a[i]==9)

break;

)

intindex=i；

if(index%3!=0)

(

a.CopyTo(b,0);

swap(b,i,i-1);

s=common.changestring(b);

if(s!=N)

(

if(!table.Contains(s))

(

node_1.now=s;

node_l.qian=node_0.now;

node_l.to1=node_0.tol+1;

open.Enqueue(node_1)；

table.Add(s,node_l.to1);

)

else

(

node_1.now=s;

node_l.qian=node_O.now;

node_1.to1=node_0.tol+1；

table.Add(s,node_1.to1);

c1ose