lab6-回溯算法设计与应用

1、精选优质文档-倾情为你奉上实验六 回溯算法设计与应用一基本原理的概括DFS+剪枝（在状态空间树上作带剪枝的DFS搜索）Ø剪枝：若搜索到某结点，其对应的部分解不满足解的约束条件且可断定以其为根的子树上不包含答案结点，则不搜索该子树，直接回到其父结点，继续DFS。 利用回溯法可求问题的一个解，多个解，所有解，最优解，还可判断解的存在性。 二该类算法设计与实现的要点回溯法通常包含以下3个步骤： 1)定义给定问题的解空间； 2)确定并表示解的约束条件和其它的剪枝条件； 3)结合剪枝深度优先搜索相应的状态空间树。 注意：回溯法的一个特征是在搜索过程中动态的产生问题的状态空间树，任何时候只存根到

2、当前搜索的结点的路径。三实验目的和要求理解回溯法的基本原理，掌握回溯法设计的基本方法及步骤，并应用于具体问题的解决。四实验内容(一) 马的周游问题1. 问题描述在n x n棋盘（有n x n个格点的棋盘）的某个格点上有一个中国象棋马，马走日字。求一条周游棋盘的路径，使得马能够从起始位置起沿着该路径每个格点恰好走一次最后回到出发位置。2. 具体要求用回溯法解决该问题。输入一个正整数n，输出一个解，解的输出形式尽可能直观。 3. 设计与实现代码如下：#include <iostream>#include <iomanip>#include <stdlib.h>#

3、include <Windows.h>using namespace std;inline int good(int x,int y,int s3030,int n) if(x>=0&&x<=n-1&&y>=0&&y<=n-1&&syx=88) return 1; else return 0;void main()int flag=1;while(flag=1)cout<<endl;cout<<"1、开始求解"<<endl<<&

4、quot;2、退出"<<endl;cout<<endl;cout<<" 请输入您的选项(1 2) "<<endl;int cd;cout<<" 您的选项是: "cin>>cd;switch(cd)case 1: enum roadd11,d12,d21,d22,d31,d32,d41,d42; road d100; int m=0; int x=0,y=0;int p=0,q=0; int s3030; int i,j; int w=1; int num=0; int n;

5、 cout<<" 输入棋盘的大小(不大于10):n=" cin>>n; for(i=0;i<n;+i) for(j=0;j<n;j+) sij=88; cout<<" 原始棋盘的情况"<<endl; for(i=0;i<n;i+) for(j=0;j<n;j+) cout<<sij<<" " cout<<endl; cout<<" 输入马在棋盘中的位置:"<<endl; cout<

6、;<"x=" cin>>p; cout<<"y=" cin>>q; p-; q-;x=p;y=q; d0=d11; syx=1; do if(dm=d11&&good(x+1,y-2,s,n)x+;y=y-2;d+m=d11;syx=+w;num+; else if(dm=d12&&good(x+2,y-1,s,n)x=x+2;y-;d+m=d11;syx=+w;num+; else if(dm=d21&&good(x+2,y+1,s,n)x=x+2;y+;d+m=

7、d11;syx=+w;num+; else if(dm=d22&&good(x+1,y+2,s,n)x+;y=y+2;d+m=d11;syx=+w;num+; else if(dm=d31&&good(x-1,y+2,s,n)x-;y=y+2;d+m=d11;syx=+w;num+; else if(dm=d32&&good(x-2,y+1,s,n)x=x-2;y+;d+m=d11;syx=+w;num+; else if(dm=d41&&good(x-2,y-1,s,n)x=x-2;y-;d+m=d11;syx=+w;num+;

8、 else if(dm=d42&&good(x-1,y-2,s,n)x-;y=y-2;d+m=d11;syx=+w;num+; else while(dm=d42) m-; if(dm=d11)syx=88;-w;x-;y=y+2; if(dm=d12)syx=88;-w;x=x-2;y+; if(dm=d21)syx=88;-w;x=x-2;y-; if(dm=d22)syx=88;-w;x-;y=y-2; if(dm=d31)syx=88;-w;x+;y=y-2; if(dm=d32)syx=88;-w;x=x+2;y-; if(dm=d41)syx=88;-w;x=x+2

9、;y+; if(m!=0&&dm=d42)syx=88;-w;x+;y=y+2; dm=road(dm+1); while(m!=0|d0!=d42|good(x-1,y-2,s,n)&&m!=n*n-1|(p-x)*(p-x)+(q-y)*(q-y)!=5); cout<<" 马跳之后的情况(数字表示跳跃先后顺序)"<<endl; for(i=0;i<n;i+) for(j=0;j<n;j+) cout<<setfill('0')<<setw(2)<<s

10、ij<<" " cout<<endl; cout<<endl;cout<<endl;break; case 2:exit(1);break;default:cout<<"选择错误！ 请重新选择！"<<endl;break;(二) 寻宝问题1. 问题描述对于某个m*n的字符串数组，相当于一个m行n列的平面形状的方格。里面S表示起点，W表示障碍，B表示可走（但是不一定可以通），X表示出口。对于起点S，有8个方向可以走，当然前提是在没有障碍的情况之下，其中可以分为单步走（on foot）和

11、跳步走（by jump）两种情况，从起点S开始追寻最短的出口路径count2。2设计与实现#include<iostream>using namespace std;int main()char a1010;int n,m,x,y,i,j,sx,sy,x1,y1,x2,y2,min,k100,flag1010=0;int tag82=-1,0,0,1,1,0,0,-1,-2,2,2,2,2,-2,-2,-2;cin>>n;while(n-)cin>>x>>y;for(i=0;i<x;i+)for(j=0;j<y;j+)cin>&

12、gt;aij;if(aij='S')x1=i;y1=j; min=32767; i=1;k0=0; ki=-1; flagx1y1=1; while(i>=1) while(ki<7) ki=ki+1; x2=x1+tagki0; y2=y1+tagki1; if(x2>=0&&x2<x&&y2>=0&&y2<y&&ax2y2!='W'&&i<min) if(ax2y2='X') if(i<min) min=i; else if(flagx2y2=0) flagx2