无后效性?

每个阶段的状态的最优值只和前面的阶段有关,和后面的阶段无关。如果将各个阶段的状态用有向图表示,那么无后效应就是要求有向图中无回路。无后效应是划分阶段的依据,只有当有向图无回路的时候才能根据有向图的拓扑排序来划分阶段。

 

这是我以前问别人无后效性的问题时别人回的信,看看吧 :)

=======================================================

我总是不太理解什么叫无后效性,能不能讲讲和别的论文或书上不一样的东西来解释一下,谢谢了:)

首先,请注意无后效性一般是针对问题的分析方式的,不是描述一个问题的。

我们说某问题不具有无后效性往往是指他的通常解法不具有这种性质,而如果我们把状态定义成满足无后效性原理

的方式,状态太多,也没有意义。

无后效性,就是说当前状态是历史的完全总结,和如何达到这一个状态无关。

例如,对于这道单词接龙的题目,每个单词最多用两次。

那么“当前接到的单词”就不能概括整个“历史”,因为同样是接到的这个单词,以前考虑过的单词究竟是用过

没有,用过多少次,将同样影响今后的发展,而单一的状态参量无法概括这些信息。如果把这些信息加到状态

参量中,状态太多(指数级),动态规划也没有多大意义。

如果影响历史的信息并不多,我们可以通过升维的方法让我们的状态具有无后效性,

所以我们在思考状态的时候,指导思想就是“简洁而又完全的概括历史”

via 无后效性?-CSDN论坛-CSDN.NET-中国最大的IT技术社区.

  • 浏览:677
  • 评论:0

发表新的回复