计算机程序设计

动态规划,基本原理

要选择编程任务的最佳解决方案,有时需要经历大量的数据组合,从而加载个人计算机的内存。 这样的方法包括例如“划分和征服”编程方法。 在这种情况下,该算法提供将任务分离成单独的小子任务。 该方法仅在小子任务彼此独立的情况下使用。 为了避免在子任务相互依赖的情况下进行不必要的工作,使用了美国R. Bellman在20世纪50年代提出的动态规划方法。

方法的本质

动态规划在于确定n维问题的最优解,将其分解为n个独立步骤。 它们中的每一个都是相对于一个变量的子任务。

这种方法的主要优点可以认为是开发人员从事子任务的一维优化任务,而不是n维问题,主要任务的解决方案是“从下到上”。

在子任务相互关联的情况下,建议应用动态规划,即 有共同的模块。 该算法为每个子任务提供一次解决方案,并将回复保存在特殊表中。 这使得在满足类似子任务时可以不重新计算答案。

动态规划的任务 解决了 优化 问题 。 这种方法的作者R. Bellman制定了最优性的原则:无论初始状态是在每个步骤,在此步骤中确定的解决方案,所有以下选择都是相对于系统在步骤结束时采取的状态最佳的。

该方法提高了通过搜索变体或递归来解决的任务的性能。

构建算法的问题

动态规划假设构建这样的任务算法,其中任务被分成两个或更多的子任务,使得其解由从其中包括的所有子任务的最优解形成。 此外,需要编写重复关系并且为整个问题计算最优参数值。

有时,在第三步,您还需要记住有关每个子任务进度的辅助信息。 这被称为相反的。

方法的应用

当有两个特征时使用动态编程:

  • 子任务的最优性;
  • 在问题中存在重叠的子任务。

通过动态规划的方法解决优化问题,首先需要描述解决方案的结构。 如果问题的解决方案由其子任务的最佳解决方案组成,则问题是最佳的。 在这种情况下,建议使用动态编程。

问题的第二个属性,对于这种方法来说至关重要,是少量的子任务。 该问题的递归解决方案使用相同的重叠子任务,其数量取决于初始信息的大小。 答案存储在一个特殊的表中,程序可以节省时间,使用这些数据。

特别有效的是使用动态规划,实质上需要逐步采取任务。 例如,考虑更换和修理设备的简单例子。 假设在轮胎制造厂的铸造机上,以两种不同的形式同时制造轮胎。 如果其中一种形式发生故障,则必须拆卸机器。 很明显,有时更换第二种形式是为了不在机壳中拆卸机器更为有利,而这种形式在下一阶段将是不可行的。 此外,在开始失败之前更换两个操作表单都更为容易。 动态规划的方法决定了更换这种形式的最佳策略,同时考虑到所有因素:继续运行形式的好处,怠速机的损失,拒收轮胎的成本等等。

Similar articles

 

 

 

 

Trending Now

 

 

 

 

Newest

Copyright © 2018 zhcn.delachieve.com. Theme powered by WordPress.