回溯与分支限界算法设计

row[i]=row[j];
row[j]=o;
}
void Swapcol(int i, int j){//将二进数进行列互换
int o;
o=col[i];
col[i]=col[j];
col[j]=o;
}
void reveR(int k){//将二进数进行行颠倒
int y=0, z=1<<(4-1);
程序及运行结果
1.骑士游历问题的程序：
package com.t5;
import java.util.Scanner;
public class Qishi{
private boolean Travel(int firstX, int firstY, int[][]board) {
//对应骑士可走的8个方向
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] < 10) {
System.out.print(" " + board[i][j]);
} else {
System.out.print(board[i][j]);
}
System.out.print(" ");
c=chArrs[i];
graph.sour|=(int)(c-'0')<<i;
}
String sd=scanner.nextLine();
char[]chArrd=sd.toCharArray();
for(graph.dest=i=0;i<16;i++){
c=chArrd[i];
graph.dest|=(int)(c-'0')<<i;
//初始化，输入初始值和目标值,即1010010000101010和1010000001100101
Scannerscanner= new Scanner(System.in);
String ss=scanner.nextLine();
char[]chArrs=ss.toCharArray();
for(graph.sour=i=0;i<16;i++){
如果在每步选择方向时，不是任意选择一个方向，而是经过一定的测试和计算，“预见”每条路的“宽窄”，再选择一条最“窄”的路先走，成功的可能性较大。理由是先走“困难的路”，光明大道留在后面。因为每一格迟早都要走到，与其把困难留在后面，不如先走“困难的路”，这样路就会越走越宽，成功的机会就越大。这种方法称为预见算法。
nextStepY[count] = temJ;
count++;
}
}
//到这里，cout表示当前点有几种走法。nextStep中存储各种走法的坐标。
int min = -1;
if (count == 0) {
return false;
}
if (1 == count) {
min = 0;
} else {
final intMaxsize=1<<16;
graph gN;//用于进行行变换、列变换、行颠倒、列颠倒
int E,N;//变换前的初始值，变换前的结果值
gN=new graph();
int hash[]=new int[1<<16];
int i,j,h=0;char c;
graph G1=new graph();
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++) {
2.行列变换问题（采用分支限界法）：
给定两个mn方格阵列组成的图形A和图形B，每个方格的颜色为黑色或白色，如下图所示。行列变换问题的每一步变换可以交换任意2行或2列方格的颜色，或者将某行或某列颠倒。上述每次变换算作一步。试设计一个算法，计算最少需要多少步，才能将图形A变换为图形B。
算法描述
1.骑士游历问题的解题思路或算法思想：
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]){
int firstX, firstY;
System.out.println("输入起始点(0-7)：");
Scannerscanner= new Scanner(System.in);
firstX = scanner.nextInt();
firstY = scanner.nextInt();
int[][] board = new int[8][8];
}
LinkedListqueue=newLinkedList();//初始化先进先出队列
tem = exitS[i];
min = i;
}
}
}
//得到最少的出路
nextX = nextStepX[min];
nextY = nextStepY[min];
board[nextX][nextY] = m;
}
return true;
}
public static void main(String[] args) {
int z=1, x=0, y;
for(int i=0;i<m;i++){
y=row[i];
for(int j=0;j<n;j++){
if((y&1)!=0) //如果y的最低位是1
x|=z;
z<<=1;
y>>=1;
}
}
this.x=x;
}
void coly(){//将四列二进制转换成一个整数
int z=1, x=0,y;
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){
int temJ = nextY + movey[i];
//走到边界，路断
if (temI < 0 || temI > 7 || temJ < 0 || temJ > 7) {
continue;
}
//记录下可走的方向
if (0 ==board[temI][temJ]) {
nextStepX[count] = temI;
}
void rowx(){//将一个整数划分成四行二进制
int y;
for(int i=0;i<m;i++){
y=1;
row[i]=0;
for(int j=0;j<n;j++){
if((x&1)!=0) //如果x的最低位是1
row[i]|=y;
y<<=1;
x>>=1;
}
}
}
void colx(){//将一个整数划分成四列二进制
//初始化下一个位置可走的位置的数目
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];
for(int j=0;j<4;j++){
if((row[k]&1)!=0) //如果y的最低位是1
y|=z;
z>>=1;
row[k]>>=1;
}
row[k]=y;
}
void reveC(int k){//将二进数进行列颠倒
int y=0, z=1<<(4-1);
for(int j=0;j<4;j++){
算法设计与分析实验报告
专业
班级
姓名
学号
实验名称
实验四：回溯与分支限界算法设计
实验目的
1.掌握回溯法解决问题的一般步骤。
2.学会使用回溯法解决实际问题。
3.掌握分支限界法解决问题的基本思想。
4.学会使用分支限界法解决实际问题。
实验内容
1.骑士游历问题（采用回溯法）：
在国际象棋的棋盘（8行×8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0,y0）,编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。