




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、 算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告專 業(yè)班 級(jí)姓 名學(xué) 號(hào)實(shí)驗(yàn)名稱實(shí)驗(yàn)四:回溯與分支限界算法設(shè)計(jì)實(shí)驗(yàn)?zāi)康?.掌握回溯法解決問題的一般步驟。2.學(xué)會(huì)使用回溯法解決實(shí)際問題。3.掌握分支限界法解決問題的基本思想。4.學(xué)會(huì)使用分支限界法解決實(shí)際問題。實(shí)驗(yàn)內(nèi)容1. 騎士游歷問題(采用回溯法):在國(guó)際象棋的棋盤(8行×8列)上放置一個(gè)馬,按照“馬走日字”的規(guī)則,馬要遍歷棋盤,即到達(dá)棋盤上的每一格,并且每格只到達(dá)一次。若給定起始位置(x0,y0),編程探索出一條路徑,沿著這條路徑馬能遍歷棋盤上的所有單元格。2. 行列變換問題(采用分支限界法):給定兩個(gè)m´n方格陣列組成的圖形A和圖形B,每個(gè)方格
2、的顏色為黑色或白色,如下圖所示。行列變換問題的每一步變換可以交換任意2行或2列方格的顏色,或者將某行或某列顛倒。上述每次變換算作一步。試設(shè)計(jì)一個(gè)算法,計(jì)算最少需要多少步,才能將圖形A變換為圖形B。算法描述1. 騎士游歷問題的解題思路或算法思想:如果在每步選擇方向時(shí),不是任意選擇一個(gè)方向,而是經(jīng)過一定的測(cè)試和計(jì)算,“預(yù)見”每條路的“寬窄”,再選擇一條最“窄”的路先走,成功的可能性較大。理由是先走“困難的路”,光明大道留在后面。因?yàn)槊恳桓襁t早都要走到,與其把困難留在后面,不如先走“困難的路”,這樣路就會(huì)越走越寬,成功的機(jī)會(huì)就越大。這種方法稱為預(yù)見算法。為每個(gè)方向測(cè)定一個(gè)值可通路數(shù),它表示該位置上還
3、有多少條通路。在每一格上對(duì)8個(gè)方向都進(jìn)行試探,并分析比較,下一步應(yīng)該選擇可通路數(shù)值最小的方向走。2. 行列變換問題的解題思路或算法思想:先進(jìn)先出隊(duì)列式分支限界法輸入數(shù)據(jù),將計(jì)算出的最少變換次數(shù)和相應(yīng)的變換序列輸出。第1 行是最少變換次數(shù)。從第2 行開始,每行用4 個(gè)數(shù)表示一次變換。程序及運(yùn)行結(jié)果1. 騎士游歷問題的程序:package com.t5;import java.util.Scanner; public class Qishi private boolean Travel(int firstX, int firstY, int board) / 對(duì)應(yīng)騎士可走的8個(gè)方向 int mov
4、ex = -2, -1, 1, 2, 2, 1, -1, -2 ; int movey = 1, 2, 2, 1, -1, -2, -2, -1 ; / 下一步出路的位置 int nextStepX = new intboard.length; int nextStepY = new intboard.length; / 記錄出路的個(gè)數(shù) int exitS = new intboard.length; int nextX = firstX; int nextY = firstY; boardnextXnextY = 1; for (int m = 2; m <= Math.pow(boa
5、rd.length, 2); m+) /初始化下一個(gè)位置可走的位置的數(shù)目 for (int i = 0; i < board.length; i+) exitSi = 0; int count = 0; / 試探8個(gè)方向 for (int i = 0; i < 8; i+) int temI = nextX + movexi; int temJ = nextY + moveyi; / 走到邊界,路斷 if (temI < 0 | temI > 7 | temJ < 0 | temJ > 7) continue; / 記錄下可走的方向 if (0 = boar
6、dtemItemJ) nextStepXcount = temI; nextStepYcount = temJ; count+; / 到這里,cout表示當(dāng)前點(diǎn)有幾種走法。nextStep中存儲(chǔ)各種走法的坐標(biāo)。 int min = -1; if (count = 0) return false; if (1 = count) min = 0; else for (int i = 0; i < count; i+) for (int j = 0; j < 8; j+) int temI = nextStepXi + movexj; int temJ = nextStepYi + mo
7、veyj; if (temI < 0 | temI > 7 | temJ < 0 | temJ > 7) continue; / 記錄下這個(gè)位置可走的方向數(shù) if (0 = boardtemItemJ) exitSi+; int tem = exitS0; min = 0; / 從可走的方向中,尋找最少走的出路 for (int i = 1; i < count; i+) if (tem > exitSi) tem = exitSi; min = i; / 得到最少的出路 nextX = nextStepXmin; nextY = nextStepYmin;
8、 boardnextXnextY = m; return true; public static void main(String args) int firstX, firstY; System.out.println("輸入起始點(diǎn)(0-7):"); Scanner scanner = new Scanner(System.in); firstX = scanner.nextInt(); firstY = scanner.nextInt(); int board = new int88; Qishi knight = new Qishi(); if (knight.Tra
9、vel(firstX, firstY, board) System.out.println("游歷完成:"); else System.out.println("游歷失敗!n"); for (int i = 0; i < board.length; i+) for (int j = 0; j < board0.length; j+) if (boardij < 10) System.out.print(" " + boardij); else System.out.print(boardij); System.out
10、.print(" "); System.out.println(); 實(shí)例:2. 行列變換問題的程序:package com.t8;import java.util.LinkedList;import java.util.Scanner;class graphstatic int sour, dest;/sour是圖形的初始整數(shù),dest是圖形的目的整數(shù)static int ans=new int1<<16;/靜態(tài)變量(即全局變量),用于存放圖形變換的路徑int m=4,n=4,x;int row=new int4;int col=new int4;void s
11、etx(int x)this.x=x;int getx()return this.x;void rowx()/將一個(gè)整數(shù)劃分成四行二進(jìn)制int y;for(int i=0;i<m;i+)y=1;rowi=0;for(int j=0;j<n;j+)if(x&1)!=0) /如果x的最低位是1rowi|=y;y<<=1;x>>=1;void colx()/將一個(gè)整數(shù)劃分成四列二進(jìn)制int y;for(int j=0;j<n;j+) colj=0;y=1;for(int i=0;i<m;i+)for(int j=0;j<n;j+)if(x
12、&1)!=0) /如果x的最低位是1colj|=y;x>>=1;y<<=1;void rowy()/將四行二進(jìn)制轉(zhuǎn)換成一個(gè)整數(shù)int z=1, x=0, y;for(int i=0;i<m;i+)y=rowi;for(int j=0;j<n;j+)if(y&1)!=0) /如果y的最低位是1x|=z;z<<=1;y>>=1;this.x=x;void coly()/將四列二進(jìn)制轉(zhuǎn)換成一個(gè)整數(shù)int z=1, x=0, y;for(int i=0;i<m;i+)for(int j=0;j<n;j+)if(co
13、lj&1)!=0) /如果y的最低位是1x|=z;z<<=1;colj>>=1;this.x=x;void Swaprow(int i, int j)/將二進(jìn)數(shù)進(jìn)行行互換int o;o=rowi;rowi=rowj;rowj=o;void Swapcol(int i, int j)/將二進(jìn)數(shù)進(jìn)行列互換int o;o=coli;coli=colj;colj=o;void reveR(int k)/將二進(jìn)數(shù)進(jìn)行行顛倒int y=0, z=1<<(4-1);for(int j=0;j<4;j+)if(rowk&1)!=0) /如果y的最低位是
14、1y|=z;z>>=1;rowk>>=1;rowk=y;void reveC(int k)/將二進(jìn)數(shù)進(jìn)行列顛倒int y=0, z=1<<(4-1);for(int j=0;j<4;j+)if(colk&1)!=0) /如果y的最低位是1y|=z;z>>=1;colk>>=1;colk=y;int rowswap(int x, int i, int j)/將二進(jìn)制數(shù)的第i行與第j行互換this.x=x;rowx();Swaprow(i,j);rowy();return this.x;int colswap(int x,
15、int i, int j)/將二進(jìn)制數(shù)的第i列與第j列互換this.x=x;colx();Swapcol(i,j);coly();return this.x;int revrow(int x, int k)/將二進(jìn)制數(shù)的第K行顛倒this.x=x;rowx();reveR(k);rowy();return this.x;int revcol(int x, int k)/將二進(jìn)制數(shù)的第K列顛倒this.x=x;colx();reveC(k);coly();return this.x;public class Tuxing public static void main(String args)f
16、inal int Maxsize=1<<16;graph gN;/用于進(jìn)行行變換、列變換、行顛倒、列顛倒int E,N;/變換前的初始值,變換前的結(jié)果值gN=new graph();int hash=new int1<<16;int i,j,h=0;char c;graph G1=new graph();Scanner scanner = new Scanner(System.in); String ss=scanner.nextLine();charchArrs=ss.toCharArray();for(graph.sour=i=0;i<16;i+)c=chAr
17、rsi;graph.sour|=(int)(c-'0')<<i;String sd=scanner.nextLine();charchArrd=sd.toCharArray();for(graph.dest=i=0;i<16;i+)c=chArrdi;graph.dest|=(int)(c-'0')<<i;LinkedList queue=new LinkedList();/初始化先進(jìn)先出隊(duì)列for(int k=0; k<Maxsize;k+)hashk=-1;G1.x=graph.sour;hashG1.x=0;queue.
18、add(G1.x);while(!queue.isEmpty()/以先進(jìn)先出隊(duì)列式實(shí)現(xiàn)分支限界法E=(int)queue.removeFirst();for(i=0;i<4-1;i+)/行變換for(j=i+1;j<4;j+)gN.x=gN.rowswap(E,i,j);N=gN.x;if(hashN=-1)hashN=hashE+1;graph.ansN=E;queue.add(N);for(i=0;i<4-1;i+)/列變換for(j=i+1;j<4;j+)gN.x=gN.colswap(E,i,j);N=gN.x;if(hashN=-1)hashN=hashE+1;graph.ansN=E;queue.add(N);for(i=0;i<4;i+)/行顛倒gN.x=gN.revrow(E,i);N=gN.x;if(hashN=-1)hashN=hashE+1;graph.ansN=E;queue.add(N);for(i=0;i<4;i+)/列顛倒gN.x=gN.revcol(E,i);N=gN.x;if(hashN=-1)hashN=hashE+1;graph.ansN=E;queue.add(N);if(hashgraph.des
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 模具代加工合同協(xié)議書
- 紅酒訂購(gòu)協(xié)議書
- 商業(yè)房租賃合同協(xié)議書
- 畜禽禁養(yǎng)協(xié)議書
- 管道管理協(xié)議書
- 續(xù)簽意向協(xié)議書
- 管養(yǎng)移交協(xié)議書
- 移植樹木協(xié)議書
- 培訓(xùn)班校長(zhǎng)合同協(xié)議書
- 碼頭維修協(xié)議書
- 房屋安全性鑒定培訓(xùn)
- 抑郁癥與rTMS治療
- 康復(fù)家居活動(dòng)改造課件
- DB23T 3630-2023黑龍江省超低能耗建筑節(jié)能工程施工質(zhì)量驗(yàn)收標(biāo)準(zhǔn)
- 2024版建筑工程外架拆除承包合同2篇
- SVG工作原理及基礎(chǔ)知識(shí)
- 《變配電工程》課件
- 數(shù)學(xué)分析選講知到智慧樹章節(jié)測(cè)試課后答案2024年秋齊魯師范學(xué)院
- 乳腺癌術(shù)后出血護(hù)理
- 2024-2030年中國(guó)吡啶行業(yè)發(fā)展可行性及投資規(guī)劃分析報(bào)告
- 中華護(hù)理學(xué)會(huì)團(tuán)體標(biāo)準(zhǔn)-氣管切開非機(jī)械通氣患者氣道護(hù)理
評(píng)論
0/150
提交評(píng)論