如何在Haskell中实现矩阵最小代价路径求解函数

首先明确路径规则为：从矩阵左上角出发，每次仅可向右或向下移动，最终到达右下角，需返回路径元素和最小的路径数组。

函数实现 #

首先导入需要的工具模块：

import Data.List (minimumBy)
import Data.Ord (comparing)

核心函数实现如下：

returnPossiblePaths :: [[Int]] -> [Int]
returnPossiblePaths [] = []
returnPossiblePaths mat = snd $ last $ last dp
  where
    rows = length mat
    cols = length $ head mat
    -- dp每个位置存储 (当前路径总代价, 路径数组)
    dp = [[calc i j | j <- [0..cols-1]] | i <- [0..rows-1]]
    calc 0 0 = (mat !! 0 !! 0, [mat !! 0 !! 0])
    -- 第一行只能从左边来
    calc 0 j = let (prevSum, prevPath) = dp !! 0 !! (j-1)
                   currVal = mat !! 0 !! j
               in (prevSum + currVal, prevPath ++ [currVal])
    -- 第一列只能从上面来
    calc i 0 = let (prevSum, prevPath) = dp !! (i-1) !! 0
                   currVal = mat !! i !! 0
               in (prevSum + currVal, prevPath ++ [currVal])
    -- 其他位置选上方或左方代价更小的路径
    calc i j = let (upSum, upPath) = dp !! (i-1) !! j
                   (leftSum, leftPath) = dp !! i !! (j-1)
                   currVal = mat !! i !! j
                   (bestSum, bestPath) = minimumBy (comparing fst) [(upSum, upPath), (leftSum, leftPath)]
               in (bestSum + currVal, bestPath ++ [currVal])

测试验证 #

用示例矩阵测试：

testMat :: [[Int]]
testMat = [[6,9,3],[2,5,7]]

main :: IO ()
main = print $ returnPossiblePaths testMat

运行输出为[6,2,5,7]，和预期结果一致。

方案优势 #

• 时间复杂度为O(mn)（m为矩阵行数、n为列数），远优于枚举所有路径的组合级时间复杂度，矩阵规模较大时性能优势明显
• 全程采用纯函数式写法，无可变状态，符合Haskell的函数式编程特性
• 逻辑清晰，通过递推计算每个位置的最优解，最终直接得到全局最优路径

内容的提问来源于stack exchange，提问作者Andrew Viera