algorithm - 找到极端高阶元素关系的优先级函数/字母顺序

Question

这个问题是对 following one 的扩展.不同之处在于，现在我们要优化的函数将在元素之间具有更高阶的关系:

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

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

任务是找到一个优先级函数 V，其中:

Count(i)->MIN |   V{i} > V{i+1} <= V{i+2}

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

所需的最大抽象(对我而言低优先级)。我猜曾经的解决方案模型为initial question扩展到涵盖这一部分的第一部分，将其扩展得更远(见下文)会更容易。

给定一个大小为 MxK 的符号矩阵 B(基本上 B[i,j] 来自集合 {<,>,<=,>=})，找到优先级函数 V，其中:

Sum(for all j in range [1,M]) {Count(i)}->EXTREMUM | V{i} B[j,1] V{i+1} B[j,2] ... B[j,K] V{i+K}

举个例子，求优先级函数V , 其中 i 的数量, 满足 V{i}<V{i+1}<V{i+2}或 V{i}>V{i+1}>V{i+2} , 是最小值。

Answer 1

我的直觉是这个问题的所有变体都将被证明是 NP 难的。所以我会开始寻找能产生合理答案的启发式方法。这可能涉及一些试验和错误。

一个简单的方法是写下一个可能的排列。然后尝试可能的交换，直到达到局部最小值。多试几次，选出最佳答案。

模拟退火提供了此方法的更复杂版本，请参阅 http://en.wikipedia.org/wiki/Simulated_annealing以获得描述。可能需要进行一些实验才能找到一组似乎收敛得相对较好的参数。

另一个想法是寻找遗传算法。基于快速的谷歌搜索，看起来标准的方法是尝试将 NP 完全问题转化为 SAT 问题，然后对该问题使用遗传算法。这种方法需要以某种合理的方式将其转化为 SAT 问题。不幸的是，我不清楚如何进行这种减少。事实上，在您拥有的第一个版本中，您的问题与经典的 NP-hard 问题密切相关。它被标记为 NP-hard 而不是 NP-complete 的事实证明人们还没有找到将其转化为 SAT 问题的好方法。因此，如果如何将简单版本转化为 SAT 问题并不明显，那么您也不太可能将难题转化为难题。

但是您仍然可以尝试遗传算法的一些变体。变异非常简单，只需交换一些元素即可。组合元素的一种方法是采用 3 种排列并使用快速排序找到组合，如下所示:采用随机主元，然后使用“多数获胜”将元素分为更大和更小。以相同的方式对每一半进行排序。

很抱歉，我不能只给你一个方法然后说，“这应该行得通。”你有一个看起来像开放式研究项目，我能做的最好的事情就是给你一些想法，告诉你一些你可以尝试的事情，这些事情可能会运作得相当好。