《回溯与分支限界算法设计说明》由会员分享，可在线阅读，更多相关《回溯与分支限界算法设计说明（17页珍藏版）》请在金锄头文库上搜索。
1、. . 算法设计与分析实验报告专 业班 级姓 名学 号实验名称实验四：回溯与分支限界算法设计实验目的1.掌握回溯法解决问题的一般步骤。2.学会使用回溯法解决实际问题。3.掌握分支限界法解决问题的基本思想。4.学会使用分支限界法解决实际问题。实验容1. 骑士游历问题（采用回溯法）：在国际象棋的棋盘（8行8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0,y0）,编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。2. 行列变换问题（采用分支限界法）：给定两个mn方格阵列组成的图形A和图形B，每个方格的颜色为黑色或白色，
2、如下图所示。行列变换问题的每一步变换可以交换任意2行或2列方格的颜色，或者将某行或某列颠倒。上述每次变换算作一步。试设计一个算法，计算最少需要多少步，才能将图形A变换为图形B。算法描述1. 骑士游历问题的解题思路或算法思想：如果在每步选择方向时，不是任意选择一个方向，而是经过一定的测试和计算，“预见”每条路的“宽窄”，再选择一条最“窄”的路先走，成功的可能性较大。理由是先走“困难的路”，光明大道留在后面。因为每一格迟早都要走到，与其把困难留在后面，不如先走“困难的路”，这样路就会越走越宽，成功的机会就越大。这种方法称为预见算法。为每个方向测定一个值可通路数，它表示该位置上还有多少条通路。在每一
3、格上对8个方向都进行试探，并分析比较，下一步应该选择可通路数值最小的方向走。2. 行列变换问题的解题思路或算法思想：先进先出队列式分支限界法输入数据，将计算出的最少变换次数和相应的变换序列输出。第1 行是最少变换次数。从第2 行开始，每行用4 个数表示一次变换。程序及运行结果1. 骑士游历问题的程序：package .t5;import java.util.Scanner; public class Qishi private boolean Travel(int firstX, int firstY, int board) / 对应骑士可走的8个方向 int movex = -2, -1,
4、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(board.length, 2); m+
5、) /初始化下一个位置可走的位置的数目 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 7 | temJ 7) continue; / 记录下可走的方向 if (0 = boardtemItemJ) nextStepXcount = temI; nextStepYcount = temJ; count+;
6、/ 到这里，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 + moveyj; if (temI 7 | temJ 7) continue; / 记录下这个位置可走的方向数 if (0 = boardtemItemJ)
7、 exitSi+; int tem = exitS0; min = 0; / 从可走的方向中，寻找最少走的出路 for (int i = 1; i exitSi) tem = exitSi; min = i; / 得到最少的出路 nextX = nextStepXmin; nextY = nextStepYmin; boardnextXnextY = m; return true; public static void main(String args) int firstX, firstY; System.out.println(输入起始点(0-7)：); Scanner scanner =
8、 new Scanner(System.in); firstX = scanner.nextInt(); firstY = scanner.nextInt(); int board = new int88; Qishi knight = new Qishi(); if (knight.Travel(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
9、; j+) if (boardij 10) System.out.print( + boardij); else System.out.print(boardij); System.out.print( ); System.out.println(); 实例：2. 行列变换问题的程序：package .t8;import java.util.LinkedList;import java.util.Scanner;class graphstatic int sour, dest;/sour是图形的初始整数，dest是图形的目的整数static int ans=new int116;/静态变量（即全局变量），用于存放图形变换的路径int m=4,n=4,x;int row=new int4;int col=new int4;void setx(int x)this.x=x;int getx()return this.x;void r
