12

我最近在一次技术面试中被问到这个问题。这是我的解决方案。http://pastebin.com/JMVHcfRq我犯了错误还是有更好的解决方案？

使用您选择的语言，在矩形数字网格中通过相邻的非重复单元格（包括对角线）查找最长的非递减序列的长度。该解决方案应处理任意宽度和高度的网格。
例如，在下面的网格中，可以追踪的一条合法路径（尽管不是最长的）是 0->3->7->9，其长度为 4。
8 2 4
0 7 1
3 7 9
路径只能连接相邻的位置（不能连接 8 -> 9）。通过跟踪路径 0->2->4->7->7->9 或 1->2->4->7->7->8，此示例的最长可能序列的长度为 6。
用您选择的语言编写一个方法，该方法将一个矩形的数字网格作为输入，并返回最长的此类序列的长度作为输出。

4

4 回答 4

6

您可以使用有向图对问题进行建模：

每个单元格都是图中的顶点，如果两个单元格 C i,j ,C k,m相邻且 C i,j < C k,m ，则 C i,j →C k,m有一条边。

现在你的问题是在这个图中找到最长的路径，但是这个图是有向无环图，因为问题说矩阵中没有重复的数字，“<”关系是反对称的。所以你的问题减少到在有向无环图中找到最长的路径，这很容易通过首先进行拓扑排序然后找到最长的路径。例如看到这个。

更新： 乍一看，我认为不可能有相等的邻居，但现在我看到是可能的，在上面的图形构造中，我们应该用 <= 替换 < 然后确定图形不是无环的，但问题仍然等于在此找到最长的路径图形。

P.S1：如果我对这个最长路径问题有任何多项式答案，我会把它带到这里，但可能通过这种问题分类更容易搜索它。

P.S2：正如评论中提到的mbeckish，最长路径问题在一般图中是NP-Hard，但我认为在这种特殊情况下可以在P中解决，但我现在没有确切的算法。

P.S3：我对它做了一些研究，我看到，网格图中的哈密顿路径是 NP-Complete，所以看来你的问题也是 NP-Complete （我现在没有减少但它们非常接近每个其他）。

于 2013-03-21T17:17:23.180 回答
2

在最坏的情况下，您的解决方案需要指数时间（矩阵大小）。

要加快速度，请使用记忆化或自下而上的动态编程。

于 2013-03-21T16:42:44.537 回答
1

还使用 n dijkstra 调用（反转它以找到最大路径），您可以在 O(n^3) 中解决它。使用最大堆可以将其降低到 0(n^2 log n)。构建图时，只为当前顶点 >= 的邻居创建边。

我尝试了拓扑排序，但我在图中发现了循环。需要检查我的代码。

于 2013-03-21T17:31:16.230 回答
0

在我看来，不测试的起始索引是那些包含在较长路径中的索引，其中包括所有索引允许的“下一个索引”的所有列表。

所以我首先为每个索引映射了允许的下一个索引，并将它们全部从起始索引组中删除以进行测试：

*Main> indexesIncludedInLongerPaths
[2,0,4,6,1,7,8] (numbers 4,8,7,3,2,7,9)

剩下两个指标需要测试：

*Main> indexesToTest
[3,5] (numbers 0,1)

之后，我从这些起始索引中搜索了所有路径并返回了最长的路径。

*Main> nonDesc matrix
[[1,2,4,7,7,9],[0,2,4,7,7,9]]


哈斯克尔代码：

import Data.List (nub, delete, sortBy, groupBy)

matrix = [8,2,4
         ,0,7,1
         ,3,7,9]::[Int]
m = 3
n = 3

neighbors index
  | index == 0           = [1,m]
  | index == m - 1       = [m-2, 2*m-1, 2*m-2]
  | index == m*n - 1     = [m*n-2, m*(n-1)-1, m*(n-1)-2]
  | index == m*(n-1)     = [m*(n-1)+1, m*(n-2), m*(n-2)+1]
  | index < m            = [index+1, index-1, index+m, index+m-1, index+m+1]
  | index > m*(n-1)      = [index+1, index-1, index-m, index-m-1, index-m+1]
  | mod index m == 0     = [index+1, index-m, index+m, index-m+1, index+m+1]
  | mod (index+1) m == 0 = [index-1, index-m, index+m, index-m-1, index+m-1]
  | otherwise            = [index+1, index-1, index-m, index+m
                           ,index-m+1, index-m-1, index+m+1, index+m-1]

indexesIncludedInLongerPaths = 
  nub $ concatMap (\x -> [a | a <- neighbors x
                              ,matrix!!x <= matrix!!a]) [0..length matrix-1]

indexesToTest = 
  foldr (\a b -> delete a b) [0..length matrix-1] indexesIncludedInLongerPaths

nonDesc matrix = solve indexesToTest [[]] where
  solve []     result = last $ groupBy (\a b -> length a == length b)
                        $ sortBy (\a b -> compare (length a) (length b)) 
                        $ map (\x -> map (\y -> matrix!!y) x) (concat result)
  solve (x:xs) result = 
    let paths = solve' [x] 
    in solve xs (paths:result)         
      where solve' y = 
              let b = [a | a <- neighbors (last y)
                                ,notElem a y
                                ,matrix!!(last y) <= matrix!!a]
              in if null b
                    then return y
                    else do a <- b
                            solve' (y ++ [a])
于 2013-03-22T15:05:48.840 回答