现代信息学问题分为两类:一类是存在有效算法的所谓P类问题,另一类是目前尚未找到有效算法的所谓NPC问题。为了解决后一类问题,我们引进了非最优化算法的概念。本节将对NPC的概念和提出非最优化算法的必要性等问题进行阐述。 一.引言 信息学是20世纪后半叶诞生的一门崭新的学科。数学、物理学、化学等学科的诞生是建立在一些科学家纯粹兴趣的研究基础上,其初期,科学家们的工作是纯理论性的。而信息学与他们的最大不同之处在于:自诞生之日起,它就与实际应用紧密地结合在一起了。每一个算法的提出,都有它广泛的应用背景。国际信息学奥林匹克竞赛(IOI)自1989年创办以来,已经举行了11届,其间题目的风格经过了一个曲折的发展过程。但我们应该看到,总的趋势是:向实际靠拢,每个题目都有一个实际背景,考察选手从实际问题中抽象出数学模型的能力。 但是,在众多的实际问题中,真正存在有效算法的P问题是少数,而大多数也是困扰人们的是NPC问题。在没有有效算法的情况下,要解决NPC问题,只能用一些非最优化算法在可接受的时间复杂度内求得一些近似解。因此为了考察选手在解决这方面题目的能力,在近年来的竞赛中,分段计分等非正常计分的题目逐渐增多。另外,在竞赛过程中,对于一些暂时想不出有效算法或实现有效算法比较困难的题目,使用非最优化算法可以得到不错的效果。(见表一)由上面两个原因可以看出,今后非最优化算法还是大有用武之地的,对非最优化算法的研究、总结是必要的...... |
查看评论
已有0位网友发表了看法