人工智能實(shí)驗(yàn)報(bào)告

.人工智能九宮格重移搜索成員：趙春杰 2009210665羊森 2009210653黃鑫 2009210周成兵 2009210664王素娟 20092106441.問題描述：八數(shù)碼問題也稱為九宮問題。在33的棋盤，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字，不同棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)棋子步數(shù)最少的移動(dòng)步驟。所謂問題的一個(gè)狀態(tài)就是棋子在棋盤上的一種擺法。棋子移動(dòng)后，狀態(tài)就會(huì)發(fā)生改變。解八數(shù)碼問題實(shí)際上就是找出從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)所經(jīng)過的一系列中間過渡狀態(tài)。2.九宮重移有無答案檢查（逆序數(shù)）我們把每個(gè)9宮格橫向展開，如第一個(gè)123456789，我們把左邊數(shù)大于右邊數(shù)的組數(shù)稱為這個(gè)九宮格的逆序數(shù)，顯然123456789的逆序數(shù)為0；考慮橫向平移，那么逆序數(shù)的增量為2或0或-2；縱向平移，逆序數(shù)的增量為4或0或-4；但147258369的逆序數(shù)為奇數(shù)。所以147258369是無解的情況。由此也可以類推當(dāng)將9宮格展開后，如果數(shù)據(jù)序列的逆序數(shù)為奇數(shù)，則此數(shù)據(jù)序列對(duì)應(yīng)的九宮格是無解的。3.BFS算法隊(duì)列： Queue open = new Queue();存放待擴(kuò)展的節(jié)點(diǎn)List： List closed = new List();存放已被擴(kuò)展過的節(jié)點(diǎn) ArrayList map = new ArrayList();/存放答案HashTale： Hashtable table = new Hashtable();構(gòu)造哈希表以方便查找3.1BFS算法介紹廣度優(yōu)先搜索算法BFS基本思想：從圖中某頂點(diǎn)v出發(fā)，逐層對(duì)節(jié)點(diǎn)進(jìn)行拓展，并考察是否為目標(biāo)節(jié)點(diǎn)，在第n層節(jié)點(diǎn)沒有全部擴(kuò)展并考察前，不對(duì)第n+1層節(jié)點(diǎn)進(jìn)行擴(kuò)展。對(duì)九宮重排問題，即構(gòu)造廣度優(yōu)先搜索樹，從初始狀態(tài)，利用廣度優(yōu)先搜索算法逐步找到目標(biāo)狀態(tài)的節(jié)點(diǎn)。3.2狀態(tài)空間表示狀態(tài)空間用一維數(shù)組表示，每個(gè)節(jié)點(diǎn)存放在Bfstr結(jié)構(gòu)體中的字符now中，從第一行開始從左往右給九宮格標(biāo)號(hào)08，字符串now元素下標(biāo)代表格子位置，而now數(shù)組中對(duì)應(yīng)數(shù)組的值代表九宮格中存放的數(shù)碼，用數(shù)值9代表空格。3.3搜索樹2 8 31 6 47 512 8 31 6 47 52 8 31 47 6 52 8 31 6 47 52342 8 36 41 7 52 31 8 47 6 52 8 31 6 7 5 42 8 31 47 6 52 8 31 47 6 5567893.4算法步驟 搜索：（1）把初始節(jié)點(diǎn)S0放入OPEN表。（2）如果OPEN表為空，則問題無解，退出。（3）把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。（5）若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。（6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。擴(kuò)展fun()：（1）取open中第一個(gè)節(jié)點(diǎn)a加入到closed中（2）找到a9中值為9（空格）的位置i；（3）當(dāng)open中元素個(gè)數(shù)不為0時(shí)，循環(huán)執(zhí)行（3）到（） 3.1從open中取出一個(gè)元素（狀態(tài)），并加入到closed中，對(duì)這個(gè)狀態(tài)擴(kuò)展； 3.2若空格在第2、3列,向左移動(dòng)得到新狀態(tài)； 新狀態(tài)不是目標(biāo)狀態(tài)，就加入open中； 新狀態(tài)是目標(biāo)狀態(tài)，就加入closed中，編號(hào)加1，結(jié)束算法； 3.3若空格在第2、3行,向上移動(dòng)得到新狀態(tài) 新狀態(tài)不是目標(biāo)狀態(tài)，就加入open中， 新狀態(tài)是目標(biāo)狀態(tài)，就加入closed中，編號(hào)加1，結(jié)束算法； 3.4若空格在第1、2列,向右移動(dòng)得到新狀態(tài) 新狀態(tài)不是目標(biāo)狀態(tài)，就加入open中， 新狀態(tài)是目標(biāo)狀態(tài)，就加入closed中，編號(hào)加1，結(jié)束算法； 3.5若空格在第1行,向下移動(dòng)得到新狀態(tài) 新狀態(tài)不是目標(biāo)狀態(tài)，就加入open中， 新狀態(tài)是目標(biāo)狀態(tài)，就加入closed中，編號(hào)加1，結(jié)束算法；3.5算法流程圖輸入初始狀態(tài)SS和目標(biāo)狀態(tài)NN開始o(jì)pen空?YNn=0,初始節(jié)點(diǎn)送入open隊(duì)列搜索失敗，算法結(jié)束，從open中取出節(jié)點(diǎn)到closed中并編號(hào)加1擴(kuò)展編號(hào)為n的節(jié)點(diǎn)，加入open中closed中是否有目標(biāo)節(jié)點(diǎn)Y算法結(jié)束是否還有后續(xù)節(jié)點(diǎn)NNY4.啟發(fā)式A*算法 隊(duì)列： Queue open = new Queue();存放待擴(kuò)展的節(jié)點(diǎn)List： List closed = new List();存放已被擴(kuò)展過的節(jié)點(diǎn) ArrayList map = new ArrayList();/存放答案HashTale： Hashtable table = new Hashtable();構(gòu)造哈希表以方便查找sort排序4.1算法介紹算法A不能保證當(dāng)圖中存在從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑時(shí)，一定能找到它，而A*中評(píng)估函數(shù)f*(n)=g*(n)+f*(n)保證路徑存在時(shí)，一定能找到。算法A中，g(n)和h(n)是g*(n)和f*(n)的近似估價(jià)。如果對(duì)于所有節(jié)點(diǎn)h(n)g*(n),則它就稱為A*算法：4.2.狀態(tài)空間表示狀態(tài)空間用一維數(shù)組表示，每個(gè)節(jié)點(diǎn)存放在Bfstr結(jié)構(gòu)體中的字符now中，從第一行開始從左往右給九宮格標(biāo)號(hào)08，字符串now元素下標(biāo)代表格子位置，而now數(shù)組中對(duì)應(yīng)數(shù)組的值代表九宮格中存放的數(shù)碼，用數(shù)值9代表空格。4.3.搜索樹2 8 31 6 47 512 8 31 6 47 52 8 31 47 6 52 8 31 6 47 52342 8 36 41 7 52 31 8 47 6 52 8 31 6 7 5 42 8 31 47 6 52 8 31 47 6 557892因?yàn)?節(jié)點(diǎn)離目標(biāo)節(jié)點(diǎn)更近，調(diào)換到3前面4.4.算法步驟算法描述：3.1把初始節(jié)點(diǎn)S0放入OPEN表，并建立目前只包含S0的圖，記為G；3.2檢查OPEN表是否為空，若為空則問題無解，退出；3.3把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSE表，并計(jì)該節(jié)點(diǎn)為n；3.4考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出；3.5擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記做集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中；3.6針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理：3.6.1對(duì)于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它們放入OPEN表；（不在OPEN表）3.6.2對(duì)于那些先前已經(jīng)在G中出現(xiàn)過的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；（在OPEN表中,對(duì)g(x)進(jìn)行更新）3.6.3對(duì)于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針；（在CLOSE表中, 對(duì)節(jié)點(diǎn)n子節(jié)點(diǎn)的子節(jié)點(diǎn)更新g(x) ）3.7對(duì)OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)進(jìn)行排序；3.8轉(zhuǎn)第2步。4.5.算法流程圖開始輸入初始狀態(tài)SS和目標(biāo)狀態(tài)NNS0加入open表，構(gòu)造Gopen空？YN失敗結(jié)束open取首節(jié)點(diǎn)放入closed,n號(hào)擴(kuò)展n節(jié)點(diǎn)，加入G將不是n為父的子節(jié)點(diǎn)記做集合MM中未在G出現(xiàn)過的設(shè)置父節(jié)點(diǎn)n,放入openM中已G出現(xiàn)過的open表中更新M中已G出現(xiàn)過且擴(kuò)展的，closed表中更新g(x)OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)進(jìn)行排序5.啟發(fā)式A算法隊(duì)列： Queue open = new Queue();存放待擴(kuò)展的節(jié)點(diǎn)List： List closed = new List();存放已被擴(kuò)展過的節(jié)點(diǎn) ArrayList map = new ArrayList();/存放答案HashTale： Hashtable table = new Hashtable();構(gòu)造哈希表以方便查找sort排序5.1算法介紹 啟發(fā)式搜索算法A，一般簡稱為A算法，是一種典型的啟發(fā)式搜索算法。其基本思想是：定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展。評(píng)價(jià)函數(shù)的形式如下：f（n）g（n）h（n） ; 其中n是被評(píng)價(jià)的節(jié)點(diǎn)。說明：g*(n)：表示從初始節(jié)點(diǎn)s到節(jié)點(diǎn)n的最短路徑的耗散值；h*(n)：表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)g的最短路徑的耗散值；f*(n)=g*(n)+h*(n)：表示從初始節(jié)點(diǎn)s經(jīng)過節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)g的最短路徑的耗散值。而f（n）、g（n）和h（n）則分別表示是對(duì)f*（n）、g*（n）和h*（n）三個(gè)函數(shù)值的的估計(jì)值。是一種預(yù)測。A算法就是利用這種預(yù)測，來達(dá)到有效搜索的目的的。它每次按照f(n)值的大小對(duì)OPEN表中的元素進(jìn)行排序，f值小的節(jié)點(diǎn)放在前面，而f值大的節(jié)點(diǎn)則被放在OPEN表的后面，這樣每次擴(kuò)展節(jié)點(diǎn)時(shí)，都是選擇當(dāng)前f值最小的節(jié)點(diǎn)來優(yōu)先擴(kuò)展。5.2.狀態(tài)空間表示狀態(tài)空間用一維數(shù)組表示，每個(gè)節(jié)點(diǎn)存放在Bfstr結(jié)構(gòu)體中的字符now中，從第一行開始從左往右給九宮格標(biāo)號(hào)08，字符串now元素下標(biāo)代表格子位置，而now數(shù)組中對(duì)應(yīng)數(shù)組的值代表九宮格中存放的數(shù)碼，用數(shù)值9代表空格。5.3.搜索樹 5.4.算法步驟5.1 建立一個(gè)只含初始節(jié)點(diǎn)So的搜索圖G，把So放入Open表，并計(jì)算f（So）的值；5.2 如果Open表是空的，則失敗，否則，繼續(xù)下一步；5.3從Open表中取出f值為最小的結(jié)點(diǎn)，置于Close表，給這個(gè)結(jié)點(diǎn)編號(hào)為n；5.4如果n是目標(biāo)結(jié)點(diǎn)，則得解，算法成功退出。此解可從目標(biāo)結(jié)點(diǎn)開始到初始節(jié)點(diǎn)的返回指針中得到。否則，繼續(xù)下一步；5.5擴(kuò)展結(jié)點(diǎn)n。生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記做集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中；5.6對(duì)于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它們放入OPEN表 ；5.7對(duì)于那些先前已經(jīng)在G中出現(xiàn)過的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；（在OPEN表中,對(duì)g(x)進(jìn)行更新）5.8對(duì)于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針；（在CLOSE表中, 對(duì)節(jié)點(diǎn)n子節(jié)點(diǎn)的子節(jié)點(diǎn)更新g(x) ）5.9按f值從大至小的順序，對(duì)Open表中的結(jié)點(diǎn)重新排序；5.10 返回步驟2。5.5算法流程圖 開始輸入初始狀態(tài)SS和目標(biāo)狀態(tài)NNS0加入open表，構(gòu)造Gopen空？YN失敗結(jié)束open取首節(jié)點(diǎn)放入closed,n號(hào)擴(kuò)展n節(jié)點(diǎn)，加入G將不是n為父的子節(jié)點(diǎn)記做集合MM中未在G出現(xiàn)過的設(shè)置父節(jié)點(diǎn)n,放入openM中已G出現(xiàn)過的open表中更新M中已G出現(xiàn)過且擴(kuò)展的，closed表中更新g(x)OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)進(jìn)行排序6.隨機(jī)數(shù)生成算法6.1.算法介紹在數(shù)據(jù)結(jié)構(gòu)、算法分析與設(shè)計(jì)、科學(xué)模擬等方面都需要用到隨機(jī)數(shù)。由于在數(shù)學(xué)上，整數(shù)是離散型的，實(shí)數(shù)是連續(xù)型的，而在某一具體的工程技術(shù)應(yīng)用中，可能還有數(shù)據(jù)值的范圍性和是否可重復(fù)性的要求。因此，我們就整數(shù)隨機(jī)數(shù)和實(shí)數(shù)隨機(jī)數(shù)，以及它們的數(shù)據(jù)值的范圍性和是否可重復(fù)性，分別對(duì)其算法加以分析和設(shè)計(jì)。1、Microsoft VC+產(chǎn)生隨機(jī)數(shù)的原理：Srand ( )和Rand( )函數(shù)。它本質(zhì)上是利用線性同余法，y=ax+b(mod m)。其中a，b，m都是常數(shù)。因此rand的產(chǎn)生決定于x，x被稱為Seed。Seed需要程序中設(shè)定，一般情況下取系統(tǒng)時(shí)間作為種子。它產(chǎn)生的隨機(jī)數(shù)之間的相關(guān)性很小，取值范圍是032767（int），即雙字節(jié)（16位數(shù)），若用unsigned int 雙字節(jié)是65535，四字節(jié)是4294967295，一般可以滿足要求。根據(jù)整數(shù)隨機(jī)數(shù)范圍性和是否可重復(fù)性，可分為：(1)某范圍內(nèi)可重復(fù)。(2)某范圍內(nèi)不可重復(fù)。(3)枚舉可重復(fù)。(4)枚舉不可重復(fù)。所謂范圍，是指在兩個(gè)數(shù)n1和n2之間。例如，在100和200之間這個(gè)范圍，那么，只要產(chǎn)生的整數(shù)隨機(jī)數(shù)n滿足100n200，都符合要求。所謂枚舉，是指有限的、已知的、若干個(gè)不連續(xù)的整數(shù)。例如，34、20、123、5、800這5個(gè)整數(shù)就是一種枚舉數(shù)，也就是單獨(dú)可以一個(gè)個(gè)確定下來。某范圍內(nèi)可重復(fù)在Visual Basic 語言中，有一個(gè)隨機(jī)數(shù)函數(shù)Rnd。語法：Rnd(number)。參數(shù)number 可選，number 的值決定了 Rnd 生成隨機(jī)數(shù)的方式。Rnd 函數(shù)返回小于 1 但大于或等于 0 的值。Number類型Rnd 結(jié)果小于零每次都相同的數(shù)字，并將 number 用作種子。大于零序列中的下一個(gè)隨機(jī)數(shù)。等于零最近生成的數(shù)字。未提供序列中的下一個(gè)隨機(jī)數(shù)。 在調(diào)用 Rnd 之前，先使用無參數(shù)的 Randomize 語句初始化隨機(jī)數(shù)生成器，該生成器具有一個(gè)基于系統(tǒng)計(jì)時(shí)器的種子。若要生成某給定范圍內(nèi)的隨機(jī)整數(shù)，可使用以下公式：Int(upperbound - lowerbound + 1) * Rnd + lowerbound)這里，upperbound 是此范圍的上限，而 lowerbound 是范圍的下限6.2.程序流程圖：開始給定范圍上限： lowerbound下限：upperbound生成隨機(jī)數(shù)：Random Int(upperboundlowerbound+1)%Rnd+lowerbound結(jié)束7.DFS黃鑫負(fù)責(zé)部分（請(qǐng)注意與上面的格式搭配一下）8.效果圖滑塊問題求解系統(tǒng)（1）DFS時(shí)當(dāng)顯示只需2、3步時(shí)，搜索空間爆棧，內(nèi)存溢出，失敗。暫時(shí)解決辦法：重新生成結(jié)束狀態(tài)或者初始狀態(tài)（2）BFS、A、A*時(shí)顯示32步時(shí)，搜索空間太多，內(nèi)存溢出，失敗。暫時(shí)解決辦法：重新生成結(jié)束狀態(tài)或者初始狀態(tài)（3）不能同時(shí)生成結(jié)束狀態(tài)圖和初始狀態(tài)圖。暫時(shí)解決辦法：分步生成結(jié)束狀態(tài)或者初始狀態(tài)（4）未完成工作：1、時(shí)間顯示2、自動(dòng)演示8.1初始界面：8.3.BFS效果圖：8.3.啟發(fā)式*效果圖：8.4啟發(fā)式A效果圖：8.5.DFS效果圖：9.代碼共包括3個(gè)工程文件：Common RAND YYSEN工程文件名類名功能代碼行數(shù)Common Ase.cs實(shí)現(xiàn)A算法約350行Common Astr.csA算法的解空間27Common Bfs.cs實(shí)現(xiàn)廣度優(yōu)先算法220Common Bfstr.cs廣度優(yōu)先算法的解空間15Common Bse.cs實(shí)現(xiàn)A*算法35Common common.cs公用方法72Common Dfs.cs實(shí)現(xiàn)深度優(yōu)先算法250Common Dfstr.cs深度優(yōu)先算法解空間15RANDRandNum.cs生成隨機(jī)地圖55YYYSENForm1.csWindows功能實(shí)現(xiàn)290YYYSENForm1.Designer.csWindows界面設(shè)計(jì)660YYYSENProgram.csWindows界面入口211、class Ase實(shí)現(xiàn)啟發(fā)式A算法using System;using System.Collections.Generic;using System.Text;using System.Collections;/約350行namespace Common public class Ase private int SS=new int9; private int NN=new int9; private string S; private string N; public bool BOOL;/是否有解； List open=new List() ;/未搜索； List closed = new List();/已搜索； Hashtable table = new Hashtable(); public ArrayList map=new ArrayList(); public Ase(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.Length); public void search() /呵呵，調(diào)用其他的搜索，不解釋 Bfs ansbfs = new Bfs(this.SS, this.NN); ansbfs.search(); map = ansbfs.map; return; if (S != N) Astr node = new Astr(); 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(); /構(gòu)造最佳答案； int i = 0; Astr p=closed closed .Count -1; closed.Remove(p); map.Add(p.now); while (p.now != S) for (i = 0; i closed.Count; i+) if (closedi.now = p.qian) map.Add(closedi.now); p = closedi; closed.Remove(p); break; /交換 int j = 0; for (i = 0, j = map.Count - 1; i j; i+, j-) string sss = mapi as string; mapi = mapj; mapj = sss; /交換值 private void swap(int a, int x, int y) int t; t = ax; ax = ay; ay = t; private int fwn(string s1, string s2) int i; int sum=0; for (i = 0; i 10000) return; /找最小元素 /list.Sort(x, y) = y.Age - x.Age);排序 int i = 0; /去open中的fn最小值 node_1 = openi; for (i = 0; i = openi.fn) node_1 = openi; open.Remove (node_1); closed.Add(node_1); if(node_1.now =N) return ; a = common.changeint(node_1.now); for (i = 0; i a.Length; i+) if (ai = 9) break; int index = 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_1.now; node_2.gn=node_1.gn +1; node_2.wn=fwn(s,N); node_2.fn =node_2.gn+node_2.wn ; int j=0; for (j = 0; j node_2.gn) open.RemoveAt(j); open.Add(node_2); tablenode_2.now = node_2.gn; break; int k; for (k = 0; k node_2.gn) closed.RemoveAt(k); closed.Add(node_2); tablenode_2.now = node_2.gn; break; if (j = open.Count) if(k = closed .Count) open.Add(node_2); table.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_1.now; node_2.gn=node_1.gn +1; node_2.wn=fwn(s,N); node_2.fn =node_2.gn+node_2.wn ; int j=0; for (j = 0; j node_2.gn) open.RemoveAt(j); open.Add(node_2); tablenode_2.now = node_2.gn; break; int k; for (k = 0; k node_2.gn) closed.RemoveAt(k); closed.Add(node_2); tablenode_2.now = node_2.gn; break; if (j = open.Count&k=closed .Count ) open.Add(node_2); table.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_1.now; node_2.gn=node_1.gn +1; node_2.wn=fwn(s,N); node_2.fn =node_2.gn+node_2.wn ; int j=0; for (j = 0; j node_2.gn) open.RemoveAt(j); open.Add(node_2); tablenode_2.now = node_2.gn; break; int k; for (k = 0; k node_2.gn) closed.RemoveAt(k); closed.Add(node_2); tablenode_2.now = node_2.gn; break; if (j = open.Count&k=closed .Count ) open.Add(node_2); t