这个组合优化问题NP-hard？

Question

我工作的组合优化问题，我怀疑是NP难，遗传算法一直与我们的数据集一直工作。我们是一个研究小组，并计划在我们的领域发布我们的研究成果（而不是数学或CS），并且我希望在发送手稿供审阅之前探索NP难题。

主要有两个问题：

1）我想知道这个特别的优化问题，是否进行了研究。我已经严重搜查了点燃，但没有看到任何完全相同的东西。 2）如果这个问题没有被研究过，我可能会在做一个可证明性证明的时候做出一些尝试，并且想要一些指向NP完全候选者的指针。

该问题可以用两种方式描述，作为子序列变体，以及作为二部图问题。

在子序列风格中，我想找到一个“宽松”的子序列，允许排列，并优化以最小化排列计数。例如：（=任何其他炭。）

查询：ABC，目标：..babc，结果：ABC（正常亚序列）

查询：ABC，目标：..baca，结果：BAC（亚一个排列组合）

二部分公式是一个匹配问题或线性分配问题，将图划分为查询字符节点和目标字符节点。边将查询字符连接到目标字符，从而每个查询字符到目标字符恰好有一条边。目标函数是最小化边缘交叉点的数量（在点亮中也称为“交叉点数”）。这与二重图形布局算法类似，它重新排列节点位置以最小化边缘交叉，但是我的问题要求两个节点顺序保持固定。

有关问题1或2的专家的任何想法？

提前致谢！

Answer 1

只是一些想法：它在某种程度上等同于找到排序数组（MIN-SBR）所需的最小交换次数吗？如果是的话，这是NP-Hard。

（顺便说一句，你工作的东西similar to this？）

Answer 2

与 “字问题” 的问题应该更加努力，对不对？ - J-16 SDiZ 14

是的，在目标中出现多次char字符似乎使我的问题比MIN-SBR更难，所以从这个角度来看，我的问题至少与NP完全一样困难。另一方面，我还不清楚他们的中心概念是否会影响我对NP完整性的主张。

我当然很高兴知道我的优化是否可以在多项式时间内解决。换句话说，如果一个评论者回来了五行伪代码，在O（n）中找到全局最大值，那么肯定会感到尴尬。

Answer 3

要piccolbo：

如果你没有在数学或CS出版，一个NP完全性结果将是不相关的，只是刺激生物学家或MD做检讨。到过那里。

你打赌。主要报告将基于湿润的结果，但我们可能会选择更具跨学科性的期刊。此外，想知道NP-ness的部分原因是我自己的熏陶。如果完全没有道理，那么使用遗传算法会很慢，并且如果有办法在多项式时间内找到保证的全局最大值。目前，GA正在寻找好的解决方案，但很难知道它是否找到最佳解决方案。

你是什么意思排列？一个只涉及两个字符？或者只有两个相邻的？我认为在一般意义上的排列允许您重新排列整个字符串，但问题变得微不足道？

它是目标字符串中的任意排列数，并且排列的数量最小化（即双分式中的边交叉）是目标函数。排列可以在任何地方，并且它们是独立分布的，所以邻接会偶尔发生（偶尔）。查询和目标字符串的排序是固定的，所以我不能做任何重新排列。

如果我证明它是NP难的，我能得到合着吗？

让我们来看看证明:-)

Answer 4

会，查询：ABC目标：..c.b.a.a结果：CBA，是三个置换（根据您使用的术语）呢？如果是这样，那么你的意思可能是换位而不是排列。转换是交换两个相邻的字符。

好问题。我们感兴趣的是来自Query - > Target的映射，尽可能少的有穿越。这是在原始帖子中提及双边边缘交叉口的动机。或者，您可以考虑在映射上最大化排名统计，如Spearman的Rho。

此外，出于好奇，查询/目标中有多少个唯一字符？ - 贾斯汀皮尔18

典型查询：100，典型目标：1000.组合，这是一个巨大的解决方案空间。

Answer 5

我不认为这是NP难。参见Pevzner和Hannehali的工作。想到的一篇论文题为“从白菜到萝卜”。这个想法是找出从一个字符串到另一个字符串的最小反转次数。他们有一个多时间算法。