动态规划算法应用及其在时间效率上的优化
| 摘要 | 第1-4页 |
| Abstract | 第4-7页 |
| 引言 | 第7-9页 |
| 1 绪论 | 第9-21页 |
| ·动态规划的本质 | 第9-12页 |
| ·多阶段决策问题 | 第9-10页 |
| ·阶段与状态 | 第10页 |
| ·决策和策略 | 第10-11页 |
| ·最优化原理与无后效性 | 第11页 |
| ·最优指标函数和规划方程 | 第11-12页 |
| ·动态规划的设计与实现 | 第12-17页 |
| ·动态规划的多样性 | 第12-14页 |
| ·动态规划的模式性 | 第14-15页 |
| ·动态规划的技巧性 | 第15-17页 |
| ·动态规划与一些算法的比较 | 第17-19页 |
| ·动态规划与分治 | 第17页 |
| ·动态规划与递推 | 第17-18页 |
| ·动态规划与搜索 | 第18-19页 |
| ·本章小结 | 第19-21页 |
| 2 动态规划算法在三个具体问题中的应用 | 第21-35页 |
| ·“过河”问题 | 第21-25页 |
| ·问题描述 | 第21-22页 |
| ·样例分析 | 第22页 |
| ·算法分析 | 第22-24页 |
| ·问题实现 | 第24页 |
| ·测试结果 | 第24-25页 |
| ·“金明的预算方案”问题 | 第25-29页 |
| ·问题描述 | 第25-26页 |
| ·样例分析 | 第26-27页 |
| ·算法分析 | 第27-29页 |
| ·问题实现 | 第29页 |
| ·测试结果 | 第29页 |
| ·“矩阵取数游戏”问题 | 第29-35页 |
| ·问题描述 | 第29-31页 |
| ·样例分析 | 第31页 |
| ·算法分析 | 第31-33页 |
| ·问题实现 | 第33页 |
| ·测试结果 | 第33-35页 |
| 3 动态规划算法在时间效率上的优化 | 第35-53页 |
| ·动态规划在时间效率上优化的必要性 | 第35页 |
| ·动态规划时间复杂度的分析 | 第35-36页 |
| ·减少状态总数 | 第36-38页 |
| ·选择适当的规划方向 | 第36-38页 |
| ·改进状态表示 | 第38页 |
| ·减少每个状态转移的状态数 | 第38-47页 |
| ·四边形不等式和决策的单调性 | 第38-43页 |
| ·决策量的优化 | 第43-45页 |
| ·合理组织状态 | 第45-47页 |
| ·细化状态转移 | 第47页 |
| ·减少状态转移的时间 | 第47-51页 |
| ·减少决策时间 | 第47-49页 |
| ·减少计算递推式的时间 | 第49-51页 |
| ·本章小结 | 第51-53页 |
| 4 实验结果 | 第53-59页 |
| ·第三章例一“大理石划分 Divide”问题 | 第53-54页 |
| ·第三章例二“石子合并(最小得分)”问题 | 第54-55页 |
| ·第三章例三“邮局post”问题 | 第55-56页 |
| ·第三章例四“石子合并(最大得分)”问题 | 第56-58页 |
| ·第三章例五“求最长单调上升子序列”问题 | 第58-59页 |
| 5 总结与展望 | 第59-61页 |
| ·本文工作总结 | 第59页 |
| ·今后工作展望 | 第59-61页 |
| 致谢 | 第61-62页 |
| 参考文献 | 第62-66页 |
