文档介绍：该【第七章人工智能蔡自兴 】是由【qqqqqq】上传分享，文档一共【152】页，该文档可以免费在线阅读，需要了解更多关于【第七章人工智能蔡自兴 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第七章高级(gāojí)搜索第一页,共一百五十二页。主要(zhǔyào)内容局部(júbù)搜索方法模拟退火算法遗传算法第二页,共一百五十二页。,共一百五十二页。优化与组合(zǔhé)优化问题很多问题属于优化问题,或者可以转化(zhuǎnhuà)为优化问题如TSP问题,皇后问题第四页,共一百五十二页。优化问题(wèntí)的描述设x是决策变量,D是x的定义域,f(x)是指标函数,g(x)是约束条件集合。则优化问题(wèntí)可以表示为,求解满足g(x)的f(x)最小值问题。如果在定义域D上,满足条件g(x)的解是有限的,则优化问题称为组合优化问题。第五页,共一百五十二页。算法(suànfǎ)的时间复杂度对于组合优化问题,由于其可能(kěnéng)的解是有限的,当问题的规模比较小时,总可以通过枚举的方法获得问题的最优解,但当问题的规模比较大时,就难于求解了。常用的算法复杂度函数第六页,共一百五十二页。输入量n复杂性函数**********!×××10139世纪时间复杂性函数(hánshù)比较(10亿次/秒)第七页,共一百五十二页。一些(yīxiē)难的组合优化问题旅行商问题背包问题装箱问题...寻求(xúnqiú)在可以接受的时间内得到满意解的方法第八页,共一百五十二页。邻域(línyù)的概念邻域(línyù),简单的说就是一个点附近的其他点的集合。在距离空间,邻域就是以某一点为中心的圆。组合优化问题的定义:设D是问题的定义域,若存在一个映射N,使得:则称N(S)为S的邻域。第九页,共一百五十二页。例:皇后(huánghòu)问题S={Si}表示一个可能(kěnéng)解,其中Si表示在第i行,第Si列有一个皇后。如四皇后问题的一个解:S=(2,4,1,3)QQQQ第十页,共一百五十二页。