山东和城乡建设厅网站,佳木斯做网站公司,公司网站重新备案,湘潭做网站找磐石网络一流一#xff0e;N皇后问题
基本原理和思路#xff1a; 从一条路往前走#xff0c;能进则进#xff0c;不能进则退回来#xff0c;换一条路再试。在包含问题的所有解的解空间树中#xff0c;按照深度优先搜索的策略#xff0c;从根结点出发深度探索解空间树。当探索到某一…一N皇后问题
基本原理和思路 从一条路往前走能进则进不能进则退回来换一条路再试。在包含问题的所有解的解空间树中按照深度优先搜索的策略从根结点出发深度探索解空间树。当探索到某一结点时要先判断该结点是否包含问题的解如果包含就从该结点出发继续探索下去如果该结点不包含问题的解则逐层向其祖先结点回溯。若用回溯法求问题的所有解时要回溯到根且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时只要搜索到问题的一个解就可以结束。
代码实现如下
#include iostream
#include cmath
using namespace std;
//皇后的个数,方案数目
int n,sum0;
//记录放置方案
int x[100];//不能这样定义int *x;
//用户递归求取方案
void Queen1(void);
void TraceBack(int);
void PrintMethod(void);
//检查这一皇后放置方案是否满足要求
int Place(int);int main()
{cout 输入皇后个数 endl;cinn;Queen1();return 0;
}void Queen1(void)
{TraceBack(0);
}
void TraceBack(int r)
{int i;if(rn){PrintMethod();//这个函数的正确性还没有得到验证sum;}else{for(i0;in;i){x[r]i;//在下一行判断当前路是不可行的之后进入同级的另外的路径if(Place(r))//先试探当前这条路是可行的则进入下一步循环TraceBack(r1);}}
}
void PrintMethod(void)
{int i,j;cout第sum个方案\n;for(i0;in;i){for(j0;jn;j){if(jx[i])cout1;elsecout0;}coutendl;}
}
int Place(int r)
{int i;for(i0;ir;i){if(x[r]x[i] || abs(r-i)abs(x[r]-x[i]))//在此处判断皇后走的下一步路是否可行如果不可行性return 0return 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 位置的哨兵时此位置及其上、下、左、右位置是否被监视。
代码实现如下
#includeiostream
#includefstream
#includequeueusing 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的pushpush会调用复制构造函数因此必须自定义一个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_queueNode 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)。
三 求解填字游戏问题
基本原理和思路从00开始向右搜索搜到30结束搜索时记录那些点被用过下一个点一定是没有被用过的点使用vis数组标记退出条件搜索到 x 3时即此时九个点都已经填了一遍值输出填入的九个值改点是否可以填入是否合法使用check函数来检查一下由于是从左向右开始填起所以相邻元素只需要考虑上和下两个方向check函数加上判断边界的条件即可。若该点合法则填入该点否则继续循环找一个可选点。判断边界即不能超出 3 * 3 的范围到了最右边要进行换行否则横坐标直接即可具体实现if(y 2) dfs(x 1, 0); else dfs(x, y 1);最后取消标记回溯上一个点找下一种选择情况。
代码实现如下
#include iostreamusing 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,j1) ) 然后为了减少空间不需要用二维数组来存储MaxSum(n,j)的值只需要求MaxSum(n,j)的时候存储下一行MaxSum(n1,j)的值就可以然后计算完第n行的MaxSum之后再覆盖原来的第n1行的MaxSum的值。
代码实现如下
#include iostream
#include cmath
#include cstdio
#include algorithmusing 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 *[N1];for(int i1; iN; i){a[i] new int[N1];}cout请输入图G的邻接矩阵:endl;for(int i1; iN; i){for(int j1; jN; j){cina[i][j];}coutendl;}cout图G的着色方案如下endl;cout当mM时图G的可行着色方案数目为mColoring(N,M,a)endl;for(int i1; iN; i){delete[] a[i];}delete []a;
}void Color::Backtrack(int t)
{if (tn){sum;for (int i1; in; i)cout x[i] ;cout endl;}else{for (int i1; im; i){x[t]i;if (Ok(t)) Backtrack(t1);x[t]0;}}
}bool Color::Ok(int k)// 检查颜色可用性
{for (int j1; jn; 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[n1];for(int i0; in; i){p[i] 0;}X.x p;X.Backtrack(1);delete []p;return X.sum;
}
分析时间复杂度是 O ( m ∗ n 2 ) O(m*n^2) O(m∗n2)。
