我正在处理一个组合优化问题,怀疑这是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个问题有何想法?
提前感谢!