实验目的

1.掌握回溯法解决问题的一般步骤。
2.学会使用回溯法解决实际问题。
3.掌握分支限界法解决问题的基本思想。
4.学会使用分支限界法解决实际问题。

实验内容

1. 骑士游历问题（采用回溯法）：

在国际象棋的棋盘（8行×8列）上放置一个马，按照“马走日字”的规则，马要遍历棋盘，即到达棋盘上的每一格，并且每格只到达一次。若给定起始位置（x0,y0）,编程探索出一条路径，沿着这条路径马能遍历棋盘上的所有单元格。

2. 行列变换问题（采用分支限界法）：

给定两个mn方格阵列组成的图形A和图形B，每个方格的颜色为黑色或白色，如下图所示。行列变换问题的每一步变换可以交换任意2行或2列方格的颜色，或者将某行或某列颠倒。上述每次变换算作一步。试设计一个算法，计算最少需要多少步，才能将图形A变换为图形B。

算法描述

1. 骑士游历问题的解题思路或算法思想：

算法步骤：

设当前马在棋盘的某个位置（x, y）上，按照规则，下一步有8个方向可走。设二维数组mat表示棋盘，每个元素表示棋盘的一格，其值定义如下：0表示马未到达过，Mat[i, j]= -1表示棋盘边界，自然数表示马到达该格的步数。
马从棋盘上的某一初始位置（x0,y0）开始，每次选择一个方向k，向前走一格，直到走完64格为止。每走一格，设置数组中相应格的元素值为马走的步数。
如果选择的方向k=0，表示可能的8种走向都试探不通，不通的原因是走向超出了棋盘范围，或当前位置已经被马访问过。此时马已无路可走，说明前几步走得不对，应该退回去重新换一种走法，这种逐步试探的设计思想称为回溯算法。
回溯算法在每一格上朝一个方向盲目地进行试探，遇到在某一格上所有方向都不能走通时，才回到前一格上来试探另一个方向。当每一格上的所有方向都试探过，不能走通时，才做出“走不通”的结论。因此该算法在探索时带有一定的盲目性和随机性，运行效率较低。

2. 行列变换问题的解题思路或算法思想：

先进先出队列式分支限界法

例如：x=21541
对其进行交换行的变换（1,2）：x=21061
对其进行交换列的变换（1,2）：x=12867
对其进行某行的颠倒（1）：x=21573
对其进行某列的颠倒（1）：x=22061

程序及运行结果

1. 骑士游历问题的程序：

import math


def Travel(firstX,firstY,board):
    movex=[-2, -1, 1, 2,  2,  1, -1, -2]
    movey=[1,  2, 2, 1, -1, -2, -2, -1]
    nextStepX=[1]*len(board)
    nextStepY=[1]*len(board)
    exitS=[1]*len(board)
    nextX = firstX
    nextY = firstY
    board[nextX][nextY] = 1
    for m in range(2,int(math.pow(len(board), 2)+1)):
        for i in range(0,len(board)):
            exitS[i] = 0
        count = 0
        for i in range(0,8):
            temI = nextX + movex[i]
            temJ = nextY + movey[i]
            if temI < 0 or temI > 7 or temJ < 0 or temJ > 7:
                continue
            if 0 == board[temI][temJ]:
                nextStepX[count] = temI
                nextStepY[count] = temJ
                count =count+1
        min=-1
        if count==0:
            return False
        if 1==count:
            min=0
        else:
            for i in range(0,count):
                for j in range(0,8):
                    temI = nextStepX[i] + movex[j]
                    temJ = nextStepY[i] + movey[j]
                    if temI < 0 or temI > 7 or temJ < 0 or temJ > 7:
                        continue
                    if 0 == board[temI][temJ]:
                        exitS[i] =exitS[i]+1
        tem = exitS[0]
        min = 0
        for  i in range(1,count):
            if tem>exitS[i]:
                tem = exitS[i]
                min = i
        nextX = nextStepX[min]
        nextY = nextStepY[min]
        board[nextX][nextY] = m
    return True


if __name__=='__main__':
    #firstX=input("输入起始点(0-7)：")
    firstX=1
    #firstY=input("输入起始点(0-7)：")
    firstY=1
    board=[[0,0,0,0,0,0,0,0],
           [0,0,0,0,0,0,0,0],
           [0,0,0,0,0,0,0,0],
           [0,0,0,0,0,0,0,0],
           [0,0,0,0,0,0,0,0],
           [0,0,0,0,0,0,0,0],
           [0,0,0,0,0,0,0,0],
           [0,0,0,0,0,0,0,0]]
    if Travel(firstX, firstY, board):
        print("游历完成：")
    else:
        print("游历失败！")
    for i in range(0, len(board)):
        for j in range(0,len(board[0])):
            if board[i][j] < 10:
                print(board[i][j],end=' ')
            else:
                print(board[i][j],end=' ')
            print(" ",end=' ')
        print()

实例：

结果：

1. 行列变换问题的程序：

import java.util.LinkedList;
import java.util.Scanner;
class graph{
    static int sour, dest;//sour是图形的初始整数，dest是图形的目的整数
    static int ans[]=new int[1<<16];//静态变量（即全局变量），用于存放图形变换的路径
    int m=4,n=4,x;
    int row[]=new int[4];
    int col[]=new int[4];
    void setx(int x){
        this.x=x;
    }
    int getx(){
        return this.x;
    }
    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(){//将一个整数划分成四列二进制
        int y;
        for(int j=0;j<n;j++) col[j]=0;
        y=1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if((x&1)!=0) //如果x的最低位是1
                    col[j]|=y;
                x>>=1;
            }
            y<<=1;
        }
    }
    void rowy(){//将四行二进制转换成一个整数
        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<m;i++){
            for(int j=0;j<n;j++){
                if((col[j]&1)!=0) //如果y的最低位是1
                    x|=z;
                z<<=1;
                col[j]>>=1;
            }
        }
        this.x=x;
    }
    void Swaprow(int i, int j){//将二进数进行行互换
        int o;
        o=row[i];
        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);
        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++){
            if((col[k]&1)!=0) //如果y的最低位是1
                y|=z;
            z>>=1;
            col[k]>>=1;
        }
        col[k]=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, 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 B {
    public static void main(String[] args){
        final int Maxsize=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();
//初始化，输入初始值和目标值,即1010010000101010和1010000001100101
        Scanner scanner = new Scanner(System.in);
        String ss=scanner.nextLine();
        char[]chArrs=ss.toCharArray();
        for(graph.sour=i=0;i<16;i++){
            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;
        }
        LinkedList  queue=new LinkedList();//初始化先进先出队列
        for(int k=0; k<Maxsize;k++)hash[k]=-1;
        G1.x=graph.sour;
        hash[G1.x]=0;
        queue.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(hash[N]==-1){
                        hash[N]=hash[E]+1;
                        graph.ans[N]=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(hash[N]==-1){
                        hash[N]=hash[E]+1;
                        graph.ans[N]=E;
                        queue.add(N);
                    }
                }
            }
            for(i=0;i<4;i++){//行颠倒
                gN.x=gN.revrow(E,i);
                N=gN.x;
                if(hash[N]==-1){
                    hash[N]=hash[E]+1;
                    graph.ans[N]=E;
                    queue.add(N);
                }
            }
            for(i=0;i<4;i++){//列颠倒
                gN.x=gN.revcol(E,i);
                N=gN.x;
                if(hash[N]==-1){
                    hash[N]=hash[E]+1;
                    graph.ans[N]=E;
                    queue.add(N);
                }
            }
            if(hash[graph.dest]!=-1){//如果目的值被遍历到，则退出循环
                System.out.println("OK");break;
            }
        }
        System.out.println(hash[graph.dest]);
        output(graph.dest);//输出变换的路径
    }
    public static void outb(int x){//将一个整数以四行二进制的形式显示
        for(int i=0; i<4;i++){
            for(int j=0;j<4;j++){
                if((x&1)!=0)System.out.print(1);
                else System.out.print(0);
                x/=2;
            }
            System.out.println();
        }
    }
    public static void output(int N){
        if(N==graph.sour){
            System.out.println();
            outb(N);
            return;
        }
        output(graph.ans[N]);//graph.ans[N]存放着从初始值到目的值的遍历路径
        System.out.println();
        outb(N);
    }
}
//1010010000101010
//1010000001100101

实例：
1010010000101010
1010000001100101
结果：

总结

实验心得体会：

通过这次实验，我深入了解了贪心算法的基本概念和两个要素，熟悉了贪心算法解决问题的基本步骤，并解决实际问题。

改进意见：

实验成绩： 指导教师： 年 月 日