《算法设计与分析-回溯法》实验报告
">242、 }
243、 for(int i = 1; i <= xLength; i++)
244、 for(int j = 1; j <= yLength; j++) {
245、 cin >> maze[i][j];
246、 visited[i][j] = 0;
247、 }
248、 cout<<"入口位置坐标:";
249、 cin>>xIn>>yIn;
250、 xIn++;
251、 yIn++;
252、 cout<<"出口位置坐标:";
253、 cin>>xOut>>yOut;
254、 xOut++;
255、 yOut++;
256、 visited[xIn][yIn] = 1; //从入口开始
257、 if(seekPath(xIn, yIn))
258、 printf("(%d,%d)\n",xIn-1,yIn-1); //输出剩余的起始点
259、 else
260、 cout<<"无解";
261、 return 0;
262、 }
四、运行输出结果：
1、 着色问题
2、 批处理作业调度问题
3、 n皇后问题
4、 迷宫问题
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
1、关于迷宫问题，我一开始忘记判断边界了，导致了一些错误，比如作为起始点，就不能向北、西和西北方向走。
于是我加入了这个代码，但是跑不了了。
无奈之下，我进行了改变，在原有矩阵外面套了一层不可通的边框。
变成
之后就可以运行了。
于是，我将代码进行了相应的改变，但是为何边框无法跑仍然是个谜题QAQ。
2、更改内容：由于我的皇后问题再找到一个解之后直接return了，所以无法输出全部的解，所以我进行了更改，加入了count计数，将return改为count++来输出全部的解。
3、同时，手算内容也重新写了，变得更加详细。
, 一、实验内容：
回溯法。
二、所用算法的基本思想及复杂度分析：
1、 着色问题
1） 基本思想
首先对一个点选一个颜色，然后对下一个点试另一个颜色，以此类推，如果重复填色，则换颜色。如果有点无论哪种颜色都有冲突，则回溯。
2） 手算图片
2、 批处理作业调度问题
1） 基本思想
对于第一个机器，不间断地工作。对于第二个机器，尽量不间断工作（每次工作都是在第一个机器结束或者上个作业结束后的最大时间后选择作业），选择第一个机器工作结束时间和第二个机器上一个工作结束时间最大的，加上下一个工作时间与最优时间进行对比，如果超过则回溯，否则继续。所有工作结束则更新最优时间，继续搜寻。
2） 手算图片
3、 n皇后问题
1） 基本思想
首先对于每一行，先从第一列开始放置，如果不行(竖线和对角有其他皇后)换下一个个位置，可以的话换下一行。如果有一行的皇后无法摆放就回溯。要是所有都试过了仍然有皇后没有摆放位置，则无解。
4、 迷宫问题
1） 基本思想
首先从起点出发，搜索8个方向，如果通且未访问过则继续，并标记已访问，如果不通已访问则试探下一个点，如果都不行则回溯。这里在外层全套上1，即加入不可通的边框。
三、源程序及注释：
1、 着色问题
2、 #include <iostream>
3、
4、 using namespace std;
5、
6、 bool arc[100][100]={0}; //存可达不可达
7、 int color[100] = {0}; //涂色
8、 int n = 5;
9、
10、 //判断颜色冲突
11、 int judge(int k){
12、 for(int i=0; i<k; ++i)
13、 if(arc[k][i]==1 && color[i]==color[k])
14、 return 0;
15、 return 1;
16、 }
17、
18、 void GraphColor(int m){
19、 //初始化颜色
20、 for(int i=0; i<n; ++i){
21、 color[i] = 0;
22、 }
23、 int k=0; //下标
24、 while(k>=0){
25、 color[k] += 1; //取色
26、 //判断，冲突就取别的颜色
27、 while(color[k]<=m){
28、 if(judge(k))
29、 break;
30、 else
31、 color[k] += 1;
32、 }
33、 //输出
34、 if(color[k]<=m && k==n-1){
35、 for(int i=0; i<n; ++i)
36、 cout<<color[i]<<" ";
37、 return;
38、 }
39、 //处理下个顶点
40、 if(color[k]<=m && k<n-1)
41、 k += 1;
42、 else
43、 color[k--] = 0; //回溯
44、 }
45、 }
46、
47、 int main()
48、 {
49、 //int n;
50、 cin>>n;
51、 int k1,k2;
52、 for(int i=0; i<n; ++i){
53、 cin>>k1>>k2;
54、 arc[k1][k2] = 1;
55、 arc[k2][k1] = 1;
56、 }
57、 GraphColor(3);
58、 return 0;
59、 }
60、 批处理作业调度问题
61、 #include <iostream>
62、
63、 using namespace std;
64、
65、 int batchJob(int a[], int b[], int n){
66、 int x[100],sum1[100],sum2[100]; //x作业编号，sum总时间
67、 //初始化
68、 int bestTime = 9999;
69、 for(int i=1; i<=n; ++i){
70、 x[i] = -1;
71、 sum1[i] = 0;
72、 sum2[i] = 0;
73、 }
74、 sum1[0] = 0;
75、 sum2[0] = 0;
76、 int k=1; //第k个作业
77、 while(k>=1){
78、 x[k]++;
79、 //安排第k个作业
80、 while(x[k]<n){
81、 //检查是否重复
82、 int i;
83、 for(i=1; i<k; ++i)
84、 if(x[i] == x[k])
85、 break;
86、 //处理
87、 if(i==k){
88、 sum1[k] = sum1[k-1] + a[x[k]];
89、 sum2[k] = sum1[k]>sum2[k-1]?sum1[k]+b[x[k]]:sum2[k-1]+b[x[k]];
90、 //判断是否超过最佳时间
91、 if(sum2[k]<bestTime)
92、 break;
93、 else
94、 x[k]++;
95、 }else
96、 x[k]++; //下一个作业
97、 }
98、 if(x[k]<n && k<n)
99、 k++; //下一个作业
100、 else{
101、 if(x[k]<n && k==n)
102、 if(bestTime > sum2[k]){
103、 bestTime = sum2[k];
104、 cout<<"当前最短作业安排：";
105、 for(int j=1; j<=n; ++j)
106、 cout<<x[j]+1<<" ";
107、 cout<<"当前最短时间："<<bestTime<<endl;
108、 }
109、 //回溯，查找下一个可能的最佳时间
110、 x[k] = -1;
111、 k--;
112、 }
113、 }
114、 return bestTime;
115、 }
116、
117、 int main()
118、 {
119、 int n;
120、 cin>>n;
121、 int a[100],b[100]; //存储处理时间
122、 for(int i=0; i<n; ++i){
123、 cin>>a[i]>>b[i];
124、 }
125、 cout<<batchJob(a,b,n)<<"为最短时间";
126、 return 0;
127、 }
128、 n皇后问题
129、 #include <iostream>
130、 #include <cmath>
131、 using namespace std;
132、
133、 int x[100]={0}; //第i个皇后摆放在第i行第i个位置
134、 int count = 0; //记录有几个解
135、
136、 //看皇后k放在x[k]会不会冲突
137、 bool judge(int k){
138、 for(int i=0; i<k; ++i)
139、 if(x[i]==x[k] || abs(i-k)==abs(x[i]-x[k]))
140、 return 1;
141、 return 0;
142、 }
143、
144、 void Queen(int n){
145、 for(int i=0; i<n; ++i)
146、 x[i] = -1;
147、 int k=0;
148、 while(k>=0){
149、 x[k]++; //在下一列放皇后k
150、 //冲突处理
151、 while(x[k]<n && judge(k)==1)
152、 x[k]++; //试探下一个位置
153、 //输出一个解
154、 if(x[k]<n && k==n-1){
155、 for(int i=0; i<n; ++i)
156、 cout<<x[i]+1<<" ";
157、 cout<<endl;
158、 count++;
159、 //return;
160、 }
161、 //有皇后未摆放
162、 else if(x[k]<n && k<n-1)
163、 k++; //准备摆放
164、 else
165、 x[k--] = -1; //回溯，重放皇后k
166、 }
167、 }
168、
169、 int main()
170、 {
171、 int n;
172、 cin>>n;
173、 Queen(n);
174、 cout<<"共"<<count<<"个解";
175、 return 0;
176、 }
177、 迷宫问题
178、 #include <iostream>
179、 using namespace std;
180、
181、 int xIn, yIn, xOut, yOut; //出入口坐标
182、 int xLength, yLength; //迷宫的行数和列数
183、 int maze[1000][1000]; //迷宫数组
184、 bool visited[1000][1000] = {0}; //访问标记数组
185、
186、 struct direction{
187、 int dx, dy;
188、 void setDirection(int dx,int dy){
189、 this->dx = dx;
190、 this->dy = dy;
191、 }
192、 }direction[8];
193、
194、 void initDirection(){
195、 direction[0].setDirection(0,1); //东
196、 direction[1].setDirection(1,1); //东南
197、 direction[2].setDirection(1,0); //南
198、 direction[3].setDirection(1,-1); //西南
199、 direction[4].setDirection(0,-1); //西
200、 direction[5].setDirection(-1,-1); //西北
201、 direction[6].setDirection(-1,0); //北
202、 direction[7].setDirection(-1,1); //东北
203、 }
204、
205、 //解决迷宫问题的递归算法
206、 bool seekPath(int x, int y){
207、 //从迷宫某一位置[i][j]开始，寻找出口[xOut][yOut]的一条路径,如果找到，则函数返回true
208、 int xtmp, ytmp; //记录位置信息
209、 if(x==xOut && y==yOut)
210、 return true;
211、 //循环遍历(x,y)的8个方向
212、 for(int i=0; i<8; i++) {
213、 xtmp = x+direction[i].dx;
214、 ytmp = y+direction[i].dy;
215、
216、 // if(xtmp<0 || xtmp>=yLength || ytmp<0 || ytmp>=xLength)
217、 // continue;
218、
219、 //找下一位置寻找通向出口的路径
220、 if(maze[xtmp][ytmp]==0 && visited[xtmp][ytmp]==0){ //如果通且未被访问过
221、 visited[xtmp][ytmp] = 1; //标记为已访问过
222、 if(seekPath(xtmp, ytmp)){ //递归试探
223、 printf("(%d,%d)\n",xtmp-1,ytmp-1);//逆向输出路径坐标
224、 return true;
225、 }
226、 }
227、 //回溯，换一个方向再试探通向出口的路径
228、 }
229、 return false; //找不到通向出口的路径
230、 }
231、
232、 int main(){
233、 initDirection(); //初始化方向
234、 cin>>xLength>>yLength;
235、 for(int i=0; i<=yLength+1; ++i){
236、 maze[0][i] = 1;
237、 maze[xLength+1][i] = 1;
238、 }
239、 for(int i=0; i<=xLength+1; ++i){
240、 maze[i][0] = 1;
241、 maze[i][yLength+1] = 1;
全套毕业设计论文现成成品资料请咨询