我正在处理一个组合优化问题，怀疑这是NP难问题，并且遗传算法在我们的数据集上表现良好。我们是一个研究小组，计划在我们的领域（不是数学或计算机科学）发表我们的结果，我想在将手稿提交审查之前探索NP难问题。
有两个主要问题：
1）我想知道是否已经研究了这个特定的优化问题。我已经仔细搜索了文献，但没有看到完全相同的内容。
2）如果该问题尚未研究，我可能会尝试进行可约简性证明，并希望获得一些指向好的NP完全候选项的指针。
该问题可以用两种方式描述，作为子序列变体和二分图问题。
在子序列变体中，我希望找到一个“放松”的子序列，允许排列，并优化以最小化排列计数。例如：(. = 任何其他字符)
查询：abc，目标：..b.a.b.c.，结果：abc（正常子序列）
查询：abc，目标：..b.a.c.a.，结果：bac（具有一个排列的子序列）
二分图公式是匹配问题或线性分配问题，其中图被分成查询字符节点和目标字符节点。边连接查询字符和目标字符，使得每个查询字符都恰好有一条边连接到目标字符。目标函数是最小化边交叉的数量（在文献中也称为“交叉数”）。这类似于二分图布局算法，可以重新排列节点位置以最小化边交叉，但我的问题要求两个节点顺序保持不变。
请问专家们对第1或第2个问题有何想法？
提前感谢！
有两个主要问题：
1）我想知道是否已经研究了这个特定的优化问题。我已经仔细搜索了文献，但没有看到完全相同的内容。
2）如果该问题尚未研究，我可能会尝试进行可约简性证明，并希望获得一些指向好的NP完全候选项的指针。
该问题可以用两种方式描述，作为子序列变体和二分图问题。
在子序列变体中，我希望找到一个“放松”的子序列，允许排列，并优化以最小化排列计数。例如：(. = 任何其他字符)
查询：abc，目标：..b.a.b.c.，结果：abc（正常子序列）
查询：abc，目标：..b.a.c.a.，结果：bac（具有一个排列的子序列）
二分图公式是匹配问题或线性分配问题，其中图被分成查询字符节点和目标字符节点。边连接查询字符和目标字符，使得每个查询字符都恰好有一条边连接到目标字符。目标函数是最小化边交叉的数量（在文献中也称为“交叉数”）。这类似于二分图布局算法，可以重新排列节点位置以最小化边交叉，但我的问题要求两个节点顺序保持不变。
请问专家们对第1或第2个问题有何想法？
提前感谢！