您现在的位置:网站首页答辩论文计算机毕业设计其他计算机专业毕业资源

非最优化算法初探

  • 简介:现代信息学问题分为两类:一类是存在有效算法的所谓P类问题,另一类是目前尚未找到有效算法的所谓NPC问题。为了解决后一类问题,我们引进了非最优化算法的概念。本节将对NPC的概念和提出非最优化算法的必要性等问题进行阐述。 一.引言 信息学是20世纪...
    • 请与管理员联系购买资料 QQ:5739126
  • 论文简介
  • 相关论文
  • 论文下载
目录 一.引言
二.基本概念
三.非最优化算法分类
四.非最优化算法的性能分析 参考资料 1.《信息学奥林匹克》(98~99)。中国计算机学会。
2.《IOI’98中国集训队优秀论文集》。
3.《IOI’99中国集训队论文集》。
4.刘福生、王建德。《青少年国际信息学奥林匹克竞赛指导——人工智能搜索与程序设计》。电子工业出版社。1993年。
5.邢文训、谢金星。《现代优化计算方法》。清华大学出版社。1999年。
6.王树和。《数学模型基础》。中国科技大学出版社。
7.《IOI’99中国集训队第三次作业》。
现代信息学问题分为两类:一类是存在有效算法的所谓P类问题,另一类是目前尚未找到有效算法的所谓NPC问题。为了解决后一类问题,我们引进了非最优化算法的概念。本节将对NPC的概念和提出非最优化算法的必要性等问题进行阐述。
一.引言
信息学是20世纪后半叶诞生的一门崭新的学科。数学、物理学、化学等学科的诞生是建立在一些科学家纯粹兴趣的研究基础上,其初期,科学家们的工作是纯理论性的。而信息学与他们的最大不同之处在于:自诞生之日起,它就与实际应用紧密地结合在一起了。每一个算法的提出,都有它广泛的应用背景。国际信息学奥林匹克竞赛(IOI)自1989年创办以来,已经举行了11届,其间题目的风格经过了一个曲折的发展过程。但我们应该看到,总的趋势是:向实际靠拢,每个题目都有一个实际背景,考察选手从实际问题中抽象出数学模型的能力。
但是,在众多的实际问题中,真正存在有效算法的P问题是少数,而大多数也是困扰人们的是NPC问题。在没有有效算法的情况下,要解决NPC问题,只能用一些非最优化算法在可接受的时间复杂度内求得一些近似解。因此为了考察选手在解决这方面题目的能力,在近年来的竞赛中,分段计分等非正常计分的题目逐渐增多。另外,在竞赛过程中,对于一些暂时想不出有效算法或实现有效算法比较困难的题目,使用非最优化算法可以得到不错的效果。(见表一)由上面两个原因可以看出,今后非最优化算法还是大有用武之地的,对非最优化算法的研究、总结是必要的......
查看评论 已有0位网友发表了看法
  • 验证码: