har*_*ree 29 algorithm math dynamic-programming
我已经在某些文本中看到了关于算法分析和设计的剪切和粘贴样张的参考.在为优化问题证明最优子结构时,通常会在动态规划的上下文中提及它(参见第15.3章CLRS).它还显示了图形操作.
这种证明的主要思想是什么？我如何使用它们来证明算法的正确性或特定方法的便利性？
Cam*_*ron 26
术语"剪切和粘贴"有时在进行动态编程时出现在算法中(以及其他事情,但这是我第一次看到它的地方).我们的想法是,为了使用动态编程,您尝试解决的问题可能具有某种底层冗余.您使用表或类似技术来避免一遍又一遍地解决相同的优化问题.当然,在开始尝试使用动态编程之前,最好先证明问题中存在这种冗余,否则你不会通过使用表来获得任何东西.这通常被称为"最佳子问题"属性(例如,在CLRS中).
"剪切和粘贴"技术是一种证明问题具有此属性的方法.特别是,您希望表明当您提出问题的最佳解决方案时,您必须使用组成子问题的最佳解决方案.证据是矛盾的.假设您通过使用次优问题的次优解决方案来提出问题的最佳解决方案.然后,如果您使用最佳子问题解决方案(通过"粘贴"它们)替换("剪切")那些次优的子问题解决方案,您将改进最佳解决方案.但是,由于您的解决方案是假设的最佳解决方案,因此您会产生矛盾.这种证明还涉及其他一些步骤,但这就是"剪切和粘贴"部分.
| 归档时间： |
|
| 查看次数： |
7946 次 |
| 最近记录： |