我正在研究一个组合优化问题，我怀疑这是 NP-hard，遗传算法已经很好地处理了我们的数据集。我们是一个研究小组，计划在我们的领域（而不是数学或 CS）发布我们的结果，我想在发送手稿进行之前探索 NP-hard 问题。
有两个主要问题：
1）我想知道这个特定的优化问题是否已经研究过。我已经大量搜索了 lit，但没有看到任何完全相同的东西。
2）如果问题还没有被研究，我可能会在做一个可约性证明的裂缝，并希望一些指针，以良好的 NP 完全候选人的减少。
该问题可以用两种方式描述，即子序列变体和二部图问题。
在子序列风味中，我想找到一个允许置换的“宽松”子序列，并进行优化以最小化置换计数。例如：（。= 任何其他 char）
查询：abc，目标：..b.a.b.c.，结果：abc（正常子序列）
查询：abc，目标：..b.a.c.a.，结果：bac（具有一个排列的子序列）
二分公式是一个匹配问题或线性分配问题，图被划分为查询字符节点和目标字符节点。边将查询字符连接到目标字符，这样从每个查询字符到目标字符只有一条边。目标函数是最小化边交叉的数量 (在点亮中也称为“交叉数量”)。这类似于二分图布局算法，该算法重新排序节点位置以最小化边交叉，但我的问题需要
专家们对问题 1 或 2 有什么想法吗？
提前谢谢！
只是一些想法：它是否以某种方式等同于找到排序数组（MIN-SBR）所需的最小交换数？如果是，这是NP-Hard。
（顺便说一句，你在做什么similar to this？）
我不认为这是 NP-hard。请参阅 Pevzner 和 Hannehali 的工作。想到的一篇论文标题为“从卷心菜到萝卜”。这个想法是找到从一个字符串到另一个字符串的最小反转数。他们对此有一个 polytime 算法。
“单词问题”的问题应该更难，对吗？-J-16 SDiZ 14
是的，在目标中多次出现 char 似乎使我的问题比 MIN-SBR 更难，所以从这个角度来看，我的问题至少与 NP-complete 一样难。
我肯定会很高兴知道我的优化是否可以在多项式时间内解决。换句话说，如果一个审阅者带着五行伪代码回来找到 O（n）中的全局最大值，那肯定会很尴尬。
Would,Query:abc Target:..c.b.a.a Result:cba,be three permutations (as per your use of the term) then?If so,then maybe you mean transpositions rather than permutations.A transposition is the swapping of two adjacent characters
好问题。我们对来自 Query-& gt;Target 的映射感兴趣，该映射具有尽可能少的crossings。这在很大程度上是在原始帖子中提到二分边 crossings 的动机。或者，您可以考虑在映射上最大化秩统计，如 Spearman 的 Rho。
另外，出于好奇，查询 / 目标中有多少个唯一字符？-Justin Peel 18
典型查询：100，典型目标：1000。组合起来，这是一个巨大的解决方案空间。
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（63条）