实验十 图着色问题

article/2024/7/17 2:57:07

《算法设计与分析》实验报告       

  

所在院系

计算机与信息工程学院

学生学号

学生姓名

年级专业

2020级计算机科学与技术

授课教师

彭绪富

学         期

2022-2023学年第一学期

提交时间

2022年11月16日

目录

实验十-1:图着色问题

一、实验目的与要求

二、实验环境

三、实验步骤与分析

四、 实验小结

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

一、 实验目的与要求

二、实验环境

三、实验步骤与分析

四、实验小结

实验十-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背包问题,这实际是一个子集树问题:首先对于背包中的物品按照单位重量价值进行排序,方便于后面子树的剪枝操作。对于背包中的每一个物品,可以选择放入(左子树)或者不放入(右子树)。依次对每个节点进行搜索,得到最优解。


http://www.ngui.cc/article/show-1007577.html

相关文章

蓝桥杯刷题冲刺 | 倒计时14天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.最长递增2.走迷宫3.解立方根4.回文特判5.修改数组1.最长递增 题目 链接&#xff1a; 最长递增…

pip安装及国内源更换

# pip安装 python3&#xff1a; curl https://bootstrap.pypa.io/get-pip.py -o get-pip.py python3 get-pip.py python2: curl https://bootstrap.pypa.io/pip/2.7/get-pip.py -o get-pip2.py python2 get-pip2.py # pip国内的一些镜像 阿里云 http://mirrors.aliyu…

vue2 和vue3动态绑定src

vue2&#xff1a; webpack 创建的vue2可以通过 require对图片进行动态绑定 <script> export default{data(){return{list:[{id:1,img:require("./assets/logo.png")},{id:2,img:require("./assets/logo.png")},{id:3,img:require("./assets/l…

java并发-通信工具类

文章目录1 Semaphore1.2 Semaphore简介1.2 Semaphore案例1.3 Semaphore原理2 Exchanger3 CountDownLatch3.1 CountDownLatch简介3.2 CountDownLatch案例4 CyclicBarrier4.1 CyclicBarrier简介4.2 CyclicBarrier Barrier被破坏4.4 CyclicBarrier原理在java.util.concurrent包下&…

浅谈Dubbo的异步调用

之前简单写了一下dubbo线程模型&#xff0c;提到了Dubbo底层是基于NIO的Netty框架实现的&#xff0c;通过IO线程池和Work线程池实现了请求和业务处理之间的异步从而提升性能。 这篇文章要写的是Dubbo对于消费端调用和服务端接口业务逻辑处理的异步&#xff0c;在2.7版本中Dubb…

1650_MIT 6.828 open函数的简单梳理

全部学习汇总&#xff1a; GreyZhang/g_unix: some basic learning about unix operating system. (github.com) 一个shell的例程分析了很长时间&#xff0c;里面的基础知识一层嵌套一层。不过&#xff0c;这也是补充基本知识的很好的机会。既然自己日常接触的更多的还是这种通…

C++ 15 string容器

目录 一、string容器 1.1 简介 1.2 构造函数 1.3 赋值操作 1.4 字符串拼接 1.5 字符串查找和替换 1.6 字符串比较 1.7 字符串存取 1.8 字符串插入和删除 1.9 子串获取 一、string容器 1.1 简介 ① string是C风格的字符串&#xff0c;而string本质上是一个类。 ② s…

TryHackMe-Sustah(boot2root)

Sustah 开发人员在他们的游戏中添加了反作弊措施。你是 能否突破限制以访问其内部 CMS&#xff1f; 端口扫描 循例 nmap Web枚举 80端口没啥东西&#xff0c;看一下8085端口 gobuster扫一下 /ping似乎没什么东西 回来home&#xff0c;看看burp 使用bash生成数字字典 使用ff…

【mongodb 基础2】Install MongoDB Community Edition on macOS

文章目录一. 安装准备Install Xcode Command-Line ToolsInstall Homebrew二. Installing MongoDB 6.0 Community Edition1. 下载MongoDB Homebrew 组件包2. 更新组件包3. 安装MongoDBTo install MongoDB三. 安装后包含的组件四. Run&stop MongoDB1. 作为macOS服务的方式运行…

计算机二级考试(C++)复习

文章目录基础知识部分C知识点部分C流操作基础知识部分 指令周期&#xff1a; 一般把计算机完成一条指令所花费的时间称为一个指令周期。指令周期越短&#xff0c;指令执行就越快。 顺序程序&#xff1a; 顺序程序具有顺序性、封闭性和可再现性的特点&#xff0c;使得程序设…