1

假设我有 n 状态 S={s1,s2,s3, ... ....ETC。

我应该使用什么算法或程序来选择从 state-x (s_x) 开始的得分最高的序列/路径。

两个问题：

  1. 选择最好的下一个状态，以便在无限长的路径中我平均选择尽可能好的状态？
  2. 给定路径长度 L ，选择将产生最高分数的状态序列？

我目前正在研究强化学习，但这似乎有点矫枉过正，因为我既没有行动，也没有政策。可能我可以使用类似价值函数的东西，不知道。

你会用什么？

PS>在某些场景中，T-matrix 可能会随着时间而改变。

http://mnemstudio.org/path-finding-q-learning-tutorial.htm

看来 Q-learning 是一个不错的选择。我看到的唯一区别是，如果我要随着时间的推移存储 Q 值，我必须想办法适应变化的 T 矩阵。

而第二个更难的是没有最终目标，只有改变中间分数。可能我不需要改变算法，它只会收敛到改变分数，我认为这没关系。

我最初的想法是在每个时间步上做 L 步最佳路径（即每次从头开始重新计算 Q），但如果可以的话，我更愿意根据传入的数据保持一个不断变化的 Q 表。

4

1 回答 1

2

您的选项 1 将被称为贪婪方法。这通常是指选择立即“最佳”选项的方法。问题在于，现在贪婪的选择会限制你未来的最佳选择。

如果您不设置路径长度的限制，那么显然最大分数是无限的。

所以现在的问题是：给定路径长度的最佳序列是什么？这可以通过诸如动态规划之类的多项式时间来解决。

一个递归公式（然后你可以用它来计算动态编程部分）会说：要找出从状态 x 开始的长度为 L 的最佳路径，请查看所有其他状态 y。对于其中的每一个，计算 T_xy +“从状态 y 开始的长度为 L-1 的最佳路径”。

显然，从某个状态 x 开始的长度为 1 的最佳路径将是“下一个最佳状态”，因此您的递归具有简单的基本情况。

于 2017-01-19T20:46:36.297 回答