在基质上模拟液体流动

Question

我必须模拟一个包含一组整数的方阵中的液体流动。液体应该从矩阵的左上角开始。它只能向右或向下移动相邻矩阵。相邻矩阵的值越低，它流动的潜力就越大。液体的运动被认为是在基质的右侧或下方停止。该程序应该能够显示液体通过的所有数字的总和。

import numpy as np

mtr= np.array ([[0, 2, 9], 
                [4, 9, 8], 
                [6, 8, 1]])

print(mtr)

def min_adj_val(a, b): 
        if (a < b): 
            return a 
        else: 
            return b 

def min_mtr(mtr, m, n):

        if (m == 2 or n == 2):
            return mtr[m][n]
        else:
            return mtr[m][n] + min_adj_val(min_mtr(mtr, m+1, n),min_mtr(mtr, m, n+1))

print(min_mtr(mtr,0, 0)) 

以上代码输出: 10

预期为: 11

我希望它是11，沿着路径0-2-9。但它选择的代价最低的路径是0-4-6。我是初学者，只学了4个月的代码。请帮帮我。

Answer 1

每次调用min_mtr都会返回从(0, 0)到(m, n)的最短路径。当您调用min_adj_val时，您的参数是对min_mtr的递归调用，这意味着您的函数所要做的就是保持到目前为止看到的最短路径长度，并将其添加到当前索引中。

一个更好的解决方案是编写一个贪婪的函数，它选择最小相邻索引，并将其值添加到运行的总计中，直到到达边界。