| 一类0-1背包问题算法程序的形式化推导 |
| 王昌晶; 薛锦云
|
| 2009
|
| 发表期刊 | 武汉大学学报(理学版)
 |
| 期号 | 6页码:674-680 |
| 摘要 | 0-1背包问题是经典的组合优化问题与NP完全问题,具有重要的应用价值与理论意义.本文使用PAR(Partition and Recurrence)方法形式化推导了0-1背包问题的高效动态规划算法程序.通过类比分析,该问题的若干变形问题的算法也可推导得到,算法通过PAR平台的自动生成系统转换成可执行语言程序并运行通过,保证了该类0-1背包问题算法的正确性和可靠性.本文主要的贡献是将PAR方法推广到能处理带约束条件的组合优化类问题,大大扩展了PAR方法的应用范围,为形式化开发高效高可信组合优化类算法开辟了一条新途径. |
| 收录类别 | 其他
|
| 关键词 | 形式化推导,高可信,组合优化,0-1背包问题
|
| 部门归属 | 江西师范大学江西省高性能计算技术重点实验室;中国科学院软件研究所;中国科学院研究生院;
|
| 内容类型 | 期刊论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/7950
|
| 专题 | 基础软件与系统重点实验室
|
推荐引用方式
GB/T 7714 |
王昌晶,薛锦云. 一类0-1背包问题算法程序的形式化推导[J]. 武汉大学学报(理学版),2009(6):674-680.
|
| APA |
王昌晶,&薛锦云.(2009).一类0-1背包问题算法程序的形式化推导.武汉大学学报(理学版)(6),674-680.
|
| MLA |
王昌晶,et al."一类0-1背包问题算法程序的形式化推导".武汉大学学报(理学版) .6(2009):674-680.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论