【教务管理排课系统的研究与设计】王天钧.pdf

所在单位专研究方向:应用软件指导教师或推荐(在职人员填后者)学习期限日86年9月至89年7月

摘要本文首先回顾了P理论产生、发展的历史,重温了人们为解决P问题面进行的思索和走过的道路.MP问题遍布商业、科学、教育、交通。工程等许多领域。正是由于问题在现实生活中的广泛性、重要性和难解性,才引起了人们如此广泛而长久的兴趣,对这些问题的较为理想的解决无疑会对社会生活、经济生活产生巨大的影响和积极的作用.人们研究NDP问题是从组合搜索问题开始的,这样的问题涉及对一个有限的但极大的状态空间、模式。或者安排的结构化集合的搜索,以便找到一个满足一些给定条件的解。任何一个这样的组合难题中都潜伏着组合爆炸的可能性。

欧几里得距离,此时问题就成为找出一个其周长最小且经过所有点的多边形.巡回推销员问题表面上并不复杂,但它实际上是一个组合爆炸问题,因为在平面上经过n个城市的可能的巡回路经数为(n-1)12,这是的一个增长极快的函数,例如,当只有20个城市时,以每秒一百万个巡回路经的速度硬着枚举出所有可能的巡回路经所需要的时间可能为一千多年.KarD和eld尝试了多种方法来解决巡回推销员问题。首先他们发现了一种基于动态规划的简捷方法,该方法最初由R1chard Be1Lman指出过动态规划方法将搜索时间减少到n”2”,但这一函数仍然是爆炸性地增长,并且这一方法自前实际上只能用于至多几十个城市的