算法之分支限界法实现

实验5 分支限界法实现

一、实验目标：

1. 熟悉分支限界法应用场景及实现的基本方法步骤； 2. 学会分支限界法的实现方法和分析方法：

二、实验内容

1. n后问题：

编程计算当n=1到8时解的个数，分别利用回溯法和分支限界法实现，比较并分析你的算法效率。 回溯法： 代码：

#include #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 #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; }