5

我正在研究一个我怀疑是 NP-hard 的组合优化问题，并且遗传算法在我们的数据集上运行良好。我们是一个研究小组，并计划在我们的领域（而不是数学或 CS）发表我们的结果，我想在将手稿送审之前探索 NP 难题。

有两个主要问题：

1）我想知道是否研究过这个特定的优化问题。我已经仔细搜索了点燃，但没有看到任何完全相同的东西。

2）如果这个问题还没有被研究过，我可能会尝试做一个可还原性证明，并且想要一些关于还原的良好 NP-完全候选者的指针。

这个问题可以用两种方式来描述，一个子序列变体，一个二分图问题。

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

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

查询：abc，目标：..baca，结果：bac（一个排列的子序列）

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

专家对问题 1 或 2 有何想法？

提前致谢！

4

4 回答 4

1

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

于 2014-01-03T02:48:17.560 回答
1

只是一些想法：它是否相当于找到对数组进行排序所需的最小交换数（MIN-SBR）？如果是，这是NP-Hard。

（顺便说一句，你在做类似的事情吗？）

于 2010-10-14T00:44:42.900 回答
0

The problem with "word problem" should be harder, right? – J-16 SDiZ 14

Yes, having multiple occurrences of the char in the target seems to make my problem harder than MIN-SBR, so from that angle my problem would be at least as hard as NP-complete. On the other hand, I'm not yet clear on how their central notion of block reversals would affect my claim of NP-completeness.

I sure would be nice to know whether my optimization can be solved in polynomial time. Put another way, it sure would be embarrassing if a reviewer came back with five lines of pseudocode that finds the global maximum in O(n)..

于 2010-10-14T19:13:29.687 回答
0

那么，查询：abc 目标：..cbaa 结果：cba，是三个排列（根据您对术语的使用）吗？如果是这样，那么也许您的意思是换位而不是排列。换位是两个相邻字符的交换。

好问题。我们对 Query -> Target 的映射感兴趣，它的交叉点 越少越好。这在很大程度上是在原始帖子中提到二分边缘交叉的动机。或者，您可以考虑在映射上最大化排名统计量，例如 Spearman 的 Rho。

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

典型查询：100，典型目标：1000。组合起来，这是一个巨大的解空间。

于 2010-10-15T16:03:33.357 回答