所以我有一个基本上是这样的问题:我有一堆字符串，我想构造一个 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。这似乎是一个关于形式语言的问题，我对这些算法还不够熟悉，无法弄清楚我应该如何进行缩减。我本身不需要完整的答案，但如果有人能指出一类似乎相关的众所周知的问题，我将不胜感激。
最佳答案
换句话说:
给定单词 w1, …, wn，计算 w1 的排列 x1, … , xn of wn 以最小化存储 x1, …, xn 的 trie 的大小。
假设一个无限大小的字母表，这个问题是 NP-hard 通过减少顶点覆盖。 (我相信它在字母表的大小上可能是可处理的固定参数。)归约很简单:给定一个图，让每个顶点都是它自己的字母，并为每条边创建一个两个字母的单词。
深度为零的节点只有一个，深度为二的节点的数量与边的数量一样多。深度一的可能节点集恰好是顶点覆盖的节点集。
关于algorithm - 这在计算复杂性方面有多难？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6004725/