算法设计与分析实验报告c++实现(N皇后问题、卫兵布置问题、求解填字游戏问题、图的m着色问题)

一．N皇后问题

基本原理和思路：
从一条路往前走，能进则进，不能进则退回来，换一条路再试。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

代码实现如下：

#include <iostream>
#include <cmath>
using namespace std;
//皇后的个数,方案数目
int n,sum=0;
//记录放置方案
int x[100];//不能这样定义int *x;
//用户递归求取方案
void Queen1(void);
void TraceBack(int);
void PrintMethod(void);
//检查这一皇后放置方案是否满足要求
int Place(int);int main()
{cout << "输入皇后个数：" << endl;cin>>n;Queen1();return 0;
}void Queen1(void)
{TraceBack(0);
}
void TraceBack(int r)
{int i;if(r>=n){PrintMethod();//这个函数的正确性还没有得到验证sum++;}else{for(i=0;i<n;i++){x[r]=i;//在下一行判断当前路是不可行的之后，进入同级的另外的路径if(Place(r))//先试探当前这条路是可行的，则进入下一步循环TraceBack(r+1);}}
}
void PrintMethod(void)
{int i,j;cout<<"第"<<sum<<"个方案\n";for(i=0;i<n;i++){for(j=0;j<n;j++){if(j==x[i])cout<<"1";elsecout<<"0";}cout<<endl;}
}
int Place(int r)
{int i;for(i=0;i<r;i++){if(x[r]==x[i] || abs(r-i)==abs(x[r]-x[i]))//在此处判断皇后走的下一步路是否可行，如果不可行性，return 0；return 0;}return 1;
}

分析：时间复杂度为O(n^n)

二．卫兵步列问题

基本原理和思路：初始令所有的 X [i, j]= 1， i =1,2, …… m ， j =1,2, ……n . 算法从 （1,1 ）开始直到 （m,n）为止， 搜索树是二叉树，有 m x n 层 . 每个结点对应一个陈列室位置，如果令 X [i, j]= 0 ，取消（i,j ） 位置的哨兵，进入左子树；否则进入右子树。在进入左子树时需要检查房间被监视的情况。 即当取消（ i,j ）位置的哨兵时，此位置及其上、下、左、右位置是否被监视。

代码实现如下：

#include<iostream>
#include<fstream>
#include<queue>using namespace std;
class Solve;class Node   //Node节点，用来存放搜索树的节点
{friend class Solve;
private:int i;    //当前要放置的新位置 横坐标：i 纵坐标：jint j;int robotNums;    //当前节点已经放置的哨兵数目int beenMonitored;   //当前已经被监视的房间数int** x;    //当前放置哨兵的地方   0表示没有，1表示放置了int** y;    //当前已经被监视的地方   0表示没有，1表示已经监视了int m;      //行int n;      //列public:Node();   //构造函数Node(int m, int n);   //构造函数,m、n是行列数Node(const Node& a);  //这个函数是用于heap的push，push会调用复制构造函数，因此必须自定义一个friend bool operator<(const Node& a, const Node& b);   //重载<，用于优先队列的使用Node& operator=(const Node& a)   //赋值运算符，懒得换位置了{if (x || y){for (int i = 0; i < m + 2; ++i){if (x){delete[] x[i];}if (y){delete[] y[i];}}delete[] x;delete[] y;x = NULL;y = NULL;}i = a.i;j = a.j;robotNums = a.robotNums;beenMonitored = a.beenMonitored;m = a.m;n = a.n;x = new int* [m + 2];y = new int* [m + 2];for (int i = 0; i < m + 2; ++i){x[i] = new int[n + 2];y[i] = new int[n + 2];for (int j = 0; j < n + 2; ++j){x[i][j] = a.x[i][j];y[i][j] = a.y[i][j];}}return *this;}~Node();   //用到了new，因此析构函数要重载，避免内存泄露};class Solve     //解决问题的类
{
private:priority_queue<Node> heap;    //优先队列heapint ans;     //答案所需要的哨兵数目int m;       //行列数int n;int** result;  //答案哨兵的排列顺序public:Solve();Solve(int m, int n);void run(ofstream& fcout);    //进行整个计算+输出void get_min();               //运用分支限界法，寻找最小值void print(ofstream& fcout);  //打印哨兵位置和数目void copy(int** x, int** y);  //将一个二维数组赋值给另一个void change(Node& tmp, int i, int j);   //生成子节点，同时将其添加到heap中
};int main()
{ifstream fcin;fcin.open("input.txt");if (!fcin.is_open()){cout << "文件 input.txt 未能打开" << endl;return -1;}int m, n;fcin >> m >> n;fcin.close();Solve solve(m, n);ofstream fcout;fcout.open("output.txt");if (!fcout.is_open()){cout << "文件 output.txt 未能打开" << endl;return -1;}solve.run(fcout);fcout.close();return 0;
}

分析：复杂度 W(n,m)=O(nm2)。

三． 求解填字游戏问题

1. 基本原理和思路：从（0，0）开始向右搜索，搜到（3，0）结束
2. 搜索时记录那些点被用过，下一个点一定是没有被用过的点，使用vis数组标记
3. 退出条件：搜索到 x == 3时，即此时九个点都已经填了一遍值，输出填入的九个值
4. 改点是否可以填入，是否合法：使用check函数来检查一下，由于是从左向右开始填起，所以相邻元素只需要考虑上和下两个方向，check函数加上判断边界的条件即可。
5. 若该点合法，则填入该点，否则继续循环找一个可选点。
6. 判断边界：即不能超出 3 * 3 的范围，到了最右边要进行换行，否则横坐标直接++即可！具体实现：if(y == 2) dfs(x + 1, 0); else dfs(x, y + 1);
7. 最后取消标记，回溯上一个点，找下一种选择情况。

代码实现如下：

#include <iostream>using namespace std;int a[3][3], count;
bool vis[10];bool isprime(int n)
{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;
}bool check(int x, int y, int k)
{// 上 if(x - 1 >= 0 && !isprime(a[x - 1][y] + k)) return false;// 左 if(y - 1 >= 0 && !isprime(a[x][y - 1] + k)) return false;return true;
}void dfs(int x, int y)
{if(x == 3){for(int i = 0; i < 3; i++){for(int j = 0; j < 3; j++){cout << a[i][j] << " ";}cout << endl;}cout << endl;count ++;return;}for(int i = 1; i <= 10; i++){if(!vis[i] && check(x, y, i)){a[x][y] = i; vis[i] = true;if(y == 2) dfs(x + 1, 0);else dfs(x, y + 1);a[x][y] = 0; vis[i] = false;}}
}int main()
{dfs(0, 0);cout << "Total: " << count << endl;return 0;
}

分析：采用回溯法，即求全排列，时间复杂度O(n!)

四．求解图的m着色问题

基本原理和思路：MaxSum(i,j)：从第i行j列到底边的最大数字之和
从最后一行开始递推，MaxSum(n,j)=D(n,j)//n行j列，MaxSum(n-1,j) = D(n-1,j) + max( MaxSum(n,j) , MaxSum(n,j+1) )
然后为了减少空间，不需要用二维数组来存储MaxSum(n,j)的值，只需要求MaxSum(n,j)的时候存储下一行MaxSum(n+1,j)的值就可以，然后计算完第n行的MaxSum之后再覆盖原来的第n+1行的MaxSum的值。

代码实现如下：

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 5;//图的顶点数
const int M = 3;//色彩数
class Color
{friend int mColoring(int, int, int **);
private:bool Ok(int k);void Backtrack(int t);int n,      //图的顶点数m,      //可用的颜色数**a,    //图的邻接矩阵*x;     //当前解long sum;   //当前已找到的可m着色方案数
};
int mColoring(int n,int m,int **a);
int main()
{int **a = new int *[N+1];for(int i=1; i<=N; i++){a[i] = new int[N+1];}cout<<"请输入图G的邻接矩阵:"<<endl;for(int i=1; i<=N; i++){for(int j=1; j<=N; j++){cin>>a[i][j];}cout<<endl;}cout<<"图G的着色方案如下："<<endl;cout<<"当m="<<M<<"时，图G的可行着色方案数目为："<<mColoring(N,M,a)<<endl;for(int i=1; i<=N; i++){delete[] a[i];}delete []a;
}void Color::Backtrack(int t)
{if (t>n){sum++;for (int i=1; i<=n; i++)cout << x[i] << " ";cout << endl;}else{for (int i=1; i<=m; i++){x[t]=i;if (Ok(t)) Backtrack(t+1);x[t]=0;}}
}bool Color::Ok(int k)// 检查颜色可用性
{for (int j=1; j<=n; j++){if ((a[k][j]==1)&&(x[j]==x[k])) //相邻且颜色相同{return false;}}return true;
}int mColoring(int n,int m,int **a)
{Color X;//初始化XX.n = n;X.m = m;X.a = a;X.sum = 0;int *p = new int[n+1];for(int i=0; i<=n; i++){p[i] = 0;}X.x = p;X.Backtrack(1);delete []p;return X.sum;
}

分析：时间复杂度是$O(m\ast n^2)$。