LAMBDA函数递归：m×n矩阵路径问题

shaowu459 · 发表于 2022-12-6 22:32

本帖最后由 shaowu459 于 2022-12-7 00:02 编辑

本帖主要来讨论递归解决的另外一个经典例子：m×n矩阵从左上角到右下角的路径问题。

有这样一个m行n列的矩阵，矩阵中的元素都是非负整数，从左上角往右下角移动时，每次只能移动到相邻的一个格子，并且每次只能向下或者向右移动。

下图是一个4×4的矩阵，最左上角的B2单元格只能移动到C2或B3，C3单元格只能移动到C4或者D3。也就是说，移动的时候，到达矩阵中的每个元素时只能从左侧或者上方的元素过来。如果用f(m,n)来表达元素的位置，则f(m,n)可能来自于f(m-1,n)或者f(m,n-1)。当m或n是第一行或第一列时，则只能来自于左侧的f(m,n-1)或者上方的f(m-1,n)。
图片.png

那么，从左上角移动到右下角的路径一共有多少种呢？因为从左上角顶点开始走，所以从左上角到右下角，总共需要走n+m-2步，向下走总共需要m-1步，又因为每次都可以选择向下走，所以路径的总数就是C(n+m- 2,m- 1)种。
图片.png

shaowu459 · 发表于 2022-12-6 22:44

本帖最后由 shaowu459 于 2022-12-7 00:05 编辑

我们做一个4×4的辅助区，在最左上角单元格输入以下公式，并向右、向下填充：

=MIN(G1,F2)+B2

复制代码

上述公式使每个单元格获得原数组的累加值，累加值结果是当前单元格左侧和上方累加值较小者和原数组中对应位置的合计。

例如下图H3单元格的5=MIN(H2单元格的4，G3单元格的5）+C3单元格的1。也就是按只能向下或向右的移动方式，移动到当前单元格所有路径中和的最小值。如此一直计算到最右下角的绿色单元格=12，也就意味着原矩阵从最左上角到最右下角所有路径上的合计值最小值是12。
图片.png

这个最小值12的路径可能有多条，下面展示一条路径：
图片.png

站在矩阵中任意单元格去看，到达该单元格的路径数量其实等于达到其左侧单元格和到达其上方单元格的路径数量合计。如下图，到达方框中的3只能从圆圈的1或5过来，因为到达圆圈1有2种路径(1-->4-->1和1-->3-->1），到达5只有一种路径（第一行1-->3-->5）,所以到达方框的3共有2+1=3种路径。

归纳来说到达f(m,n)的路径条数=f(m,n-1)+f(m-1,n)，当m=1或者n=1及m=n=1时需要特殊处理一下。
图片.png

shaowu459 · 发表于 2022-12-6 23:16

本帖最后由 shaowu459 于 2022-12-6 23:18 编辑

根据上面的分析，明显可以看出求最终的路径总条数可以用递归来解决。我们定义fx如下：

=LAMBDA(d,m,n,IF(m*n=1,1,IF(m=1,fx(d,1,n-1),IF(n=1,fx(d,m-1,1),fx(d,m-1,n)+fx(d,m,n-1)))))

复制代码

在任意单元格中输入以下公式即可获得矩阵从左上角到右下角的总路径数：

=fx(A1:D4,4,4)

复制代码

公式大致分析如下：
=LAMBDA(d, 初始参数矩阵
            m, 初始参数矩阵的行数
            n,    初始参数矩阵的列数
            IF(m*n=1,1,    如果m=n=1就是到最左上角单元格，返回1
                              IF(m=1,fx(d,1,n-1), 如果到第1行了，就只能往做移动
                                                         IF(n=1,fx(d,m-1,1), 如果到第1列了，就只能往上移动
                                                                                    fx(d,m-1,n)+fx(d,m,n-1)))))  加和左侧和上方路径数量

shaowu459 · 发表于 2022-12-6 23:25

同样的道理，我们可以定义gx来获取所有路径的具体情况：

=LAMBDA(d,m,n,IF(m*n=1,@+d,IF(m=1,gx(d,1,n-1),IF(n=1,gx(d,m-1,1),VSTACK(gx(d,m-1,n),gx(d,m,n-1))))&"->"&INDEX(d,m,n)))

复制代码

公式大致解读如下：

=LAMBDA(d, 初始参数矩阵
            m, 初始参数矩阵行数
            n, 初始参数矩阵列数
            IF(m*n=1,@+d,  如果m=n=1则返回矩阵左上角的值
                           IF(m=1,gx(d,1,n-1),  如果到第1行，只能向左走
                                       IF(n=1,gx(d,m-1,1),  如果到第1列，只能向上走
                                                VSTACK(    非第1行第1列，则堆积上方和左侧结果
                                                            gx(d,m-1,n),  上方结果
                                                            gx(d,m,n-1) 左侧结果
                                                            )
                                          )
                              )&"->"&INDEX(d,m,n)  记录以上的路径->当前的元素值
               )
            )

shaowu459 · 发表于 2022-12-6 23:31

本帖最后由 shaowu459 于 2022-12-6 23:47 编辑

定义tx，可以获得每条路径经过数字合计值的最小值（可能有多条最小值路径）：

=LAMBDA(d,m,n,IF(m*n=1,@+d,IF(m=1,tx(d,1,n-1),IF(n=1,tx(d,m-1,1),MIN(tx(d,m-1,n),tx(d,m,n-1))))+INDEX(d,m,n)))

复制代码

公式与前两个公式大同小异：
=LAMBDA(d,
            m,
            n,
            IF(m*n=1,@+d,
                           IF(m=1,tx(d,1,n-1),
                                       IF(n=1,tx(d,m-1,1),
                                                MIN(tx(d,m-1,n),tx(d,m,n-1))  取左侧和上方的合计值较小者
                                          )
                              )+INDEX(d,m,n) 较小者加上当前矩阵的元素数值
            )
            )

shaowu459 · 发表于 2022-12-6 23:40

本帖最后由 shaowu459 于 2022-12-7 00:08 编辑

4楼公式已经获得了所有路径，如果要求最小路径，就可以MAP函数将每个元素按分隔符拆分求和，然后再FILTER(路径数组，每个路径值合计=每个路径值合计数组的最小值)来筛选出来。我们也可以定一个一个dx来直接获得（忽略效率问题）最小值对应的各种路径：

=LAMBDA(d,m,n,IF(m*n=1,@+d,IF(m=1,dx(d,1,n-1),IF(n=1,dx(d,m-1,1),LET(s,VSTACK(dx(d,m-1,n),dx(d,m,n-1)),t,MAP(s,LAMBDA(x,SUM(--TEXTSPLIT(x,"->")))),FILTER(s,t=MIN(t)))))&"->"&INDEX(d,m,n)))

复制代码

=LAMBDA(d,
            m,
            n,
            IF(m*n=1,@+d,
                           IF(m=1,dx(d,1,n-1),
                                       IF(n=1,dx(d,m-1,1),
                                                  LET(s,VSTACK(dx(d,m-1,n),dx(d,m,n-1)), 堆积各种方案结果

                                                        t,MAP(s,LAMBDA(x,SUM(--TEXTSPLIT(x,"->")))), 将方案中数字拆分后求和
                                                        FILTER(s,t=MIN(t)) 筛选数值最小的路径
                                                      )
                                         )
                              )&"->"&INDEX(d,m,n) 当前元素之前的最小路径并上当前元素
               )
            )

shaowu459 · 发表于 2022-12-6 23:43

本帖最后由 shaowu459 于 2022-12-6 23:49 编辑

文件已在1楼上传，递归公式根据算法不同写法应该有很多种，欢迎分享探讨。在Excel中解决类似问题，效率确实不太理想。矩阵稍微增大之后，比如说10×20的矩阵，Excel就计算不出来了，并且由于路径总数太大，也无法显示在工作表的有限行数内。所以，本帖也仅仅是练习使用递归解决问题的方法，如果真实需求使用，这些还得靠各种编程语言来高效率实现。

alan57 · 发表于 2022-12-7 10:04

HCDGCS · 发表于 2022-12-9 16:13

太厉害了！！！

一杯绿茶来了 · 发表于 2022-12-12 12:51

一脸懵，云山雾绕

		自动登录	找回密码
密码			免费注册

[原创] LAMBDA函数递归：m×n矩阵路径问题

评分