0

考虑一棵深度树B（即：所有路径都有长度B），其节点代表系统状态，边代表动作。

每个动作a in ActionSet都有一个增益，并使系统从一个状态转移到另一个状态。执行一系列动作A-B-C或C-B-A（或这些动作的任何其他排列）会带来相同的收益。而且：

  • 之前执行的动作次数越多，询问a时总增益的增加越低a
  • 每条路径获得的增益不能大于一个量H，即：某些路径可能获得低于 的增益，但是每当执行一个动作使H总增益等于H0
  • 动作序列得到的#b,h,j, ..., a#是g(a)( 0 <= g(a) <= H)
  • 一旦对从根到叶的路径执行了操作，就不能在同一路径上再次执行该操作

算法1的应用。我应用以下算法（A*-like）：

  1. 从根开始。
  2. 展开树的第一层，它将包含ActionSet. 每个扩展操作a都有增益f(a) = g(a) + h(a)，其中g(a)定义如前所述，是对执行其他操作h(a)将获得的收益的估计。B-1
  3. 选择a*最大化的动作f(a)
  4. 展开子项a*
  5. B迭代 2-3 直到从根到保证最高的叶子的整个动作路径f(n)被访问。请注意，新选择的操作也可以从先前级别放弃的节点中选择。例如，如果扩展后a*的节点最大化f(a)是根的一个孩子，则选择它作为新的最佳节点

算法2的应用。现在，假设我有一个贪心算法，它只查看g(n)知识加启发式函数的组成部分f(n)，即该算法根据已经获得的收益选择动作：

  1. 在第一步，我选择a最大化增益的动作g(a)
  2. 在第二步，我选择b最大化增益的动作g(b)

宣称。实验证明告诉我，这两种算法带来了相同的结果，可能是混合的（例如，第一个建议序列A-B-C，第二个建议B-C-A）。但是，我没有成功理解为什么。

我的问题是：是否有一种正式的方法可以证明这两种算法返回相同的结果，尽管在某些情况下是混合的？

谢谢你。

4

1 回答 1

0

A* 搜索将返回最优路径。根据我对问题的理解，您的贪婪搜索只是执行贝叶斯计算，并且会继续这样做，直到找到一组最佳节点。由于节点的顺序无关紧要，因此两者应该返回相同的节点集，尽管顺序不同。

我认为这是正确的，假设您可以从每个节点执行相同的操作集。

于 2013-07-01T17:23:46.337 回答