Fre*_*red 5 algorithm optimization np-complete mathematical-optimization combinatorics
我正在研究一个组合优化问题,我怀疑它是NP难的,遗传算法在我们的数据集中运行良好.我们是一个研究小组,并计划在我们的领域(不是数学或CS)发表我们的结果,我想在发送稿件进行审核之前探讨NP难题.
有两个主要问题:
1)我想知道是否已经研究了这个特定的优化问题.我已经大量搜索了灯,但没有看到任何完全一样的东西.
2)如果问题还没有被研究过,我可能会在进行还原性证明方面采取一些措施,并且希望能够提供一些好的NP-complete候选者来进行减少.
该问题可以用两种方式描述,作为子序列变体,以及作为二分图问题.
在后续的味道中,我想找到允许排列的"放松"子序列,并优化以最小化排列计数.例如:(.=任何其他字符)
查询:abc,目标:.. babc,结果:abc(正常子序列)
查询:abc,目标:.. baca,结果:bac(带有一个排列的子序列)
二分公式是一个匹配问题或线性分配问题,图分为查询字符节点和目标字符节点.边缘将查询字符连接到目标字符,这样每个查询字符到目标字符只有一条边.目标函数是最小化边缘交叉的数量(在点亮时也称为"交叉数").这类似于二分图布局算法,它重新排序节点放置以最小化边缘交叉,但我的问题要求两个节点顺序保持固定.
有关问题1或2的专家的任何想法？
提前致谢!