查找极端高阶元素关系的优先功能/字母顺序 [英] Find the priority function / alphabet order for extreme higher order elements relation

问题描述

此问题是下列操作之一的扩展。所不同的是，现在我们的函数来优化将具有元件之间高阶关系：

This question is an extension to the following one. The difference is that now our function to optimize will have higher order relations between elements:

我们有元素 A1，A2，... AN 从字母电子的数组。假设 | N | ＆GT;＆GT; | E |。

We have an array of elements a1,a2,...aN from an alphabet E. Assuming |N| >> |E|.

有关字母表中的每个符号，我们定义了一个唯一的整数优先级= V（符号）。让我们来定义 V {I}：= V（符号（AI））的简单

For each symbol of the alphabet we define an unique integer priority = V(sym). Let's define V{i} := V(symbol(ai)) for the simplicity.

的任务是找到一个优先级功能，V代表其中：

The task is to find a priority function V for which:

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

换句话说，我需要找到字母表中的优先级/置换为其位置数我，满足条件 V {我}＆GT; V {I + 1}＆LT; = V {I + 2} ，最小

所需最大的抽象（对我来说低优先级）。我猜想一旦溶液模型href="http://stackoverflow.com/q/4959719/607131">最初的问题是扩大到包括这一个的第一部分

Maximum required abstraction (low priority for me). I guess once the solution model for the initial question is extended to cover the first part of this one, extending it farther (see below) will be easier.

鉴于大小的MXK（标志B中的矩阵基本上 B [I，J] 是集 {＆LT;，＆gt;中＆LT; =，＆GT; =} ），找到优先功能V代表其中：

Given a matrix of signs B of size MxK (basically B[i,j] is from the set {<,>,<=,>=}), find the priority function V for which:

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 ，对其中的数我，满足 V {I}＆LT; V {I + 1}＆LT; V {I + 2} 或 V {I}＆GT; V {I + 1}＆GT ; V {I + 2} ，最小

As an example, find the priority function V, for which the number of i, satisfying V{i}<V{i+1}<V{i+2} or V{i}>V{i+1}>V{i+2}, is minimum.

推荐答案

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

My intuition is that all variations on this problem will prove to be NP-hard. So I'd begin looking for heuristics that produce reasonable answers. This may involve some trial and error.

有一个简单的方法是写一个可能的排列。然后尝试可能互换，直到你到达一个局部最小。试了几次，并挑选了最好的答案。

A simplistic approach is to write down a possible permutation. And then try possible swaps until you've arrived at a local minimum. Try several times, and pick the best answer.

模拟退火提供了这种方法的一个更复杂的版本，请参阅 http://en.wikipedia.org/维基/ Simulated_annealing 的描述。这可能需要一些实验来寻找一组参数，似乎收敛比较好。

Simulated annealing provides a more sophisticated version of this approach, see http://en.wikipedia.org/wiki/Simulated_annealing for a description. It may take some experimentation to find a set of parameters that seems to converge relatively well.

另一个想法是寻找一个遗传算法。基于快速谷歌搜索，它看起来像标准的方式做到这一点是要设法把一个NP完全问题转化为SAT问题，然后用遗传算法上的问题。这种方法需要把这个变成一个SAT问题在某种合理的方式。遗憾的是并不明显，我怎么一会去这样做降低。事实上，在你拥有的第一个版本，你的问题是紧密相连的经典NP问题。它标记为NP难的，而不是NP完全的事实，证据，人们还没有找到将其改造成一个SAT问题的好办法。所以，如果这不是明摆着如何将简单的版本到SAT的问题，那么你就不太可能要么转换的难题。

Another idea is to look for a genetic algorithm. Based on a quick Google search it looks like the standard way to do this is to try to turn an NP-complete problem into a SAT problem, and then use a genetic algorithm on that problem. This approach would require turning this into a SAT problem in some reasonable way. Unfortunately it is not obvious to me how one would go about doing this reduction. Indeed in the first version that you had, your problem was closely connected to a classic NP-hard problem. The fact that it is labeled NP-hard rather than NP-complete is evidence that people haven't found a good way to transform it into a SAT problem. So if it isn't obvious how to turn the simple version into a SAT problem, then you are unlikely to convert the hard problem either.

但你仍然可以尝试基于遗传算法的一些变化。突变是pretty的简单，只要将身边的一些元素。结合元素的一种方法是采取3排列，并使用快速排序，找到组合如下：采取随机支点，然后用多数获胜来斗元素融入更大和更小。排序每个半以相同的方式

But you could still try some variation on genetic algorithms. Mutation is pretty simple, just swap some elements around. One way to combine elements would be to take 3 permutations and use quicksort to find the combination as follows: take a random pivot, and then use "majority wins" to bucket elements into bigger and smaller. Sort each half in the same way.

我很抱歉，我不能只是给你一个办法，说：这应该工作。你有什么看起来像一个开放式的研究项目，并且尽我所能做的就是给你一些想法的事情，你可以尝试可能工作得非常好。

I'm sorry that I can't just give you an approach and say, "This should work." You've got what looks like an open-ended research project, and the best I can do is give you some ideas about things you can try that might work reasonably well.

这篇关于查找极端高阶元素关系的优先功能/字母顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！