1、*大學人工智能基礎課程實驗報告（2011-2012學年第一學期）啟發式搜索王浩算法班 級:學 號:姓 名:指導教師：成 績:*2012年1月10日實驗一啟發式搜索算法1.實驗內容：使用啟發式搜索算法求解 8數碼問題。編制程序實現求解 8數碼問題A算法，采用估價函數w n f n d n,P n其中：d n是搜索樹中結點n的深度；w n為結點n的數據庫中錯放的棋子個數；p n為結點n的數據庫中每個棋子與其目標位置之間的距離總和。分析上述中兩種估價函數求解8數碼問題的效率差另1J,給出一個是p n的上界的h n的定義，并測試使用該估價函數是否使算法失去可采納性。2 .實驗目的熟練掌握啟發式搜索 A

2、算法及其可采納性。3 .實驗原理使用啟發式信息知道搜索過程，可以在較大的程度上提高搜索算法的時間效率和空間效 率；啟發式搜索的效率在于啟發式函數的優劣，在啟發式函數構造不好的情況下，甚至在存在解的 情形下也可能導致解丟失的現象或者找不到最優解，所以構造一個優秀的啟發式函數是前提條件。4 .實驗內容1 .問題描述在一個3*3的九宮格 里有1至8八個數以及一個空格隨機擺放在格子中，如下圖：2 8316目標狀態初始狀態現需將圖一轉化為圖二的目標狀態，調整的規則為：每次只能將空格與其相鄰的一個數字進行 交換。實質是要求給出一個合法的移動步驟，實現從初始狀態到目標狀態的轉變。2.算法分析(1)解存在性的

3、討論對于任意的一個初始狀態，是否有解可通過線性代數的有關理論證明。按數組存儲后，算出 初始狀態的逆序數和目標狀態的逆序數，若兩者的奇偶性一致，則表明有解。(2)估價函數的確定通過對八數碼的特性的研究，找出一個相對好的函數，f(n)=d(n)+h(n) 其中 h(n)=2*compare(n)+3*S(n);d(n)為已搜索的深度；(compare (n)為當前節點與目標結點相同位置不相同的個數，S(n)為當前節點的無序度。)(3)節點的處理取得一個結點后，判斷是否有解，然后對其進行擴展，用估價函數從中取得一個最優節點， 依次循環將路徑得到，直到取的最后的目標狀態。(4)算法設計a. 輸入初始結

4、點，判斷解的存在性，并與目標節點對比。b. 若不是目標節點則進行擴展，生成其全部后繼節點。c. 對于每個后繼節點均求其f(n),并比較。d.將最小f(n)存入正確路徑，并與目標節點進行對比。e.若不是目標節點則循環執行 b,若是目標節點則輸出5實驗結果輸入輸出：源代碼如下：#include<stdio.h>int final9=123,8,0,4,7,6,5;目標狀態節點int a10009,c9,e9,f9;路徑節點和擴展節點int deep=1,fn;/ 深度和估計值int b9;char moveaction;/ 移動方向int fnjisuan(int b9)/估價函數in

5、t compare=0,s=0,fn1,d9;d0=b0;d1=b1;d2=b2;d3=b5;d4=b8;d5=b7;d6=b6;d7=b3;d 8=b4;for(int i=0;i<9;i+)if(bi!=finali&&i!=4)compare+;for(i=0;i<7;i+)if(di+1-di)!=1)s+;fn1=2*compare+3*s+deep;/ 估價函數計算結果return fn1;void show(int c9)/ 輸出節點for(int i=0;i<9;i+)adeepi=ci;for(i=0;i<9;i+)if(i)%3=0)

6、printf("n");printf("%dt",ci);deep+;printf("n");int jingguo(int e9)/ 測試當前節點是否已經經過避免回溯for(int i=0;i<deep;i+)int k=0;for(int j=0;j<9;j+)if(ej=aij)k+;if(k=9)return 0;return 1;int move_up(int c9,int Zerosign)/上移操作for(int i=0;i<9;i+)ci=bi;cZerosign=cZerosign-3;cZeros

7、ign-3=0;int fn1=fnjisuan(c);return fn1;int move_down(int c9,int Zerosign)/下移操作for(int i=0;i<9;i+)ci=bi;cZerosign=cZerosign+3;cZerosign+3=0;int fn1=fnjisuan(c);return fn1;int move_left(int c9,int Zerosign)/for(int i=0;i<9;i+)ci=bi;cZerosign=cZerosign-1;cZerosign-1=0;int fn1=fnjisuan(c);return f

8、n1;int move_right(int c9,int Zerosign)/for(int i=0;i<9;i+)ci=bi;cZerosign=cZerosign+1;cZerosign+1=0;int fn1=fnjisuan(c);return fn1;int zuixiao(int fn1,int fn2,int fn3,int fn4)/int f1,f2,f3;f1=(fn1<=fn2)?fn1:fn2;f2=(fn3<=fn4)?fn3:fn4;f3=(f1<=f2)?f1:f2;return f3;int cixiao(int fn1,int fn2,

9、int fn3,int fn4)/int f1,f2,f3,f4;f1=(fn1<=fn2)?fn1:fn2;f3=(fn1>fn2)?fn1:fn2;f2=(fn3<=fn4)?fn3:fn4;f4=(fn1>fn2)?fn1:fn2;if(f1<=f2)if(f3<=f2)return f3;else return f2;else if(f4<=f1)return f4;else return f1;左移操作右移操作求次小值求最小值處理估價函數最void budeng(int f1,int f2,int fn1,int fn2,int fn3,in

10、t fn4,int Zerosign)/小值唯一的時候if(f1=fn1)if(moveaction!='d'&&jingguo(c) move_up(c,Zerosign);moveaction='u' elseif(f2=fn2)move_right(c,Zerosign);moveaction='r'if(f2=fn3)move_left(c,Zerosign);moveaction='l'if(f2=fn4)move_down(c,Zerosign);moveaction='d'if(f1=

11、fn2)if(moveaction!='l'&&jingguo(c)move_right(c,Zerosign);moveaction='r' elseif(f2=fn3)move_left(c,Zerosign);moveaction='l'if(f2=fn4)move_down(c,Zerosign);moveaction='d'if(f2=fn1)move_up(c,Zerosign);moveaction='u'if(f1=fn3)if(moveaction!='r'&

12、;&jingguo(c)move_left(c,Zerosign);moveaction='l' elseif(f2=fn1)move_up(c,Zerosign);moveaction='u'if(f2=fn2)move_right(c,Zerosign);moveaction='r'if(f2=fn4)move_down(c,Zerosign);moveaction='d' if(f1=fn4)if(moveaction!='u'&&jingguo(c)move_down(c,Zeros

13、ign);moveaction='d' elseif(f2=fn2)move_right(c,Zerosign);moveaction='r'if(f2=fn3)move_left(c,Zerosign);moveaction='l'if(f2=fn1)move_up(c,Zerosign);moveaction='u' int ceshi(int k9)/ 測試估價函數int fn1=100,fn2=100,fn3=100,fn4=100,f1,Zerosign;for(int i=0;i<9;i+)if(0=ki)Zer

14、osign=i;break;if(Zerosign!=0&&Zerosign!=1&&Zerosign!=2&&moveaction!='d')fn1=move_up(c,Zerosign);if(Zerosign!=2&&Zerosign!=5&&Zerosign!=8&&moveaction!='l') fn2=move_right(c,Zerosign);if(Zerosign!=0&&Zerosign!=3&&Zerosign!

15、=6&&moveaction!='r') fn3=move_left(c,Zerosign);if(Zerosign!=6&&Zerosign!=7&&Zerosign!=8&&moveaction!='u') fn4=move_down(c,Zerosign);f1=zuixiao(fn1,fn2,fn3,fn4);return f1;void move(int c9)/ 確定移動方向int fn1=100,fn2=100,fn3=100,fn4=100,f1,f2,Zerosign;for(in

16、t i=0;i<9;i+)if(0=ci)Zerosign=i;break;if(Zerosign!=0&&Zerosign!=1&&Zerosign!=2&&moveaction!='d')fn1=move_up(c,Zerosign);if(Zerosign!=2&&Zerosign!=5&&Zerosign!=8&&moveaction!='l') fn2=move_right(c,Zerosign);if(Zerosign!=0&&Zer

17、osign!=3&&Zerosign!=6&&moveaction!='r') fn3=move_left(c,Zerosign);if(Zerosign!=6&&Zerosign!=7&&Zerosign!=8&&moveaction!='u') fn4=move_down(c,Zerosign);f1=zuixiao(fn1,fn2,fn3,fn4);f2=cixiao(fn1,fn2,fn3,fn4);if(f1=f2)if(fn1=fn2&&fn1=f1)mo

18、ve_up(c,Zerosign);for(i=0;i<9;i+)ei=ci;move_right(c,Zerosign);for(i=0;i<9;i+)fi=ci;if(ceshi(e)<ceshi(f)&&jingguo(e)move_up(c,Zerosign);moveaction='u' else move_right(c,Zerosign);moveaction='r' if(fn1=fn3&&fn1=f1) move_up(c,Zerosign);for(i=0;i<9;i+)ei=ci;mo

19、ve_left(c,Zerosign);for(i=0;i<9;i+)fi=ci;if(ceshi(e)<ceshi(f)&&jingguo(e)move_up(c,Zerosign);moveaction='u' else move_left(c,Zerosign);moveaction='l'if(fn1=fn4&&fn1=f1)move_up(c,Zerosign);for(i=0;i<9;i+)ei=ci;move_down(c,Zerosign);for(i=0;i<9;i+)fi=ci;if(c

20、eshi(e)<ceshi(f)&&jingguo(e)move_up(c,Zerosign);moveaction='u' else move_down(c,Zerosign);moveaction='d'if(fn2=fn3&&fn2=f1)move_right(c,Zerosign);for(i=0;i<9;i+)ei=ci;move_left(c,Zerosign);for(i=0;i<9;i+)fi=ci;if(ceshi(e)<ceshi(f)&&jingguo(e)move_r

21、ight(c,Zerosign);moveaction='r' else move_left(c,Zerosign);moveaction='l'if(fn2=fn4&&fn2=f1)move_right(c,Zerosign);for(i=0;i<9;i+)ei=ci;move_down(c,Zerosign);for(i=0;i<9;i+)fi=ci;if(ceshi(e)<ceshi(f)&&jingguo(e)move_right(c,Zerosign);moveaction='r' el

22、se move_down(c,Zerosign);moveaction='d'if(fn3=fn4&&fn3=f1)move_left(c,Zerosign);for(i=0;i<9;i+)ei=ci;move_down(c,Zerosign);for(i=0;i<9;i+)fi=ci;if(ceshi(e)<ceshi(f)&&jingguo(e)move_left(c,Zerosign);moveaction='l'else move_down(c,Zerosign);moveaction='d

23、9;else budeng(f1,f2,fn1,fn2,fn3,fn4,Zerosign);int duibi(int c9) /與目標節點比較for(int i=0;i<9;i+)if(ci!=finali)break;if(i>=9)return 1;else return 0;int cunzaixing(int c9) /得出初始化節點是否存在路徑到目標節點int nixu=0,nixu1=0,i,j;for( j=0;j<9;j+)for(int i=j+1;i<9;i+)if(finalj>finali&&finalj!=0&&

24、amp;finali!=0)nixu+;for(j=0;j<9;j+)for( i=j+1;i<9;i+)if(cj>ci&&cj!=0&&ci!=0)nixu1+;if(nixu%2)-(nixu1%2)=0)return 1;else return 0;void main()/ 主函數int sd=1;printf(" 請輸入初始結點如( 2 8 3 1 6 4 7 0 5) 以空格隔開的九個0 到 9 之間的不重復數: n");for(int i=0;i<9;i+)scanf("%d",&am

25、p;bi);ci=bi;printf(" 您輸入的初始矩陣為：n");show(c);deep-;if(cunzaixing(c)=0)printf(" 此矩陣不存在路徑至目標矩陣！n");elsewhile(!duibi(c)&&deep<100)move(c);printf("第 步移動后的矩陣為：n",sd+);show(c);for(int i=0;i<9;i+)bi=ci;實驗二王浩算法的實現1 .實驗內容：實現命題邏輯框架內的王浩算法。將命題邏輯中的王浩算法推廣至下述命題語言的情形之下：i命題變

26、量符號：pl, p2, p3,ii邏輯連接符：，iii間隔符：(,)在上述中所定義的命題語言中實現王浩算法。2 .實驗目的熟練掌握命題邏輯中的王浩算法。3 .實驗要求實驗題目必須由個人獨立完成，允許自行參考相關文獻資料，但嚴禁同學間相互拷貝和抄襲程序以及文檔資料。實驗結束后一周內上交實驗報告和實驗文檔資料。提交的文檔資料包括設計文檔和程序源代碼。設計文檔和程序源代碼以書面文檔方式提供(用A4紙打印)；并提交電子文檔備查。四.數據結構給定公式，例如：(p1->(q1->n)->(p1->q1)->(p1->n)函數inite主要作用是負責將符號初始化成樹的結構

27、。函數clone復制一棵完全相同的符號樹。函數restruct 查找所有&, | , <->等符號，并將其拆分成新形式：！，->符號。函數searching王浩算法的主要函數。函數show和output:顯示符號串和推理過程。五.實驗結果公式正確_ :生茸上生職"!帝碣人量證朝翦公£,交量行號可由大小寫字母和知繃 (t>l Xfll >rl>> >«pl >ql) -XKd >rl»化成慈含式：般導造果為=<2)<3><4><5>(B>(9

28、>(10><li><I2>(I35C14><15>IE)<1U>(1?)(20)<21>pZlQqLpl.pJ.pl Jqlpjl plQl-Zrl->plrl pl/gl-Apl 薪 ripl <ql->rl> ->ipl-rle*1 .q1 >qi -ri1Pl .觀1 . rl-rl里 1a.l11, * ifl -irlpl>rl->rlmql Jpl b>f1位.q L pl-X ql - >rl>=>Fl由3)根網則工再<:G3

29、根跟規則孑 由艮哌現則工航G醯滯據規則3公四由仃硼理原柱由艱據現!蟲小 ) 喂下酶刑之I I I n Ipl.pl->gll=>rlpl - >qjl > pl - > Cql- >ri,rlnl ->ql R jkl-Xal-JrlijI Xiil >->!>, pl Jrlpl - ><«1 ->rl > >> < pl - W >-> Cpl->r 1 >->fJ > » (pl *>n1*>1"1 >=

30、><pI(q 1 I >>-><<pt-><|1巾根室反II 樂1?)柬據次原4 圉叱湘揖現妣白門"很據視!一 日相6根據規貝! I 三：根據視劑4TK.實驗總結通過本次實驗，使我更深入的理解了啟發式搜索的原理以及實現，對于其優越性有一定認識，加深了對語法分析以及邏輯公式理解，同時熟練掌握了對樹的操作。在編程實現過程中出現過不少問題，通過一次次調試得以解決，并一定程度上提高了我的編程能力,而且讓我對人工智能這一課程有了更直接的認知。王浩算法源代碼清單：#include<stdio.h> #include<stdl

31、ib.h> #include<string.h>#define MAXL 5 int i=0;int stepcount=1;enum typeand,or,detrusion,equal,level,variable;struct nodechar *s;type kind;int polar;node *next;node *child;int start;struct stepstep *child;step *brother;node *lhead;node*rhead;int count;char name30;int inite(char *s,node *hea

32、d)int len=strlen(s);int j=0,polar=1;node *now=NULL;node *last=NULL;if(s=NULL)return 0;last=head;while(i<len)if(si='|')if(!(si+1<=Z&&si+1>='A'|si+1<='z'&&si+1>='a')&&si+1!='1'&&si+1!='0'&&si+1!='

33、;('&&si+1!='!'|i=0)return 0;now=(node*)malloc(sizeof(node);now->kind=or;now->s=NULL;now->next=NULL;now->child=NULL;now->polar=polar;now->start=0;if(last->kind=level&&last->child=NULL)last->child=now;elselast->next=now;last=now;i+;else if(si=&

34、#39;&')if(!(si+1<=Z&&si+1>='A'|si+1<='z'&&si+1>='a')&&si+1!='1'&&si+1!='0' &&si+1!='('&&si+1!='!'|i=0)return 0;now=(node*)malloc(sizeof(node);now->kind=and;now->s=NULL;no

35、w->next=NULL;now->child=NULL;now->polar=polar;now->start=0;if(last->kind=level&&last->child=NULL)last->child=now;elselast->next=now;last=now;i+;else if(si='!')if(!(si+1<=Z&&si+1>='A'|si+1<='z'&&si+1>='a')&

36、;&si+1!='1'&&si+1!='0' &&si+1!='('&&si+1!='!')return 0;polar=1-polar;i+;else if(si='-')if(si+1!='>'|(si+2!='!'&&si+2!='('&&!(si+2<=Z&&si+2>='A'|si+2<='z' &a

37、mp;&si+2>='a')|i=0)return 0;now=(node*)malloc(sizeof(node);now->kind=detrusion;now->s=NULL;now->next=NULL;now->child=NULL;now->polar=polar;now->start=0;if(last->kind=level&&last->child=NULL) last->child=now;elselast->next=now;last=now;i=i+2;else i

38、f(si='<')if(si+1!='-'|si+2!='>')|(si+3!='!'&&si+3!='('&&!(si+3<=Z&&si+3>='A'|si+3<='z'&&si+3>='a')|i=0)&&si+3!='1'&&si+3!='0')return 0;now=(node*)malloc(s

39、izeof(node);now->kind=equal;now->s=NULL;now->next=NULL;now->child=NULL;now->polar=polar;now->start=0;if(last->kind=level&&last->child=NULL) last->child=now;elselast->next=now;last=now;i=i+3;else if(si<=Z&&si>='A'|si<='z'&&

40、;si>='a') now=(node*)malloc(sizeof(node);now->kind=variable;now->next=NULL;now->child=NULL;now->polar=polar;now->start=0;now->s=(char*)malloc(MAX_L*sizeof(char);if(last->kind=level&&last->child=NULL) last->child=now;elselast->next=now;last=now;j=0;whi

41、le(si<=Z&&si>='A'|si<='z'&&si>='a')|(si<='9'&&si>='0') (now->s)j=si;i+;j+;if(si!=T&&si!=&&&si!='-'&&si!='<'&&si!='0'&&si!=')')return 0;(

42、now->s)j='0'polar=1;if(si+1!='<'&&si+1!='-'&&si+1!='&'&&si+1!='|'&&si+1!=')'&&si+1!='0') return 0;now=(node*)malloc(sizeof(node);now->kind=equal;now->s=(char*)malloc(2*sizeof(char);(now-&g

43、t;s)0=si;(now->s)1='0'now->next=NULL;now->child=NULL;now->polar=polar;now->start=0;if(last->kind=level&&last->child=NULL)last->child=now;elselast->next=now;last=now;i+;else if(si='(')if(!(si+1<='Z'&&si+1>='A'|si+1<=&

44、#39;z'&&si+1>='a')&&si+1!='1'&&si+1!='0' &&si+1!='!'&&si+1!='(')return 0;now=(node*)malloc(sizeof(node);now->kind=level;now->s=NULL;now->next=NULL;now->child=NULL;now->polar=polar;now->start=0;if

45、(last->kind=level&&last->child=NULL)last->child=now;elselast->next=now;last=now;i+;polar=1;if(!inite(s,last)return 0;else if(si=')')if(si+1!='P'&&si+1!='1'&&si+1!='0'&&si+1!='-'&&si+1!='<'&&

46、;si+1!='&'&&s i+1!='|'&&si+1!='0'&&si+1!=')')return 0;i+；return 1;else return 0;return 1;node* clone(node *parent)node *son=NULL;if(parent=NULL)return NULL;son=(node*)malloc(sizeof(node);son->kind=parent->kind;son->polar=parent->

47、;polar;son->s=parent->s;son->start=parent->start;if(parent->next!=NULL) son->next=clone(parent->next);else son->next=NULL;if(parent->child!=NULL) son->child=clone(parent->child);else son->child=NULL;return son;void remove(node *head)node *now=NULL;now=head;if(now=

48、NULL)return;if(now->kind=level&&now->child->kind=variable&&now->child->next=NULL)now->polar=(now->child->polar=now->polar);now->child->polar=1;while(now->kind=level&&now->child->kind=level&&now->child->next=NULL) now->

49、;polar=(now->polar=now->child->polar);now->child=now->child->child;if(now->next!=NULL)remove(now->next);if(now->child!=NULL)remove(now->child);void restruct(node* head)node *now=NULL;node *last=NULL;node *newone=NULL,*newtwo=NULL,*newthree=NULL,*newfour=NULL,*newnow=NUL

50、L;int order=1;while(order<=4)last=head;now=last->child;while(now!=NULL)if(now->kind=variable|now->kind=level)&&order=1) if(now->next!=NULL&&now->next->kind=and) newone=(node*)malloc(sizeof(node);newone->child=NULL;newone->kind=level;newone->next=NULL;new

51、one->polar=0;newone->s=NULL;newone->start=0;if(last->kind=level)last->child=newone;elselast->next=newone;newone->next=now->next->next->next;newone->child=now;now->next->next->polar=1-now->next->next->polar;now->next->kind=detrusion;now->nex

52、t->next->next=NULL;now=newone;elselast=now;now=now->next;else if(now->kind=variable|now->kind=level)&&order=2)if(now->next!=NULL&&now->next->kind=or)newone=(node*)malloc(sizeof(node);newone->child=NULL;newone->kind=level;newone->next=NULL;newone->p

53、olar=1;newone->s=NULL;newone->start=0;if(last->kind=level)last->child=newone;elselast->next=newone;newone->next=now->next->next->next;newone->child=now;now->polar=1-now->polar;now->next->kind=detrusion;now->next->next->next=NULL;now=newone;elselast=

54、now;now=now->next;else if(now->kind=variable|now->kind=level)&&order=3)if(now->next!=NULL&&now->next->kind=equal) newone=(node*)malloc(sizeof(node);newone->child=NULL;newone->kind=level;newone->next=NULL;newone->polar=0;newone->s=NULL;newone->start

55、=0;newtwo=(node*)malloc(sizeof(node);newtwo->child=NULL;newtwo->kind=level;newtwo->next=NULL;newtwo->polar=1;newtwo->s=NULL;newtwo->start=0;newthree=(node*)malloc(sizeof(node);newthree->child=NULL;newthree->kind=detrusion;newthree->next=NULL;newthree->polar=1;newthree-&

56、gt;s=NULL;newthree->start=0;newfour=(node*)malloc(sizeof(node);newfour->child=NULL;newfour->kind=level;newfour->next=NULL;newfour->polar=0;newfour->s=NULL;newfour->start=0;if(last->kind=level)last->child=newone;elselast->next=newone;newone->next=now->next->next

57、->next;newone->child=newtwo;now->next->kind=detrusion;newtwo->child=now;now->next->next->next=NULL;newtwo->next=newthree;newthree->next=newfour;newfour->next=NULL;newnow=clone(now);newnow->next->kind=detrusion;newfour->child=newnow->next->next;newnow-&

58、gt;next->next->next=newnow->next; newnow->next->next=newnow;newnow->next=NULL;now=newone;elselast=now;now=now->next;else if(now->kind=level&&order=4)restruct(now);last=now;now=now->next;elselast=now;now=now->next;order+;void show(node *head)node *now=NULL;now=he

59、ad;while(now!=NULL)if(now->kind=level)if(now->polar=0)printf("!");if(now->start!=1|(now->polar=0&&now->child->next!=NULL)printf("(");show(now->child);if(now->start!=1|(now->polar=0&&now->child->next!=NULL)printf(")"); now

60、=now->next;if(now!=NULL&&now->start=1)putchar(',');else if(now->kind=and)printf("&");now=now->next;else if(now->kind=or)printf("|");now=now->next;else if(now->kind=detrusion)printf("->");now=now->next;else if(now->kind=e

61、qual)printf("<->");now=now->next;else if(now->kind=variable)if(now->polar=0)printf("!");printf("%s",now->s);now=now->next;return;int searching(step *one)node *now=NULL;node *last=NULL;node *newlev=NULL;node *nnow=NULL;node *nlast=NULL;step *nextone=

62、NULL;step *nexttwo=NULL;int key=0;int mark=0;int re1=1;int re2=1;nextone=(step*)malloc(sizeof(step);nextone->brother=NULL;nextone->child=NULL;nextone->lhead=NULL;nextone->rhead=clone(one->rhead);nextone->lhead=clone(one->lhead);strcpy(nextone->name,"");one->child

63、=nextone;now=nextone->rhead;last=now;while(now!=NULL)if(now->polar=0)if(now=nextone->rhead)nextone->rhead=now->next;else last->next=now->next;now->next=NULL;remove(now);now->next=nextone->lhead;nextone->lhead=now;now->polar=1-now->polar;now->start=1;now=last->next;strcpy(one->name," 根據規則1");mark=1;key=1;break;else if(now->child->next!=NULL&&no