algorithm - 这个组合优化问题是 NP 难的吗？

Question

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

主要有两个问题:

1) 我想知道这个特定的优化问题是否已经被研究过。我已经大量搜索了 lit 但没有看到任何完全相同的东西。

2) 如果这个问题还没有被研究过，我可能会尝试做一个可还原性证明，并希望得到一些关于好的 NP 完全候选者的建议以进行还原。

该问题可以用两种方式描述，一种是子序列变体，另一种是二分图问题。

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

查询:abc，目标:..b.a.b.c.，结果:abc(正常子序列)

查询:abc，目标:..b.a.c.a.，结果:bac(一个排列的子序列)

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

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

提前致谢!

Answer 1

只是一些想法:它是否在某种程度上等同于找到对数组进行排序所需的最小交换数量 (MIN-SBR)？如果是，这是 NP-Hard .

(顺便说一句，你在做什么 similar to this 吗？)