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