Алгоритм динамического программирования для поиска палиндромов в ориентированном ациклическом графе

Question

Проблема заключается в следующем: по заданному ациклическому графу, где каждый узел помечен символом, найдите все самые длинные пути узлов в графе, которые образуют палиндром.

Исходное решение, которое яМысль о том, чтобы просто перечислить все пути в графе.Это эффективно генерирует набор строк, к которым мы можем затем применить алгоритм Манахера , чтобы найти все самые длинные палиндромы.Однако это не кажется эффективным, поскольку количество путей в графе экспоненциально по числу узлов.

Тогда я начал думать об использовании динамического программирования непосредственно на графе, но моя проблема заключается в том, чтоЯ не могу понять, как структурировать мой «массив динамического программирования».Моя первоначальная попытка состояла в том, чтобы использовать 2d логический массив, где array [i] [j] == true означает, что узел i к узлу j является палиндромом, но проблема в том, что может быть несколько путей от i до j.

Я застрял в этой проблеме довольно долгое время, и теперь я не могу понять, любая помощь будет признательна.

Answer 1

Линейный трюк алгоритма Манахера основан на том факте, что если вы знаете, что самый длинный палиндром с центром в символе 15 имеет длину 5 (символы 13-17), а палиндром центрируется в узле 19 длины 13 (символы)13-25), тогда вы можете пропустить вычисление самого длинного палиндрома с центром в символе 23 (23 = 19 + (19 - 15)), потому что вы знаете, что это будет просто зеркало того, который центрирован в символе 15.

С DAG у вас нет такой гарантии, потому что палиндромы могут двигаться в любом направлении, а не только вперед и назад.Однако, если у вас есть предполагаемый путь палиндрома от узла m до узла n, то, можете ли вы расширить эту строку до более длинного палиндрома, не зависит от пути между m и n, а только от m и n (и сам граф).

Поэтому я бы сделал следующее:

Сначала отсортируем узлы графа топологически , чтобы выиметь массив s[] индексов узлов, а наличие ребра от s[i] до s[j] подразумевает, что i < j.

Я также предполагаю, что вы создаете обратный массив или хеш-структуруsinv[] такое, что s[sinv[j]] == j и sinv[s[n]] == n для всех целых чисел j в 0..nodeCount-1 и всех индексов узлов n.

Кроме того, я предполагаю, что у вас есть функции graphPredecessors,graphSuccessors и graphLetter, которые берут индекс узла и возвращают список предшественников на графе, список преемников или букву в этом узле, соответственно.

Затем создайте двумерныймассив целых чисел размером nodeCount на nodeCount, называемый r.Когда r[i][j] = y и y> 0, это будет означать, что если существует путь палиндрома от преемника s[i] к предшественнику s[j], то этот путь можно расширить, добавив s[i] кспереди и s[j] сзади, и что расширение может быть продолжено на y больше узлов (включая s[i] и s[j]) в каждом направлении:

for (i=0; i < nodeCount; i++) {
  for (j=i; j < nodeCount; j++) {
    if (graphLetter(s[i]) == graphLetter(s[j])) {
      r[i][j] = 1;
      for (pred in graphPredecessors(s[i])) {
        for (succ in graphSuccessors(s[j])) {
          /* note that by our sorting, sinv[pred] < i <= j < sinv[succ] */
          if (r[sinv[pred]][sinv[succ]] >= r[i][j]) {
            r[i][j] = 1 + r[sinv[pred]][sinv[succ]];
          }
        }
      }
    } else {
      r[i][j] = 0;
    }
  }
}

Затем найдите максимальное значениеr[x][x] для x в 0..nodeSize-1 и r[lft][rgt], где есть ребро от s[lft] до s[rgt].Назовите это максимальное значение M и скажите, что вы нашли его в местоположении [i][j].Каждая такая пара i, j будет представлять собой центр самого длинного пути палиндрома.Пока M больше 1, вы затем расширяете каждый центр, находя pred в graphPredecessors(s[i]) и succ в graphSuccessors(s[j]), такие что r[sinv[pred]][sinv[succ]] == M - 1 (палиндром теперь pred-> s[i] -> s[j] -> succ).Затем вы расширяете его, находя соответствующий индекс со значением r, равным M - 2 и т. Д., Останавливаясь, когда достигаете точки, где значение в r равно 1.

. Я думаю, что этоалгоритм в целом заканчивается временем выполнения O(V^2 + E^2), но я не совсем уверен в этом.