Техническое интервью: самая длинная не снижающаяся подпоследовательность в матрице MxN

Ответ 1

Вы можете моделировать свою проблему с помощью ориентированного графика:

Каждая ячейка является вершиной в вашем графике, и есть край от C _{i, j} → C _{k, m}, если две ячейки C _{i, j}, C _{k, m} являются смежными и C _{i, j} < С <суб > к, тсуб > .

Теперь ваша проблема заключается в поиске самого длинного пути на этом графике, но этот график представляет собой ациклический граф с прямой арифметикой, поскольку, как указывает проблема, в матрице не повторяется число "<" отношение антисимметричное. Таким образом, ваша задача сводится к поиску длинного пути в ациклическом графике, что легко, сначала сделав топологическую сортировку, а затем найдя самый длинный путь. например, this.

Update: На первый взгляд я думал, что невозможно иметь равных соседей, но теперь я вижу, возможно. В приведенной выше конструкции графика мы должны заменить < с < =, тогда верный график не является ациклическим, но проблема остается равной самому длинному пути на этом графике.

P.S1: Если у меня есть какой-либо полиномиальный ответ для этой проблемы с самым длинным путём, я приведу его здесь, но, возможно, этой классификацией проблемы проще искать по ней.

P.S2: как mbeckish, упомянутый в комментариях, самая длинная проблема пути NP-Hard в общем графике, но я думаю, что в этом специальном случае можно решить в P, но сейчас у меня нет точного алгоритма.

P.S3: Я немного разбираюсь в этом, я видел, Гамильтонов путь в grid-графике NP-Complete, так кажется ваша проблема также NP-Complete (сейчас у меня нет сокращения, но они очень близки друг к другу).

Ответ 2

Ваше решение занимает экспоненциальное время (в размере матрицы) в худшем случае.

Чтобы ускорить его, используйте memoization или снизу вверх динамическое программирование.

Ответ 3

Кроме того, используя n dijkstra calls (переверните его, чтобы найти максимальный путь), вы можете решить его в O (n ^ 3). Использование максимальной кучи может снизить ее до 0 (n ^ 2 log n). При построении графика создавайте только края для соседей, которые >= для текущей вершины.

Я попробовал топологическую сортировку, но нашел графики на графике. Необходимо проверить мой код.

Ответ 4

Мне кажется, что начальные индексы, которые не тестируются, это те, которые включены в более длинные пути, которые включают в себя все списки разрешенных "следующих индексов" для всех индексов.

Итак, я сначала сопоставил допустимые следующие индексы для каждого индекса и удалил все из них из группы начальных индексов для проверки:

*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]]

Код Haskell:

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])