学位论文 > 优秀研究生学位论文题录展示

联合启发式求解优先约束问题

作　者: 程爽
导　师: 谷文祥
学　校: 东北师范大学
专　业: 计算机软件与理论
关键词: 启发式搜索 k-分割最大启发式联合启发 hcem hpcc
分类号: TP18
类　型: 硕士论文
年　份: 2011年
下　载: 17次
引　用: 0次
阅　读: 论文下载

内容摘要

从上世纪60年代起,人们就开始了对智能规划的研究。如今,智能规划已经成为人工智能领域的一个重要分支。近年来,有关智能规划的研究取得了新的突破,使得智能规划成为一个热门的人工智能研究领域。启发式搜索结合知识与经验进行求解,常常能有效地解决问题。目前已有很多启发式搜索技术应用于规划领域的成功范例,比如快速前向规划系统FF。在规划问题中经常出现的一种情况就是当某个子目标实现时,它删除了在它之前实现的某个子目标,这样被删除的子目标需要重新实现,造成了时间和空间的浪费。在本文中,提出一种解决优先约束问题的算法,假设一个规划问题有很多子目标,首先,根据子目标间的相互关系,用k-分割策略给子目标进行分组,有相互作用的子目标分到一组,这样组与组之间是独立的;其次,在组内进行预处理,对子目标进行排序;第三,用ctx函数来检测是否会出现上述优先约束的情况,然后在各个大组间再进行检测;最后,在组内用我们提出的启发式h^cem,组间用启发式h^pcc,二者并行,计算实现最终目标的代价。组内使用h^cem启发式,当实例数量很大时,可以避免大量重复实现某些实例。提高运行效率,降低启发式值;组间使用h^pcc启发式,可以减少在预处理阶段ctx函数运行的时间。由于算法把大部分的工作留在预处理阶段,所以应用启发式h^cem和启发式h^pcc并行的求解速度要优于应用启发式h^cea求解的速度;启发式h^cem所携带的信息少于启发式h^cea,但保证了算法的可纳性。

联合启发式求解优先约束问题

内容摘要

全文目录

相似论文