实验十-1：图着色问题

一、实验目的与要求 

给定无向连通图G=（V,E），图着色问题求最小的整数m，用m种颜色对图G的顶点着色，使得任意两个相邻顶点着色不同。

二、实验环境

DEV C++

三、实验步骤与分析

回溯法在解空间树的搜集过程如图所示，搜索过程下：

图3-1 回溯法求解图着色问题示例

算法分析：

程序如下：

void GraphColor(int m){int i,j,n;for(i=0;i<n;i++)color[i]=0;for(i=0;i>=0; ) //为顶点i着色  {color[i]=color[i]+1;//取下一种颜色while(color[i]<=m&&Ok(i)==1)color[i]=color[i]+1;//搜索下一个颜色if(color[i]>m) color[i--]=0;//回溯else if(i<n-1) i=i+1;//处理下一个顶点else{for(j=0;j<n;j++)cout<<color[j]<<" ";return;}     }}int Ok(int i){for(int j=0;j<i;j++)if(arc[i][j]==1&&color[i]==color[j])return 1;return 0;//着色发生冲突返回1}

运行结果：

• 实验小结

这个问题和八皇后还有求子集和等问题都具有类似之处，其核心在通过遍历找到所有的问题子集 ，但是在递归遍历的时候，都在加一个判断，将那些明显不满足条件的情况给直接排出，减少问题的规模，其实这类问题，在递归遍历的时候都是类似与对一颗树的便利每个节点相当走到此时的状态，然后再判断此时的状态是否能继续走下去，如果不能就将其回溯到上一个节点，避免浪费时间。

实验十-2：0/1背包问题

• 实验目的与要求 

设计回溯算法求解0/1背包问题；设计测试数据，统计搜索过程中经过的节点

二、实验环境

DEVC++

三、实验步骤与分析

// n=5, c=10, w={2, 2, 6, 5, 4}, v={6, 3, 5, 4, 6}的0-1背包问题的最优解和最优值。#include <iostream>using namespace std;#define N 10int w[N];//重量int v[N];//价值int x[N];//1表放入背包，0表不放入int n,c;//n：物品个数 c：背包的最大容量int cw=0;//当前物品总重int cv=0;//当前物品总价值int bestp=0;//当前最大价值int bestx[N];//最优解//回溯函数 k表示当前处在第几层做选择，k=1时表示决定是否将第一个物品放入背包void backtrack(int k){//叶子节点，输出结果if(k>n){//找到一个更优的解if(cv>bestp){//保存更优的值和解bestp = cv;for(int i=1; i<=n; i++)bestx[i] = x[i];}}else{//遍历当前节点的子节点for(int i=0; i<=1; i++){x[k]=i;if(i==0){backtrack(k+1);}else{//约束条件：当前物品是否放的下if((cw+w[k])<=c){cw += w[k];cv += v[k];backtrack(k+1);cw -= w[k];cv -= v[k];}}}}}int main(){cout<<"请输入物品的个数：";cin>>n;cout<<"请输入每个物品的重量及价值:"<<endl;for(int i=1;i<=n;i++){cin>>w[i]>>v[i];}cout<<"请输入背包的限制容量：";cin>>c;backtrack(1);cout<<"最优值是:"<<bestp<<endl;cout<<"(";for(int i=1;i<=n;i++)cout<<bestx[i]<<" ";cout<<")";return 0;

运行结果：

四、实验小结

用回溯法解决01背包问题，这实际是一个子集树问题：首先对于背包中的物品按照单位重量价值进行排序，方便于后面子树的剪枝操作。对于背包中的每一个物品，可以选择放入（左子树）或者不放入（右子树）。依次对每个节点进行搜索，得到最优解。