3

所以我有一个基本上是这样的问题：我有一堆字符串，我想构造一个 DAG，使得每条路径都对应一个字符串，反之亦然。但是，我可以自由地任意排列我的字符串。字符的顺序无关紧要。我生成的 DAG 具有与之相关的成本。基本上，DAG 中一个分支的成本与其子路径的长度成正比。

例如，假设我有字符串 BAAA、CAAA、DAAA，并且我构造了一个 DAG 来表示它们而不对它们进行置换。我得到：

() -> (B, C, D) -> A -> A -> A

其中元组表示分支。

就我的目的而言，更便宜的表示是：

() -> A -> A -> A -> (B, C, D)

问题是：给定 n 个字符串，对字符串进行置换，使得对应的 DAG 成本最低，其中成本函数为：如果我们从源头开始深度遍历图，从左到右顺序，我们的节点总数访问，具有多样性。

所以第一个例子的成本是12，因为我们必须在遍历中多次访问A。第二个示例的成本是 6，因为在处理分支之前我们只访问 A 一次。

我感觉这个问题是NP Hard。这似乎是一个关于形式语言的问题，我对这些算法还不够熟悉，无法弄清楚我应该如何进行缩减。我本身不需要完整的答案，但如果有人能指出一类似乎相关的众所周知的问题，我将不胜感激。

4

1 回答 1

2

改写：

给定单词 w 1 , ..., w n ，计算w 1 , ..., x n的排列 x 1 , ..., x n以最小化存储 x 1 , ..., x n的树的大小。

假设一个无限大小的字母表，这个问题是 NP-hard 通过减少顶点覆盖。（我相信它可能是字母表大小的固定参数。）简化很容易：给定一个图形，让每个顶点都是它自己的字母，并为每个边创建一个两个字母的单词。

深度 0 处恰好有一个节点，深度 2 处的节点与边的数量一样多。深度一的可能节点集正是顶点覆盖的节点集。

于 2011-05-14T22:00:05.383 回答