1、 算法設計與分析實驗報告專 業班 級姓 名學 號實驗名稱實驗四：回溯與分支限界算法設計實驗目的1.掌握回溯法解決問題的一般步驟。2.學會使用回溯法解決實際問題。3.掌握分支限界法解決問題的基本思想。4.學會使用分支限界法解決實際問題。實驗內容1. 騎士游歷問題（采用回溯法）：在國際象棋的棋盤（8行×8列）上放置一個馬，按照“馬走日字”的規則，馬要遍歷棋盤，即到達棋盤上的每一格，并且每格只到達一次。若給定起始位置（x0,y0）,編程探索出一條路徑，沿著這條路徑馬能遍歷棋盤上的所有單元格。2. 行列變換問題（采用分支限界法）：給定兩個m´n方格陣列組成的圖形A和圖形B，每個方格

2、的顏色為黑色或白色，如下圖所示。行列變換問題的每一步變換可以交換任意2行或2列方格的顏色，或者將某行或某列顛倒。上述每次變換算作一步。試設計一個算法，計算最少需要多少步，才能將圖形A變換為圖形B。算法描述1. 騎士游歷問題的解題思路或算法思想：如果在每步選擇方向時，不是任意選擇一個方向，而是經過一定的測試和計算，“預見”每條路的“寬窄”，再選擇一條最“窄”的路先走，成功的可能性較大。理由是先走“困難的路”，光明大道留在后面。因為每一格遲早都要走到，與其把困難留在后面，不如先走“困難的路”，這樣路就會越走越寬，成功的機會就越大。這種方法稱為預見算法。為每個方向測定一個值可通路數，它表示該位置上還

3、有多少條通路。在每一格上對8個方向都進行試探，并分析比較，下一步應該選擇可通路數值最小的方向走。2. 行列變換問題的解題思路或算法思想：先進先出隊列式分支限界法輸入數據，將計算出的最少變換次數和相應的變換序列輸出。第1 行是最少變換次數。從第2 行開始，每行用4 個數表示一次變換。程序及運行結果1. 騎士游歷問題的程序：package com.t5;import java.util.Scanner; public class Qishi private boolean Travel(int firstX, int firstY, int board) / 對應騎士可走的8個方向 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; / 記錄出路的個數 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+) /初始化下一個位置可走的位置的數目 for (int i = 0; i < board.length; i+) exitSi = 0; int count = 0; / 試探8個方向 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表示當前點有幾種走法。nextStep中存儲各種走法的坐標。 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; / 記錄下這個位置可走的方向數 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("輸入起始點(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(); 實例：2. 行列變換問題的程序：package com.t8;import java.util.LinkedList;import java.util.Scanner;class graphstatic int sour, dest;/sour是圖形的初始整數，dest是圖形的目的整數static int ans=new int1<<16;/靜態變量（即全局變量），用于存放圖形變換的路徑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()/將一個整數劃分成四行二進制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()/將一個整數劃分成四列二進制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()/將四行二進制轉換成一個整數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()/將四列二進制轉換成一個整數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)/將二進數進行行互換int o;o=rowi;rowi=rowj;rowj=o;void Swapcol(int i, int j)/將二進數進行列互換int o;o=coli;coli=colj;colj=o;void reveR(int k)/將二進數進行行顛倒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)/將二進數進行列顛倒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)/將二進制數的第i行與第j行互換this.x=x;rowx();Swaprow(i,j);rowy();return this.x;int colswap(int x,

15、int i, int j)/將二進制數的第i列與第j列互換this.x=x;colx();Swapcol(i,j);coly();return this.x;int revrow(int x, int k)/將二進制數的第K行顛倒this.x=x;rowx();reveR(k);rowy();return this.x;int revcol(int x, int k)/將二進制數的第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;/用于進行行變換、列變換、行顛倒、列顛倒int E,N;/變換前的初始值，變換前的結果值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();/初始化先進先出隊列for(int k=0; k<Maxsize;k+)hashk=-1;G1.x=graph.sour;hashG1.x=0;queue.

18、add(G1.x);while(!queue.isEmpty()/以先進先出隊列式實現分支限界法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