没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
xdhu 1
运筹学通论I
胡晓东
应用数学研究所
中国科学院数学与系统科学研究院
http://www.amt.ac.cn/member/huxiaodong/index.html
Institute of Applied Mathematics
xdhu 2
5. 组合优化 - 算法设计技巧
精确算法
分而治之 (搜索、排大小序、旅行商)
动态规划 (最短路、三角剖分、背包)
分支定界 (整数线性规划、旅行商、工件排序)
近似算法或启发式算法
贪婪策略 (最小生成树、最大可满足、背包、
顶点覆盖、独立集、旅行商)
局部搜索(最大匹配、旅行商、最大割)
序贯法 (工件排序、装箱、顶点着色)
整数规划法 (顶点覆盖、最大可满足、最大割)
随机方法 (最小割、最大可满足、顶点覆盖)
在线算法 (页面调度、k-服务器、工件排序、装箱)
不可近似 (最大团、背包、旅行商、装箱、连通控制集等)
xdhu 3
5.7 整数规划方法
整数规划是组合优化领域的一个非常重要的研究方向。
一般来讲,绝大多数组合优化问题都可以比较容易地表述为等
价的整数规划问题,有时候是线性的,有时候是非线性的。这
样借助一些商业软件,就可以求解这些组合优化问题了。基于
整数规划的求解组合优化问题的方法包括如下几个步骤:
将所考虑的组合优化问题转化为一个等价的整数规划问题
将整数约束条件松弛,得到一个容易求解的优化问题
用有效算法(在多项式时间内)求解松弛问题
将所求得的最优(非整数)解进行适当的舍入,
得到原问题的一个可行(整数)解
4
5.7 最小权顶点覆盖
我们首先考虑最小权顶点覆盖问题。它是最小顶点覆盖
问题的一般形式,而后者是一个著名的 NP-难问题。
权值为 11 的
顶点覆盖
1
3
2
2
1
2
2
2
权值为 9的
顶点覆盖
1
3
2
2
1
2
2
2
顶点赋权图
1
3
2
2
1
2
2
2
问 题: 最小权顶点覆盖
实 例: 图 G=(V, E) 及顶点 v
i
V 的权值 w
i
。
可行解: 顶点覆盖 CV。
目 标: 最小化覆盖 C 中的顶点的权值之和 ||C||= w
i
v
i
C
剩余22页未读,继续阅读
卡哥Carlos
- 粉丝: 27
- 资源: 300
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- fdsfdsfdsfdsfdsfdsfdsfds
- 目标检测-零售食品LOGO检测数据集-5000张图-+对应VOC-COCO-YOLO三种格式标签+数据集划分脚本
- 目标检测-零售食品LOGO检测数据集-1000张图-+对应VOC-COCO-YOLO三种格式标签+数据集划分脚本
- 计算机科学选修课:人工智能导论 第四节 PPT
- 计算机科学选修课:人工智能导论 第三节 PPT
- Delphi 12 控件之LMD.VCL.Full.Version.zip
- 常用阀门定位器的调试步骤及说明
- 计算机科学选修课:人工智能导论 第二节 PPT
- 计算机科学选修课:人工智能导论 第一章 PPT
- Delphi 12 控件Indy-Indy-10.6.3.3.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0