内容发布更新时间 : 2024/12/24 8:01:13星期一 下面是文章的全部内容请认真阅读。

算

法设计与分析实验报

告

班 级 学 号 实验四：回溯与分支限界算法设计 1.掌握回溯法解决问题的一般步骤。 2.学会使用回溯法解决实际问题。 3.掌握分支限界法解决问题的基本思想。 4.学会使用分支限界法解决实际问题。 1. 骑士游历问题（采用回溯法）： 在国际象棋的棋盘（8行×8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0,y0）,编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。 2. 行列变换问题（采用分支限界法）： 给定两个m?n方格阵列组成的图形A和图形B，每个方格的颜色为黑色或白色，如下图所示。行列变换问题的每一步变换可以交换任意2行或2列方格的颜色，或者将某行或某列颠倒。上述每次变换算作一步。试设计一个算法，计算最少需要多少步，才能将图形A变换为图形B。

专 业 姓 名 实验名称 实验目的 实验内容 图形A图形B 算法描述 1. 骑士游历问题的解题思路或算法思想： 如果在每步选择方向时，不是任意选择一个方向，而是经过一定的测试和计算，“预见”每条路的“宽窄”，再选择一条最“窄”的路先走，成功的可能性较大。理由是先走“困难的路”，光明大道留在后面。因为每一格迟早都要走到，与其把困难留在后面，不如先走“困难的路”，这样路就会越走越宽，成功的机会就越大。这种方法称为预见算法。 为每个方向测定一个值――可通路数，它表示该位置上还有多少条通路。在每一格上对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[] movex = { -2, -1, 1, 2, 2, 1, -1, -2 }; int[] movey = { 1, 2, 2, 1, -1, -2, -2, -1 }; // 下一步出路的位置 int[] nextStepX = new int[board.length]; int[] nextStepY = new int[board.length]; // 记录出路的个数 int[] exitS = new int[board.length]; int nextX = firstX; int nextY = firstY; board[nextX][nextY] = 1; for (int m = 2; m <= Math.pow(board.length, 2); m++) { //初始化下一个位置可走的位置的数目 for (int i = 0; i < board.length; i++) { exitS[i] = 0; } int count = 0; // 试探8个方向 for (int i = 0; i < 8; i++) { int temI = nextX + movex[i]; int temJ = nextY + movey[i]; // 走到边界，路断 if (temI < 0 || temI > 7 || temJ < 0 || temJ > 7) { continue; } // 记录下可走的方向 if (0 == board[temI][temJ]) { nextStepX[count] = temI; nextStepY[count] = 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 = nextStepX[i] + movex[j]; int temJ = nextStepY[i] + movey[j]; if (temI < 0 || temI > 7 || temJ < 0 || temJ > 7) { continue; } // 记录下这个位置可走的方向数 if (0 == board[temI][temJ]) { exitS[i]++; } } } int tem = exitS[0]; min = 0; // 从可走的方向中，寻找最少走的出路 for (int i = 1; i < count; i++) { if (tem > exitS[i]) { tem = exitS[i]; min = i; } } } // 得到最少的出路