2025年智能路徑探索與迷宮問(wèn)題解決方案研究

《編程實(shí)訓(xùn)》 3 32.軟件功能分析 33.數(shù)據(jù)準(zhǔn)備 3 3 42.模塊間調(diào)用關(guān)系 43.主程序模塊 54.抽象數(shù)據(jù)類型描述 5 6 62.各功能模塊的詳細(xì)設(shè)計(jì) 7 7 72.重要問(wèn)題及處理 83.測(cè)試執(zhí)行及成果 8 9 911.1任務(wù)規(guī)定以一種m*n的長(zhǎng)方陣表達(dá)迷宮，0和1分別表達(dá)迷宮中的通路和障礙。設(shè)計(jì)一種程序，對(duì)1.2軟件功能分析設(shè)計(jì)一種迷宮，通過(guò)該程序可以找出通往出口的最短途徑。程序功能有三(1)創(chuàng)立迷宮；(2)求解迷宮；(3)輸出迷宮的解。1.3數(shù)據(jù)準(zhǔn)備0010001000100010000011010111001000010000010001010111100111000101110000002概要設(shè)計(jì)2.1功能模塊圖#defineStackSize100//假定預(yù)分派的?？臻g最多為100個(gè)元素typedefcharDataType;//假定棧元素的數(shù)據(jù)類型為字符typedefstruct{}}{Error("Stackoverflow");//上溢，退出運(yùn)行S->data[++S->top]=x;//棧頂指針加1后將x入棧{Error("Stackunderflow");//下溢，退出運(yùn)行returnS->data[S->top--];//棧頂元素返回后將棧頂指針減1}(6)取棧頂元素returnS->data[S->top}2.2模塊間調(diào)用關(guān)系Stack.h中調(diào)用的base.h#defineFALSE0#defineOK1typedefintStatus;typedefstruct{typedefstruct{S.base=(SElemType*)malloc(INIT_SIZE*sizeof(SElemT*)realloc(S.base,(S.stackSize+INCREMENT}3詳細(xì)設(shè)計(jì)typedefintStatus;typedefstruct{//迷宮中r行c列的位置 typedefstructtypedefstructStatusInitMaze(M●可通位置StatusPass(MazeType●標(biāo)識(shí)非通路StatusMarkPrint(MazeType&StatusMazePath(MazeType&maze,PostTypestart,voidPrintMaze(MazeType&maze)4實(shí)現(xiàn)和調(diào)試4.1重要的算法{將目前位置入棧；//納入途徑若該位置是出口位置，則結(jié)束；//求得途徑寄存在棧中}否則{則{}}{?？贞U明沒(méi)有途徑存在}4.2重要問(wèn)題及處理輸入數(shù)據(jù)：當(dāng)入口為(1,1)時(shí)，出口為(9,8)或"1"(表達(dá)不可以進(jìn)出)隨機(jī)產(chǎn)生一種9*8的迷宮，其中使用迷宮障礙坐標(biāo)如下：輸入過(guò)程如下圖所示：輸入時(shí)(-1,-1)結(jié)束，接著輸入入口參數(shù)(1,1)然后輸入出口參數(shù)(9,8),運(yùn)行：圖中“1”表達(dá)圍墻和障礙物?！癅”表達(dá)走過(guò)但不是通路.而“0”表達(dá)最短途徑。通過(guò)不停的調(diào)試簡(jiǎn)短了程序并最終實(shí)現(xiàn)了功能。第一次寫的程序出現(xiàn)錯(cuò)誤，找不到途徑，陷入死循環(huán)。通過(guò)多次改善，程序可以找到最短途徑。再次改善后能標(biāo)出走過(guò)的但非最短的途徑，有了很大的進(jìn)步。6附錄源程序代碼typedefintStatus;#defineINIT_SIZE100//存儲(chǔ)空間初始分派量#defineINCREMENT10//存儲(chǔ)空間分派增量typedefstruct{//迷宮中r行c列的位置typedefstructintdi;typedefstruct{S.base=(SElemType*)malloc(INIT_SIZE*siz{StatusPush(Stack&S,SEif(S.top-S.base>=S.stackSize)S.base=(SElemType*)realloc(S.base,(S.stackSize+INCREMENT#defineMAXLEN10//迷宮包括外墻最大行列數(shù)目typedef{charadr[MAXLEN][MAXLEN];//可取’''*''@''#'StatusInitMaz{scanf("%d%d",&maze.r,&maze.c);//迷宮行和maze.adr[maze.r+1][i]maze.adr[i][maze.c+1]}printf("輸入障礙物坐標(biāo)，以-1-1結(jié)束：");maze.adr[m][n]='I';/printf("輸入障礙物坐標(biāo)，以-1-1結(jié)束：");StatusPass(MazeTypemaze,PostType//目前位置可通則返回TURE,否則返回FALSEStatusFootPrint(MazeType&maze,PostTy{maze.adr[curpos.r][curpos.c]='0';//"*"表達(dá)可通PostTypeNextPos(PostType&curpos,int}StatusMarkPrint(MazeType&maze,PostTypecu{curstep=1;//{if(curpos.r==end.r&&curpos{}//if{while(e.di==4&&!StackEmpt{}//if}//if}if(!DestroyStack(S))//voidPrintMaze(MazeType&m{//將標(biāo)識(shí)途徑信息的迷宮輸出到終端(包括外墻)printf("\n迷宮的途徑(*---途徑):\n\n");printf("%4c",maze.adr[i][j]);//輸出迷宮//目前位置的標(biāo)識(shí)}scanf("%d%d",&startprintf("\nBeyondthemaze!!!\n");w