algorithm - 找到优先级函数/字母顺序的极值

Question

我们有一个元素数组 a1,a2,...aN来自字母表 E .假设 |N| >> |E| .

对于字母表中的每个符号，我们定义了一个唯一的整数优先级 = V(sym) .让我们定义 V{i} := V(symbol(ai))为简单起见。

我怎样才能找到优先级函数 V:

Count(i)->MAX | V{i} < V{i+1}

换句话说，我需要找到位置数 i 的字母表的优先级/排列，满足条件V{i}<V{i+1} , 是最大值。

Edit-1:请仔细阅读。我得到了一个数组 ai任务是产生一个函数 V .它不是关于使用优先级函数对输入数组进行排序。

Edit-2:例子

E = {a,b,c}; A = 'abcab$'; (这里$=人工终止符号，V{$}=+无穷大)

最佳优先级函数之一是:V{a}=1,V{b}=2,V{c}=3 ，它为我们提供了数组元素之间的以下符号:a<b<c>a<b<$ ，导致总共 5 个符号中有 4 个“<”符号。

Answer 1

如果元素不能绑定(bind)优先级，这将是微不足道的。只需按优先级排序。但你们可以有同等的优先权。

我会先按优先级对字母表进行排序。然后我会提取最长的上升子序列。那是你的答案的开始。从剩下的部分中提取最长的上升序列。将其附加到您的答案中。重复提取过程，直到提取出整个字母表。

我相信这会给出最佳结果，但我还没有尝试证明这一点。如果它不是完美的最优，它仍然会很好。

现在我想我理解了这个问题，我可以告诉你，没有好的算法可以解决它。

要了解这一点，让我们首先构造一个有向图，其顶点是您的元素，其边表示一个元素紧接在另一个元素之前的次数。您可以通过删除足够多的边以获得有向无环图来创建优先级函数，使用边创建部分有序集，然后添加顺序关系直到您拥有完整的线性顺序，您可以从中轻松获得优先级函数。一旦您确定了要丢弃的边，所有这些都非常简单。相反，鉴于该有向图和您的最终优先级函数，很容易找出您必须决定删除哪一组边。

因此，您的问题完全等同于找出您需要从a有向图中删除以获得a有向无环图的最小边集。然而作为http://en.wikipedia.org/wiki/Feedback_arc_set说，这是一个已知的 NP 难题，称为最小反馈弧集。 开始更新 因此，对于您可以想出的图形，不太可能有好的算法。 结束更新

如果您需要在实践中解决它，我建议您使用某种贪心算法。它并不总是正确的，但通常会在合理的时间内给出一些合理的结果。

更新:白痴是对的，我没有证明 NP-hard。然而，有充分的启发式理由相信该问题实际上是 NP-hard 问题。查看评论了解更多信息。