Leetcode688: 骑士在棋盘上的概率(medium, 基于概率转移矩阵的解法)_骑士棋盘概率转移矩阵

目录

1. 题目描述

2. 解题分析

2.1 概率转移矩阵

2.2 概率状态转移

2.3 处理流程

3. 代码实现

4. 进一步的优化策略

---

 

1. 题目描述

        参见Leetcode688: 骑士在棋盘上的概率(medium)https://blog.csdn.net/chenxy_bwave/article/details/122975361

2. 解题分析

        在上一篇中给出的是基于动态规划的解决方案。本篇给出从另外一个有趣的角度出发解决方案。

2.1 概率转移矩阵

        对于棋盘上的每一格格子，反过来看，有多个可能的位置可能通过走一步到达。以n=3的棋盘为例，如下所示（图中的数字表示cell的标号，是为了方便说明）：

图1 棋盘示例 

        从cell#2和cell#7能够到达cell#0；从cell#6和cell#8能够到达cell#1，。。。，余者类推。

        根据题意，从每个cell出发向任意8各方向移动的概率相等，即每个方向都是1/8。由此我们可以得到如下图所示的概率转移矩阵（这个矩阵的大小是）：

图2 概率转移矩阵示例 

        其中， 行表示出发cell，列表示到达cell。每个格子中的数值表示从所在行对应的cell到达列对应的cell的概率。图中数值实际上应该是1/8。写成1只是处于方便，在外面统一乘以一个1/8的因子即可。Unsurprisingly, 这个矩阵是一个对称矩阵，更甚的是，它沿对角线和反对角线都是对称的。

         进一步，用一个长度为行向量p来表示棋盘的概率状态，向量每个元素值表示棋子出现在对应cell中的概率。该行向量中的元素序号与图1中所示的cell标号对应。比如说，p[0]表示棋子当前出现在棋盘最左上cell中的概率。

2.2 概率状态转移

        基于以上表示，从棋盘的一个状态出发经过一步以后到达的下一个状态就可以用一个矩阵乘法来表示，如下所示(其中T表示概率转移矩阵)：

                        

        进一步，从某个初始状态出发，经过k步移动以后所得到的概率状态（记为）为：

                         

        就是一个矩阵的幂运算，然后左乘一个行向量就搞定了。非常漂亮，是不是？熟悉概率论和随机过程的小伙伴对此当然会微微一笑，这就是大名鼎鼎的马尔科夫过程的状态转移动力学机制（dynamics）。

2.3 处理流程

        基于以上讨论，本问题的解决流程如下：

1.         根据输入n，构建概率转移矩阵T
2.         根据输入n和row, col 构建初始概率状态向量
3.         计算 
4.         计算经过k步以后仍然在棋盘上的概率，就是对中各项求和

        这里唯一需要担心的是，矩阵幂运算的效率如何，尤其是在n比较大的时候。以下实现中采用numpy来实现矩阵乘法。

3. 代码实现

import time
import numpy as np
 
class Solution:
    def knightProbability_matpower(self, n: int, k: int, row: int, col: int) -> float:
        delta = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
        # 1. Create row vector to represent prob state 
        p0            = np.zeros((1,n*n))
        p0[0][row*n+col] = 1 
        # 2. Create prob transition matrix
        T = np.zeros((n*n, n*n))
        for l in range(n*n): # for each row of T. Transition from cell#l
            # Fill T according to the reachability from cell#r
            l_row = l // n
            l_col = l % n
            for m in range(8):
                r_new,c_new = l_row + delta[m][0], l_col + delta[m][1]
                if r_new>=0 and r_new<n and c_new>=0 and c_new<n:
                    T[l][r_new * n + c_new] = 1        
        T  /= 8
        # print(T,p0)
 
        # 3. Calculate the final prob state after k steps
        Tk = np.eye(n*n)
        for j in range(0,k):
            Tk = Tk @ T
        pk = p0 @ Tk
            
        # 4. Calculate the probability inside the board after k steps
        return np.sum(pk,1)[0]

        运行结果（及对比）：

        跟之前用动态规划的方法相对比：在k较小的情况下如{6,12},{10,13}的基于概率转移矩阵幂的解法更快，而k比较大的时候如{8,30}则概率转移矩阵幂要慢得多。BUT。。。

4. 进一步的优化策略

        如上一节所示，在步数较大的时候，基于概率转移矩阵幂的方案比较慢。但是那是因为我们还有杀招没有使出来。

        由于概率转移矩阵T是实对称方阵，由线性代数可知，存在正交矩阵P使得

成立。其中为对角线矩阵，其对角线元素为T的特征根，可以表示为.

        由此可得：

                 

         只要先对T进行正交对角化处理，T的k次幂缩减为只需要1次矩阵运算，以及若干个实数(T的特征根)的k次幂运算。由于T的对角化需要一些一次性的代价，所以在k较小时可能没有太大的收益，但是随着k越来越大，所带来的计算量节约将越来越大！

        这就是数学的力量！

        关于这一方案的代码以后再补充。