一类0-1背包问题算法程序的形式化推导
| Data(s) |
2009
|
|---|---|
| Resumo |
0-1背包问题是经典的组合优化问题与NP完全问题,具有重要的应用价值与理论意义.本文使用PAR(Partition and Recurrence)方法形式化推导了0-1背包问题的高效动态规划算法程序.通过类比分析,该问题的若干变形问题的算法也可推导得到,算法通过PAR平台的自动生成系统转换成可执行语言程序并运行通过,保证了该类0-1背包问题算法的正确性和可靠性.本文主要的贡献是将PAR方法推广到能处理带约束条件的组合优化类问题,大大扩展了PAR方法的应用范围,为形式化开发高效高可信组合优化类算法开辟了一条新途径. |
| Identificador | |
| Fonte |
王昌晶;薛锦云.一类0-1背包问题算法程序的形式化推导,武汉大学学报(理学版),2009,(6):674-680 |
| Palavras-Chave | #形式化推导 #高可信 #组合优化 #0-1背包问题 |
| Tipo |
期刊论文 |
