在阅读本文之前，请先对强化学习，Q-learning以及房间问题有一个初步的了解。可以参考下面这两个链接：

Q-learning Step by Step Tutorial

Q-learning算法分析与代码实现

“房间问题”简单来说就是终点确定的最短路径寻找问题，但是个单目标优化问题，也就是说仅仅只需要考虑路程最短，不需要考虑其它成本。在众多关于Q-learning与“房间问题”的入门介绍的文章中，无一不是参考了上面两篇文章中的方法。这个方法具有很好的可理解性，并可以快速的梳理出实现Q-learning的一般步骤，但存在一个很严重的问题，即需要人工给出Reward Matrix（奖励矩阵），这样很大程度上就限制了其通用性。面对一个仅有6个房间的问题，画出节点图，手工写出奖励矩阵并非难事，但如果是100个房间，10000个房间呢？这就比较难了，不仅手写奖励矩阵很困难，也会极大的增加训练的时间复杂度。为什么这么说，还是用6个房间的这个例子比较好解释。在建立Q-learning中被用来训练更新的Q-Table时，通常以状态(state)为行，动作(action)为列，但实际上在“6个房间问题”里，却用的是当前状态(current state)为行，下一状态(future state)为列。所以需要一个6x6的Q-table：

在Q-learning算法的实现过程中，每次的训练都会有由state去确定action的步骤，即找到可行的action并确定下一个state，相应的Q-Table可以表示成Q(S, A)。也就是依据current state找寻future state，在确定当前状态后，找寻可能的action和需要遍历所有的未来状态，对于“6个房间问题”而言，需要循环6次。假设对于某一特定的状态可行的action和future state有n个，那么在对这n个结果求解其Q(future state, fucture action)中的最大值，至少需要6(n - 1)次循环，如果加上action确定的6次循环，则一次迭代至少需要6n次。想象一下，如果是1920x1080个房间呢？毫无疑问运算量将大大增加。

通用方法

在此之前可先阅读这两篇文章:

强化学习(Q-learning~了解了一波

增强学习系列之（二）：实现一个简单的增强学习的例子

以上两篇文章都是关于一维空间寻最短路径的问题，其中的action只有左右两个选项。然而对于一个二维平面的最短路径寻找问题(Path-Finding)，处在任何一个状态的动作都只有4个选项，上下左右，所以这个Q-Table也可以写成如下形式（UDLR分别代表上下左右）：

这种6x4的矩阵才是通用方法中的Q-Table，即使state多达10000个，矩阵的维度也只有10000x4，远小于第一种方法的10000x10000。使用这个形式Q-Table的关键问题在于如何由action获得下一个的state，也就是action到state的转化问题。还是以“6个房间问题”为例子，通过抽象化的处理，我可以把左边这副实际的房间分布图转换成右边的示意图。

示意图对原图中房间的重新编号与新添的3号房间对最终结果并无任何影响。原先的0号房间编程了5号，1号成了4号，2号变为0号，3号变为1号， 4号成了2号，5号变成了6号。状态0的action矩阵可以写为：

在Action矩阵中，0表示路线被隔断，1表示路线通畅。对于A0来说，只有向右的action是可以通畅的转往状态1的。可以很快的写出A0~A6的Action矩阵，如若仅自动识别可行的action，4x6次循环即可，而如果是遍历和每一个state的关联，则需6x6次循环，效率的提升不言而喻。Action转换为state的基本思想其实也很简单，假设当前处在第r个房间也就是状态r（总共有MxN个房间，M为列数，N为行数），其上下左右的状态分别为，r-M

，r+M，r-1，r+1，处在边界的状态再特殊考虑：

基本的原理就是这样了。

如需原码，请参考链接：

https://github.com/JinyuGuan/Q-learning-Room-Problem.git

https://github.com/JinyuGuan/Q-learning-Room-Problem.git