一个老鼠走迷宫问题的python解法

今天在查找马尔科夫链的过程中，在网上看到一个有意思的问题，于是用python将其做了实现和改进，题目如下：

如下图所示的迷宫共有9个格子，相邻格子有门相通，9号格子就是迷宫出口. 整个迷宫将会在5分钟后坍塌.
1号格子有一只老鼠，这只老鼠以每分钟一格的速度在迷宫里乱窜（它通过各扇门的机会均等）。求此老鼠在迷宫坍塌之前逃生的概率。如果这只老鼠速度提高一倍，则老鼠在迷宫坍塌之前逃生的概率能增加多少？

题目中可以看空间1为入口，空间9为出口，思路上既可以用迭代的方法，也可以用矩阵形式来编写。

先是基于马尔科夫链的矩阵形式。马尔科夫链的本质是一个时间、状态离散的马尔可夫过程，本质特征就是，模型当前的状态，依赖也仅依赖于前面的那一个状态。
设S为状态分布矩阵，P为状态转移矩阵，那么老鼠的每一次移动，这个过程即是乘上P的过程，当前的状态分布矩阵，即是P与S的矩阵乘积。（此处S需以列向量的形式呈现）具体不在赘述，如果编程采用矩阵运算的形式，那么对于题中这样一个长度为9的状态分布矩阵，就需要用到9*9的状态转移矩阵来计算，如果迷宫变大了，矩阵将会变得非常大。

那么从迭代的思路来看呢：
在初始状态的情况下，老鼠所在的位置，空间状态概率被记为1，其余位置的概率为零。
现在老鼠只有两个选择，要么去2，要么去4，在机会均等的情况下，那么下一个状态（也就是老鼠动一步的情况下），老鼠到达2和4的概率都是0.5，而老鼠留在1的概率为0，所以2、4的当前状态的概率都变成了0.5，而1的当前状态的概率，变成了0。
现在要进行下一次移动，又会面临新的选择，老鼠每一次的移动，就以此类推。

我们抛开确定的状态，从整体任选一个状态。如果老鼠的当前位置处于四个角上，即周围存在两个可以去的空间，那么移动机会均等的情况下，去往每一个空间的可能性为1/2。如果老鼠当前位于边上，周围就有三个可以去的空间，那么这个概率就变成了1/3，以此类推，内部的话就会有四个空间，概率是1/4。

然后我们再考虑，从上一个状态到达当前状态的概率是多少呢？那就要看，当前位置，老鼠可能是从哪里来的。如果老鼠来源的那个空间，周围有三个可以去的空间，那么现在空间的概率，就是老鼠来源空间概率的1/3，当然，当前空间不仅仅只会有这一个老鼠来源，会有很多个，那么当前空间的概率，就是这些来源的累积。

除此以外，要考虑几个点：老鼠走到出口后，是不会再动的，这就意味着，出口相邻的点，是不会接受来自出口的老鼠的，也就是从出口出来的老鼠，概率应当统统记为0。既然老鼠在出口去不了其他地方，是在出口是不会动的，那么老鼠在出口的概率，就每次更新状态时候应当保留。（出口，是一个只进不出的点）

此外，这个程序可以自行设定迷宫长与宽，设定老鼠当前位置和出口位置，设置步数。

可以的改进：可以扩展到三维或是多维；设定某个移动方向的倾向（也就是概率，目前是概率均等）

import numpy as np

def connect(point,size,rat_exit):
    flag = 0
    m,n = size
    x,y = point
    if [x,y] == rat_exit:
        return 0
    for [xx,yy] in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        if 0<=xx<m and 0<=yy<n:
            flag += 1
    if flag == 1:
        return 1
    elif flag == 2:
        return 0.5
    elif flag == 3:
        return 1/3
    elif flag ==4:
        return 0.25
#main
size = input('棋盘的长与宽：')
size = list(int(x) for x in size.split(','))
m,n = size
rat = input('入口所在坐标：')
rat = list(int(x) for x in rat.split(','))
a,b = rat
rat_exit = input('出口所在坐标：')
rat_exit = list(int(x) for x in rat_exit.split(','))
aa,bb = rat_exit
# l = int(input('逃离步长：'))
t = int(input('逃离步数：'))
A = np.zeros([m,n])
A[a,b] = 1
print('初始状态为：')
print(A)
for i in range(t):
    AA = A.copy()
    for x in range(m):
        for y in range(n):
            if [x,y] != rat_exit:
                AA[x,y] = 0
            for [xx,yy] in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
                if 0<=xx<m and 0<=yy<n:
                    AA[x,y] += A[xx,yy]*connect([xx,yy],size,rat_exit)
    A = AA
    print('第{}次行动后的状态为：'.format(str(i+1)))
    print(A)
    print('\n')
P = A[aa,bb]
print('老鼠到达出口的概率为：'+ str(P))