NP类问题的共性与个性探索

在现实生活中，有大量的NP类问题。它一项被广泛研究的课题，已经吸引了众多的科学工作者。到目前为止仍存在着许多悬而未决的问题。最短超串问题（Shortest Superstring）是一个较典型的NP完全问题，在计算分子生物学和数据压缩中有着重要应用。本次研究将以最短超串问题为中心，展开对NP类问题的共性与个性的研究。目前NP类问题的求解方法很多，而最短超串问题的求解方法单一，主要集中在贪心法。本次研究想试探一下包括局域搜索法在内的一些启发式方法对最短超串问题是否有效，并试图提出一些更有效的NP类问题的求解法。在最短超串问题求解法中，目前最好的性能比(近似解与最优解之比)被证明为2.5，但人们猜测贪心法的性能比为2。这一问题至今没有人解决。本次研究试图挑战这一难题。