實(shí)驗(yàn)二 電路布線問題

實(shí)驗(yàn)二電路布線問題實(shí)驗(yàn)二電路布線問題實(shí)驗(yàn)二電路布線問題實(shí)驗(yàn)二電路布線問題編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:實(shí)驗(yàn)二電路布線問題問題定義及需求分析課題目的和任務(wù)問題描述：印刷電路板將布線區(qū)域劃分為n╳n個(gè)方格陣列。在布線時(shí)，電路只能沿直線或直角布線。為避免線路相交，已布線的方格要做封鎖標(biāo)記。設(shè)起始位置為a，終止位置為b，求解電路布線問題。實(shí)驗(yàn)要求：設(shè)計(jì)印刷電路板的布線模擬程序。1)采用?；蜿?duì)列等數(shù)據(jù)結(jié)構(gòu)。2)采用窮舉法的回溯搜索，求a到b可能的布線線路。3)推薦采用層次優(yōu)先搜索，求a到b最優(yōu)的布線線路。數(shù)據(jù)形式輸入數(shù)據(jù)形式：通過生成隨機(jī)數(shù)的函數(shù)隨機(jī)生成一個(gè)矩陣。輸入值的范圍：生成的矩陣中的數(shù)值為int型，為0或者1，其中0表示死路，1表示通路。輸出數(shù)據(jù)形式：輸出到顯示器。程序功能隨機(jī)給定一個(gè)線路分布矩陣，利用窮舉法，通過棧的應(yīng)用，求出從a到b的可能布線線路；采用層次優(yōu)先搜索，通過隊(duì)列的應(yīng)用，求出a到b的最優(yōu)布線線路。測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)為隨機(jī)生成的矩陣。概要設(shè)計(jì)抽象數(shù)據(jù)類型需要定義一個(gè)位置類型的數(shù)據(jù)，里面包含int型的x和y坐標(biāo)，用來記錄位置信息；再定義一個(gè)SWire的通道塊數(shù)據(jù)類型，里面包含該通道塊的位置數(shù)據(jù)，在路徑上的序號(hào)和方向信息；另外還需要構(gòu)建棧和隊(duì)列的基本結(jié)構(gòu)類型。主程序流程及各模塊之間的調(diào)用關(guān)系詳細(xì)設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)typedefstruct{=0;path[MShortPath].y=0;=;=;intj;for(j=MShortPath-1;j>=0;j--){!=0&&path[i].y!=0;i++){printf("(%d,%d)",path[i].x,path[i].y);if(path[i].x!=8||path[i].y!=8){printf("->");}}printf("\n");=0;path[MShortPath].y=0;=;=;intj;for(j=MShortPath-1;j>=0;j--){path[j]=curpos;for(i=0;i<5;i++){=;=;NextPos(neighbour,i);if(Board[][]==j+2){break;}}=;=;}!=0&&path[i].y!=0;i++){printf("(%d,%d)",path[i].x,path[i].y);if(path[i].x!=8||path[i].y!=8){printf("->");}}printf("\n");//輸出最短路徑搜尋矩陣printf("\n搜尋路徑圖：\n");for(i=0;i<n;i++){for(j=0;j<n;j++){printf("%d\t",Board[i][j]);}printf("\n");}return1;}intmain(){//主函數(shù)Positionstart,finish;=1;=1;=8;=8;CreateBoard();printf("\n可能布線路徑為：");WirePath(Board,star