实验5 分支限界法实现
一、实验目标：
1. 熟悉分支限界法应用场景及实现的基本方法步骤； 2. 学会分支限界法的实现方法和分析方法：
二、实验内容
1. n后问题：
编程计算当n=1到8时解的个数，分别利用回溯法和分支限界法实现，比较并分析你的算法效率。 回溯法： 代码：
#include
using namespace std;
//法一：迭代回溯 class Queen { friend int nQueen(int); private: bool Place(int k); void Backtrack(int t); int n;//皇后个数 int *x;//当前解 int sum;//当前已找到的可行方案数 };
bool Queen::Place(int k)
{ for (int j = 1; j < k; j++) { if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k])) return false; } return true; }
void Queen::Backtrack(int t) { if (t > n) sum++; else for (int i = 1; i <= n; i++) { x[t] = i; if (Place(t)) Backtrack(t + 1); } }
int nQueen(int n) { Queen X; //初始化X X.n = n; 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; }
int main() { cout << \共有\种\ system(\ return 0; }
截图：
分支限界法： 代码：
#include
using namespace std; class Queen { friend int nQueen(int); private: bool Place(int k); void redu(int t); int n;//皇后个数 int *x;//当前解 int sum;//当前已找到的可行方案数 };
//剪枝函数
//判断当前状态是否合理，即皇后会不会互相攻击 bool Queen::Place(int k) { for (int j = 1; j < k; j++) { if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k])) return false; } //所有皇后都不会互相攻击 return true; }