没有合适的资源?快使用搜索试试~ 我知道了~
算法之分支限界法实现.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 152 浏览量
2021-10-02
11:40:29
上传
评论
收藏 149KB DOC 举报
温馨提示
试读
17页
算法之分支限界法实现.doc
资源推荐
资源详情
资源评论
.
.
实验 5 分支限界法实现
一、实验目标:
1.熟悉分支限界法应用场景及实现的根本方法步骤;
2.学会分支限界法的实现方法和分析方法:
二、实验内容
1. n 后问题:
编程计算当 n=1 到 8 时解的个数,分别利用回溯法和分支限界法实现,比拟并
分析你的算法效率。
回溯法:
代码:
#include<iostream>
#include<cmath>
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]))
. .word.zl.
.
.
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 << "共有" << nQueen(8) << "种" << endl;
system("pause");
return 0;
}
截图:
. .word.zl.
.
.
分支限界法:
代码:
#include<iostream>
#include<cmath>
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;
}
int nQueen(int n)
{
Queen X;
//初始化X
. .word.zl.
.
.
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.redu(1);
delete[]p;
return X.sum;
}
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
void Queen::redu(int t)
{
if (t > n)
sum++;
else
for (int i = 1; i <= n; i++)
{
x[t] = i;
if (Place(t))
redu(t + 1);
}
}
int main()
{
cout << "共有" << nQueen(8) << "种" << endl;
system("pause");
return 0;
}
截图:
. .word.zl.
剩余16页未读,继续阅读
资源评论
gjmm89
- 粉丝: 14
- 资源: 19万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功