- 1、本文档共42页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[基础科学]组合优化
组合优化
(Combinatorial Optimization )
组合优化
• 通常把从有限个可行解中找出使某个目标
函数达到最优的解的优化问题称为组合优
化 (Combinatorial Optimization) 。
• 象Lagrange 乘子法那样在实数空间内取值
的优化问题称为连续优化 (Continuous
Optimization ),与之相对应的就称为离散
优化 (Discrete Optimization )。
1
背包问题
n j
• 设需要考虑的物品共有 种,第 种物品的价值
p w C
为 ,大小为 ,背包容量为
j j
• 背包问题 (knapsack )要求选择I {1,2, , n},
使得在wj C 的前提下,使p j 尽可能的大
j I j I
• 由于每个物品只有放入和不放入两种可能,因此
n
可行解数目不超过 个
2
2
旅行售货商问题
• 一推销商想在若干个城市中推销自己的产
品。计划从某个城市出发,经过每个城市
恰好一次,最后回到出发的城市。假设城
市之间距离已知,推销商应如何选择环游
路线,使他走的路程最短。该问题称为旅
行售货商问题 (Traveling Salesman
Problem,TSP )
旅行售货商问题
阿姆斯特丹685 925 1180 960 1755 1235 1180 阿姆斯特丹
柏林1160 1105 340 1530 585 630 华沙
日内瓦 325 950 880 1575 1025 柏林
米兰 870 575 1495 830 布拉格
布拉格 1290 625 290 日内瓦
罗马 1915 1130
华沙 795 维也纳
米兰
维也纳
最优路程:5140 罗马
VLSI设计中的TSP
• PMA343
枚举
• 组合优化问题通常不能通过枚举所有可能的解加
以比较来求解,其原因是可行解的数目可能是一
很大的数,以致于当前或相当长的一段时间内人
力或计算机不能承受
• 也有一些问题,如最小生成树,可以不通过枚举
找到最优解,从而使求解时间大幅下降。而对有
些问题,如TSP,目前还没有找到这样的方法
• 组合优化研究的一个重要方面是区分哪些问题是
容易求解,哪些问题是难求解的
枚举
20 1
您可能关注的文档
- [基础医学]A791、儿科、眼、耳鼻咽喉科学文献信息.ppt
- [基础医学]2012第54届美国血液年会ASH进展.ppt
- [基础医学]上消化道出血诊治规范.ppt
- [基础医学]三阴性乳腺癌的治疗进展--吴新红.ppt
- [基础医学]不寐.ppt
- [基础医学]中国文化行业分析报告.pdf
- [基础医学]《循环系统疾病中药关联销售》.ppt
- [基础医学]医学_护理.doc
- [基础医学]呼吸机.ppt
- [基础医学]休克 Shock.ppt
- 2024《医院药品管理系统分析与设计》10000字.docx
- 2024《西麦食品公司激励机制存在问题及对策9300字》.docx
- 2024《辛弃疾流寓经历及作品分析》11000字.docx
- 2024《中航油公司的财务风险管理存在的问题及完善对策研究》21000字.docx
- 2024《S县沿海工业城道路绿化树种的选择设计》10000字.doc
- 2024《基于单片机电锅炉恒温控制系统的硬件电路设计》11000字.docx
- 2024《我国数据主权保护面临的挑战及完善对策研究》15000字.docx
- 2024《人力资源管理部门实践报告》4000字.docx
- 2024《上海市浦东新区社区养老服务问题及完善对策研究—以S社区养老服务中心为例》12000字.doc
- 2024《云南白药公司现金流量表分析案例》9600字.docx
文档评论(0)