算法设计与分析实验报告

/*******约束、限界函数*************/ bool check(int i,int cc) {

if(a[x[i-1]][x[i]] != noedge && cc+a[x[i-1]][x[i]] < bestc) return true; else

return false; }

/*******功能函数*************/ bool traveling(int i;int cc) {

if(i>n) {}

else for(int j=i;j<=n;j++) {

swap(x[i],x[j]); if(check(i,cc)) {

cc+=a[x[i-1]][x[i]]; traveling(i+1,cc); cc-=a[x[i-1]][x[i]]; }

swap(x[i],x[j]); }

if(a[x[n][1]]!=noedge) {

for(int k=1;k<=n;k++) cout<

（6） 设计算法求解 n 后问题，并编程实现。（#include \ #include \ #include \ #include \ using namespace std; int n;//皇后个数 int *x;

int count=0; bool check(int i) {

for(int k=1;k

P129） {

if((x[k]==x[i])||fabs(x[k]-x[i])==fabs(k-i)) return false; else

return true; } }

void output(int i) {

cout<

int queue(int i) {

if(i>n) {

output(i); return 0; } else

for(int j=1;j<=n;j++) {

x[i]=j;

if(check(i)) { i++;

count++;

return queue(i+1); } } }

void main() {

cout<<\请输入皇后个数：\ cin>>n;

x=new int[n+1]; queue(1);

cout<<\可行方案有\种\ }

（7） 设计算法完成图的 m 着色问题，并编程实现。关键代码

#include \ #include \

P137） （ void main() {

getdata(); count=0; trycolor(1);

cout<

void trycolor(int i) {

if(i>n) output();

else for(int j=1;j<=m;j++) {

x[i] = j; if(check(i)) trycolor(i+1); } }

bool check(int i) {

for(int k=1;k<=i+1;i++)

if((a[k][i]) == 1 && (x[k] == x[i])) return false; return true; }

（8） 设计算法用 L 形覆盖一个正方块组成的正方形，要求不重不漏(若边长不刚 好，还需要挖掉 1 块)。

（9） 设计算法求解最佳调度问题，并编程实现。（P156，算法实现题 5-15）

（11） 设计算法求解无优先级运算问题，并编程实现。（P156，算法实现题 5-16） 注：至少选择其中 3 题完成。 3.主要仪器设备及软件 （1） PC 机

（2） TC、VC++、Java 等任一编程语言 实验六 分支限界法及其应用

（ 验证型、设计型实验 4 学时） 1.目的要求

（1） 理解分支限界法的基本思想和剪枝搜索策略；

（2） 掌握设计分支限界法的基本技巧和实际问题的分析求解。 2.实验内容：

（1） 编程实现 0/1 背包问题的队列式/优先队列式分支限界算法；

（2） 编程实现队列式/优先队列式分支限界算法求解旅行商问题的求解。 #include template class Traveling{

friend void main(void); public:

Type BBTSP(int v[]); private:

int n; //图 G 的顶点数

Type **a, //图 G 的邻接矩阵 NoEdge, //图 G 的无边标志 cc, //当前费用

bestc; //当前最小费用 };

template class MinHeapNode{ friend Traveling; public:

operator Type()const {return lcost;} private:

Type lcost, //子树费用的下界 cc, //当前费用

rcost, //x[s:n-1]中顶点最小出边费用和 int s, //根结点到当前结点的路径为 x[0:s] *x; //需要进一步搜索的顶点是 x[s+1:n-1] }

template

Type Traveling::BBTSP(int v[])

{ //旅行收货商问题的优先队列式分支限界法 //定义最小堆的容量为 1000

MinHeap>H(1000); Type *MinOut = new Type[n+1];

//计算 MinOut[i] = 顶点 i 的最小出边费用 Type MinSum = 0;//最小出边费用和 for(int i=1;i<=n;i++){ Type Min = NoEdge; for(int j=1;j<=n;j++)

if(a[i][j]!=NoEdge && (a[i][j]

return NoEdge;//无回路 MinOut[i] = Min; MinSum += Min; }

//初始化

MinHeapNodeE; E.x = new int[n];