在有向无环图中寻找回文的动态规划算法

Question

问题如下：给定一个有向无环图，其中每个节点都用一个字符标记，找到图中所有节点的最长路径形成回文。

我最初想到的解决方案是简单地枚举图中的所有路径。这有效地生成了一堆字符串，然后我们可以在这些字符串上应用 Manacher's algorithm 来查找所有最长的回文。然而，这似乎并不那么有效，因为图中路径的数量是节点数量的指数。

然后我开始考虑直接在图上使用动态规划，但我的问题是我不知道如何构建我的 "dynamic programming array"。我最初的尝试是使用一个二维布尔数组，其中 array[i][j] == true 意味着节点 i 到节点 j 是一个回文，但问题是从 i 到 j 可能有多个路径。

我已经被这个问题困扰了很长一段时间，现在我似乎无法弄清楚，任何帮助将不胜感激。

Answer 1

Manacher 算法的线性时间技巧依赖于这样一个事实：如果您知道以字符 15 为中心的最长回文长度为 5（字符 13-17），并且有一个以节点 19 为中心的长度为 13 的回文（字符 13-25），那么您可以跳过计算以字符 23 为中心的最长回文 (23 = 19 + (19 - 15))，因为您知道它只是以字符 15 为中心的回文的镜像。

对于 DAG，您没有那种保证，因为回文可以在任何方向发生，而不仅仅是向前和向后。但是，如果你有一个从节点m到节点n的候选回文路径，你是否可以将该字符串扩展到更长的回文不依赖于m和[=之间的路径12=]，但仅限于 m 和 n（以及图表本身）。

因此，我会这样做：

首先，sort the graph nodes topologically，所以你有一个节点索引数组s[]，并且从s[i]到s[j]有一条边意味着i < j.

我还假设您建立了一个逆数组或散列结构 sinv[]，使得 s[sinv[j]] == j 和 sinv[s[n]] == n 对于 [=25] 中的所有整数 j =] 和所有节点索引 n.

此外，我假设您有函数 graphPredecessors、graphSuccessors 和 graphLetter，它们采用节点索引和 return 上的前辈列表图形、后继者列表或该节点处的字母。

然后，创建一个二维整数数组，大小为 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;
    }
  }
}

然后在0..nodeSize-1中求x的r[x][x]的最大值，s[lft]到[=]的r[lft][rgt]的最大值47=]。将该最大值称为 M，并假设您在位置 [i][j] 找到了它。每个这样的 i、j 对将代表最长回文路径的中心。只要 M 大于 1，您就可以通过在 graphPredecessors(s[i]) 中找到一个 pred 并在 graphSuccessors(s[j]) 中找到一个 succ 来扩展每个中心那r[sinv[pred]][sinv[succ]] == M - 1（回文现在是pred->s[i]->s[j]->succ）。然后，您可以通过找到 r 值为 M - 2 的适当索引来扩展它，等等，当您到达 r 中的值为 1 的位置时停止。 =69=]

我认为这个算法总体上以 O(V^2 + E^2) 的运行时间结束，但我不完全确定这一点。

在有向无环图中寻找回文的动态规划算法

Dynamic programming algorithm to find palindromes in a directed acyclic graph

graph-theory

dynamic-programming

palindrome

graph-algorithm