算法分析与设计实验报告

算法分析与设计实验报告⼀．实验⽬的

1掌握回溯法解题的基本思想以及算法设计⽅法;

2.掌握动态规则法和分⽀限界法的基本思想和算法设计⽅法；3掌握深度优先遍历法的基本思想及运⽤；

4．进⼀步的对N皇后问题，⼦集和数问题，0-1背包问题做深⼊的了解。⼆．实验内容1.实现求n 皇后问题和⼦集和数问题的回溯算法 。2.⽤动态规划的⽅法实现0/1背包问题。3.⽤分⽀限界法实现0/1背包问题。

4.⽤深度优化的⽅法遍历⼀个图，并判断图中是否有回路存在，如果有，请输出回路。三． 实验设计1． N 皇后问题：

我是采取了尊循 top-down design 的顺序来设计整个算法和程序。 采 ⽤ OOP 的思 想 ， 先假 设 存 在 ⼀个 · 表 ⽰棋盘 格 局的类 queens ， 则定 义 回 溯 函数 solve_from(queens configuration)，configuration 表⽰当前棋盘格局，算法不断扩展棋盘的当 前格局（找到下⼀个⾮冲突位置） ，当找到⼀个解决⽅案时打印该⽅案。该递归函数采⽤回 溯法求出所有解。main 函数调⽤ solve_from 时传递的实参是⼀个空棋盘。 对于模拟棋盘的 queens 类，我们可以定义三个数据成员： 1.size ：棋盘的边长，即⼤⼩ .2. count ：已放置的互不冲突的皇后数 3.array[][]：布尔矩阵，true 表⽰当前格有皇后 这⾥需要稍加思考以便稍后可以简化程序：因为每⾏只能放⼀个皇后，从上到下，从左到右 放，那么 count 个皇后占⽤的⾏为 0——count －1。所以count 还表⽰下⼀个皇后应该添加 在哪⼀⾏。 这样， 和 remove 操作的⼊⼝参数就只需要提供列号就⾏了， add 降低了耦合度 ： ）

下⾯是程序运⾏结果：

2． ⼦集和数问题：

本设计利⽤⼤⼩固定的元组来研究回溯算法，在此情况下，解向量的元素X （i ）取1或0值，它表⽰是否包含了权数W （i ）.⽣成图中任⼀结点的⼉⼦是很容易的。对于i 级上的⼀个结点，其左⼉⼦对应于X （i ）=1，右⼉⼦对应于X(i)=0。对于限界函数的⼀

种简单选择是，当且仅当∑∑+==≥+n

k i k i M i W i X i W 11)()()(时，B(X(1),···，X （k ）)=true。

显然，如果这个条件不满⾜，X(1),···，X （k ）就不能导致⼀个答案结点。如果假定这些W （i ）⼀开始就是按⾮降次序列排列的，那么这些限界函数可以被强化。在这种情况下，如果M k W i X i W ki >++∑=)1()()(1

,则X(1),···，X （k ）就不能导致⼀个答案结点。因此，将要使⽤的限界函数是B

k （X （1），···，X （k ））=true,当且仅当M

i W i X i W n k i k i =+∑∑+==11)()()(。下⾯是运⾏结果

3． 动态规则法解0-1背包问题：

在0 / 1背包问题中，需对容量为c 的背包进⾏装载。从n 个物品中选取装⼊背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可⾏的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装⼊的物品价值最⾼，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n ，x 取0或1，取1表⽰选取物品i) 取得最⼤值。

在该问题中需要决定x1 .. xn 的值。假设按i = 1，2，...，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品(即物品2，3，.，n)，背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最⼤背包容量为c-w1 的问题。现设r?{c ，c-w1 } 为剩余的背包容量。

在第⼀次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，[x2 ，.，xn ] 必须是第⼀次决策之后的⼀个最优⽅案，如果不是，则会有⼀个更好的⽅案[y2，.，yn ]，因⽽[x1，y2，.，yn ]是⼀个更好的⽅案。下⾯是程序运⾏结果：

4．分⽀限界法解0-1背包问题：

在解0-1背包问题的优先队列式分⽀限界法中，活结点优先队列中结点元素N的优先级由该结点的上界函数Bound计算出的值uprofit给出。⼦集树中以结点N为根的⼦树中任⼀结点的价值不超过N.profit。可⽤⼀个最⼤堆来实现活结点优先队列。堆中元素类型为HeapNode，其私有成员有uprofit,profit,weight和level。对于任意活结点N，N.weight是结点N所相应的重量；N.profit是N所相应的价值；N.uprofit是结点N的价值上界，最⼤堆以这个值作为优先级。⼦集空间树中结点类型为bbnode。

下⾯是程序运⾏结果：

5．⽤深度优化的⽅法遍历⼀个图：

假设给定图G的初态是所有顶点均未曾访问过。在G中任选⼀顶点v为初始出发点(源点)，则深度优先遍历可定义如下：⾸先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进⾏深度优先遍历，直⾄图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为⽌。若此时图中仍有未访问的顶点，则另选⼀个尚未访问的顶点作为新的源点重复上述过程，直⾄图中所有顶点均已被访问为⽌。下⾯是程序运⾏结果：

四．实验分析与⼩结

本次实验让我更加深⼊地了解了回溯法，动态规则法，分⽀限界法，图的深度优先遍历这4种算法以及实际运⽤，也扫除了以前存在的⼀些疑惑，在⾃⼰努⼒后获得了能⼒上的提升很欣慰！也很感谢⽼师安排的这次实验，在实验的过程中，也发现了⾃⼰的⼀些不⾜之处，第五个算法，对图的遍历还没有把握的很好，因⽽有些纰漏，我会更加努⼒的学习，来提⾼我的编程⽔平的！五．程序代码1．#include

const int n = 8; //8皇后问题.改动n可变成N皇后问题const int n_sub = n - 1 ;

int queen[n] ; //N个棋⼦.N对应每⼀列,如n=0的棋⼦只下在0列,1下1....类推bool row[n] ; //棋局的每⼀⾏是否有棋,有则为1,⽆为0 ;bool passive[2*n-1] ; //斜率为1的斜线⽅向上是不是有皇后

bool negative[2*n-1] ; //斜率为负1的斜线⽅向上是不是有皇后.//之所以⽤全局变量,因全局数组元素值⾃动为0int main(){

int cur = 0 ;//游标,当前移动的棋⼦(哪⼀列的棋⼦)bool flag = false ; //当前棋⼦位置是否合法

queen[0] = -1 ; //第0列棋⼦准备,因⼀开始移动的就是第0列棋⼦int count = 0 ; //⼀共有多少种下法;

cout<<\"============================Starting=============================\"=0){

while(cur>=0 && queen[cur]{

queen[cur]++ ;// cout<<\"第\"if(queen[cur] >= n) { //如果当前列已经下完(找不到合法位置)

// cout<<\"当前⾏是⾮法⾏,当前列棋⼦⾛完,没有合法位置,回溯上⼀列棋⼦\"queen[cur] = -1 ; //当前列棋⼦置于准备状态cur-- ; //回溯到上⼀列的棋⼦if(cur>=0) {

row[queen[cur]] = false ;

passive[queen[cur] + cur] = false ;negative[n_sub + cur - queen[cur]] = false ;}

//由于要移下⼀步,所以回溯棋⼦原位置所在⾏应该没有棋⼦啦.置row[]为false//并且棋⼦对应的斜线的标志位passive[cur]和negative[cur]也应该要设为false ;}else {

//先判断棋⼦所在⾏没有棋⼦

if(row[queen[cur]] == false) { //当前⾏没有棋⼦// cout<<\"棋⼦\"<

flag = true ; // 暂设为true,或与之前棋⼦斜交,则再设为false ;//以下检查当前棋⼦是否与之前的棋⼦斜线相交

if( passive[queen[cur] + cur] == true || negative[n_sub + cur - queen[cur]] == true) {flag = false ;

// cout<<\"出现斜线相交,该位置不合法\"<}elseflag = true ;

if(flag) { //没有斜交,位置合法

// cout<<\"斜线也没有相交,该位置合法\"// cout<<\"棋⼦⾛完⼀轮,总⾛法加1\"row[queen[cur]] = true ;// 当前⾏设为有棋⼦

passive[queen[cur] + cur] = true ;//当前⾏正斜率⽅向有棋⼦

negative[n_sub + cur - queen[cur]] = true ; //当前⾏负斜率⽅向上也有棋⼦cur++ ;if(cur >= n) {cur-- ;

row[queen[cur]] = false ;

passive[queen[cur] + cur] = false ;

negative[n_sub + cur - queen[cur]] = false ;//原理同回溯}flag = false ;}}}//else}}cout2．#include#define M 31

#define N 4 //集合元素个数int w[N]={11,13,24,7};int x[N];

void Subset(int s,int k) //解⼦集和数问题函数{

int i,l;l=0; x[l]=k;while(l>=0){

while(s+w[x[l]-1]{

s=s+w[x[l]-1];k++;l++;x[l]=k;}

while(s+w[x[l]-1]>M&&k<=N){

k++;x[l]=k;}

if(s+w[x[l]-1]==M){ k++;

for(i=0;i<=l;i++)

printf(\" %d\输出变长解向量printf(\"\\n\");}

while(k>N) //返回上⼀个节点，实现回溯的主要思想 {l--;k=x[l];x[l]=k+1;s=0;for(i=0;i{

s=s+w[x[i]-1];}}}}

void main(){

Subset(0,1);//调⽤subset(int s,int k)函数}3．

#include#include

using namespace std;//w[]为n个物体的重量//p[]为n个物体的价值//m为背包的载重量//x[]为背包是否被选中//n为背包的数量

int beibao(int w[],int p[],int m, bool x[],int n){int i,j;int **optp;

optp=new int*[n+1];for(i=0;i<=n;i++)optp[i]=new int[m+1];for(i=0;i<=n;i++){optp[0][i]=0;optp[i][0]=0;x[i]=false;}

for(i=1;i<=n;i++)for(j=1;j<=m;j++){

optp[i][j]=optp[i-1][j];if(j>=w[i]&&optp[i-1][j]j=m;for(i=n;i>0;i--){

if(optp[i][j]>optp[i-1][j]){x[i]=true;j-=w[i];}}

return optp[n][m];

}int main(){

int w[6]={0,2,2,6,5,4};int p[6]={0,6,3,5,4,6};int m=10;int n=5;bool x[6];

int z=beibao(w,p,m,x,n);cout4．#include#include

#define MAXNUM 100struct node{int step;double price;double weight;double max, min;unsigned long po;};

typedef struct node DataType;

struct SeqQueue { /* 顺序队列类型定义 */int f, r;

DataType q[MAXNUM];};

typedef struct SeqQueue *PSeqQueue;PSeqQueue createEmptyQueue_seq( void ) {PSeqQueue paqu;

paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue)); if (paqu == NULL)printf(\"Out of space!! \\n\");else

paqu->f = paqu->r = 0;return paqu;}

int isEmptyQueue_seq( PSeqQueue paqu ) {return paqu->f == paqu->r;}

/* 在队列中插⼊⼀元素x */

void enQueue_seq( PSeqQueue paqu, DataType x ) {if( (paqu->r + 1) % MAXNUM == paqu->f )printf( \"Full queue.\\n\" );else {

paqu->q[paqu->r] = x;

paqu->r = (paqu->r + 1) % MAXNUM;}}

/* 删除队列头元素 */

void deQueue_seq( PSeqQueue paqu ) {if( paqu->f == paqu->r )printf( \"Empty Queue.\\n\" );else

paqu->f = (paqu->f + 1) % MAXNUM;}

/* 对⾮空队列,求队列头部元素 */

DataType frontQueue_seq( PSeqQueue paqu ) {return (paqu->q[paqu->f]);}

/* 物品按性价⽐从新排序*/

void sort(int n, double p[], double w[]){int i, j;

for (i = 0; i < n-1; i++)for (j = i; j < n-1; j++) {double a = p[j]/w[j];

double b = p[j+1]/w[j+1];if (a < b) {

double temp = p[j];p[j] = p[j+1];p[j+1] = temp;temp = w[j];w[j] = w[j+1];w[j+1] = temp;}}}

/* 求最⼤可能值*/

double up(int k, double m, int n, double p[], double w[]){ int i = k;double s = 0;

while (i < n && w[i] < m) {m -= w[i];s += p[i];i++;}

if (i < n && m > 0) {s += p[i] * m / w[i];i++;}return s;}

/* 求最⼩可能值*/

double down(int k, double m, int n, double p[], double w[]){ int i = k;double s = 0;

while (i < n && w[i] <= m) {m -= w[i];s += p[i];i++;}return s;}

/* ⽤队列实现分⽀定界算法*/

double solve(double m, int n, double p[], double w[], unsigned long* po){ double min;PSeqQueue q = createEmptyQueue_seq();DataType x = {0,0,0,0,0,0};sort(n, p, w);

x.max = up(0, m, n, p, w);x.min = min = down(0, m, n, p, w);if (min == 0) return -1;enQueue_seq(q, x);

while (!isEmptyQueue_seq(q)){int step;DataType y;

x = frontQueue_seq(q);deQueue_seq(q);if (x.max < min) continue;step = x.step + 1;if (step == n+1) continue;

y.max = x.price + up(step, m - x.weight, n, p, w);if (y.max >= min) {

y.min = x.price + down(step, m-x.weight, n, p, w);y.price = x.price;y.weight = x.weight;y.step = step;y.po = x.po << 1;if (y.min >= min) {min = y.min;

if (step == n) *po = y.po;}

enQueue_seq(q, y);}

if (x.weight + w[step-1] <= m) {y.max = x.price + p[step-1] +

up(step, m-x.weight-w[step-1], n, p, w);if (y.max >= min) {

y.min = x.price + p[step-1] +

down(step, m-x.weight-w[step-1], n, p, w);y.price = x.price + p[step-1];y.weight = x.weight + w[step-1];y.step = step;y.po = (x.po << 1) + 1;if (y.min >= min) {min = y.min;

if (step == n) *po = y.po;}

enQueue_seq(q, y);}}}

return min;}

#define n 4double m = 15;

double p[n] = {10, 10, 12, 18};double w[n] = {2, 4, 6, 9};int main() {int i;double d;unsigned long po;d = solve(m, n, p, w, &po);if (d == -1)

printf(\"No solution!\\n\");else {

for (i = 0; i < n; i++)

printf(\"x%d is %d\\n\}getchar();return 0;}5．#include

#include

struct node /* 图顶点结构定义 */{

int vertex; /* 顶点数据信息 */

struct node *nextnode; /* 指下⼀顶点的指标 */};

typedef struct node *graph; /* 图形的结构新型态 */ struct node head[9]; /* 图形顶点数组 */int visited[9]; /* 遍历标记数组 *//*根据已有的信息建⽴邻接表*/

void creategraph(int node[20][2],int num)/*num指的是图的边数*/ {graph newnode; /*指向新节点的指针定义*/graph ptr;

int from; /* 边的起点 */int to; /* 边的终点 */int i;

for ( i = 0; i < num; i++ ) /* 读取边线信息，插⼊邻接表*/ {from = node[i][0]; /* 边线的起点 */ to = node[i][1]; /* 边线的终点 *//* 建⽴新顶点 */

newnode = ( graph ) malloc(sizeof(struct node));newnode->vertex = to; /* 建⽴顶点内容 */newnode->nextnode = NULL; /* 设定指标初值 */ptr = &(head[from]); /* 顶点位置 */

while ( ptr->nextnode != NULL ) /* 遍历⾄链表尾 */ptr = ptr->nextnode; /* 下⼀个顶点 */ptr->nextnode = newnode; /* 插⼊节点 */}}

/* 图的深度优先搜寻法 */void dfs(int current){graph ptr;

visited[current] = 1; /* 记录已遍历过 */

printf(\"vertex[%d]\\n\输出遍历顶点值 */ ptr = head[current].nextnode; /* 顶点位置 */while ( ptr != NULL ) /* 遍历⾄链表尾 */{

if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */dfs(ptr->vertex); /* 递回遍历呼叫 */ptr = ptr->nextnode; /* 下⼀个顶点 */}}int main(){

graph ptr; /* 边线数组 */int node[20][2] = { {1, 2}, {2, 1},{1, 3}, {3, 1},{1, 4}, {4, 1},{2, 5}, {5, 2},{2, 6}, {6, 2},{3, 7}, {7, 3},{4, 7}, {4, 4},{5, 8}, {8, 5},{6, 7}, {7, 6},{7, 8}, {8, 7} };int i;

for ( i = 1; i <= 8; i++ ) /* 顶点数组初始化 */ {

head[i].vertex = i; /* 设定顶点值 */ head[i].nextnode = NULL; /* 指针为空 */ visited[i] = 0; /* 设定遍历初始标志 */ }creategraph(node,20); /* 建⽴邻接表 */ printf(\"Content of the gragh's ADlist is:\\n\");for ( i = 1; i <= 8; i++ ){

printf(\"vertex%d ->\顶点值 */ ptr = head[i].nextnode; /* 顶点位置 */ while ( ptr != NULL ) /* 遍历⾄链表尾 */ {printf(\" %d \印出顶点内容 */ ptr = ptr->nextnode; /* 下⼀个顶点 */ }printf(\"\\n\"); /* 换⾏ */ }

printf(\"\\nThe end of the dfs are:\\n\");

dfs(1); /* 打印输出遍历过程 */ printf(\"\\n\"); /* 换⾏ */system(\"pause\");return 0;}