精选文档
第7章 高级搜索
在第一章、第二章，我们分别介绍了深度优先、宽度优先、A*算法和AO*算法等常规的搜索算法。深度优先、宽度优先等盲目搜索算法就不用说了，即便是A*算法，一般情况下，其算法复杂性仍然是指数时间级的。因此，当问题的规模大到一定程度之后，这些常规的搜索算法就显得无能为力了。本章将介绍一些相对比较新的搜索方法，如局部搜索、模拟退火和遗传算法等。这些算法的一个共同特点是引入了随机因素，每次运行并不能保证求得问题的最优解，但经过多次运行之后，一般总能得到一个与最优解相差不太大的满意解。以放弃每次必然找到最佳解，换取了算法时间复杂度的降低，以适合于求解大规模的优化问题。
7.1 基本概念
7.1.1 组合优化问题
在现实世界中，很多问题属于优化问题，或者可以转化为优化问题求解。比如我们前面介绍过的旅行商问题（TSP），就是求解旅行商在满足给定的约束条件下的最短路径问题。这里的约束条件是“从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后再回到出发城市”。还有皇后问题，它要求在一个n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”，即在任何一行、一列和任何一个斜线上，只能有一个皇后。皇后问题本身并不是一个优化问题，但可以转化为优化问题来求解。比如我们可以定义指标函数为棋盘上能够相互“捕捉”的皇后数，显然该指标函数的取值范围是一个大于等于0的整数，当棋盘上摆放了n个皇后，且其指标函数取值为最小值0时，刚好是问题的解。因此皇后问题转变成了求解该指标函数最小的优化问题。
设x是决策变量，D是x的定义域，f(x)是指标函数，g(x)是约束条件集合。则优化问题可以表示为，求解满足g(x)的f(x)最小值问题。即
可修改
精选文档
min?f(x)|g(x)?
x?D （7.1）
如果在定义域D上，满足条件g(x)的解是有限的，则优化问题称为组合优化问题。现实世界中的大量优化问题，属于组合优化问题。像旅行商问题、皇后问题等是组合优化问题的典型代表。
对于组合优化问题，由于其可能的解是有限的，当问题的规模比较小时，总可以通过枚举的方法获得问题的最优解，但当问题的规模比较大时，其状态数往往呈指数级增长，这样就很难通过枚举的方式来获得问题的最优解了。
一个问题的大小通常用输入数据量n来衡量，如旅行商问题中的城市数目，皇后问题中的皇后数目等。对于同一个问题，不同的求解方法的效率是不同的，差别可能会非常大。通常用算法的时间复杂性来评价一个求解方法的好坏。常用的算法复杂性函数按复杂性从小到大排列有如下几种：
O(logn),O(n),O(nlogn),O(n2),O(2n),O(nlogn),O(n!),O(nn)
其中O(h(n))表示该算法的复杂性为h(n)量级。如n皇后问题，由问题的约束条件，我们知道每一行、每一列只能并且必须放一个皇后。如果我们先不考虑对角线的情况，先用枚举法生成出n个皇后不在同一行、同一列的所有状态，再从中找出满足约束条件的解。从第一行开始放起，则第一行每个位置都可以放皇后，因此共有n种方法；第二行除了第一行皇后的所在列以外，其他位置都可以放皇后，因此共有n-1种方法；依此类推，第i行共有n-i种摆放方法。所以所有可能的状态数共n!个。这样我们可以大概估算出，用这样一种枚举法求解n皇后问题，所花费的时间与n!成正比关系，其时间复杂性用算法复杂性函数表示就是O(n!)。
Nirwan Ansari和Edwin Hou在他们的书中，给出了假定计算机的处理速度为每秒钟执行10亿次运算的条件下，不同输入数据量下各种复杂性函数所需要的计算时间。如表7.1所示。
表7.1 时间复杂性函数比较
输入量n 复杂性函数 10 10ns 10ns 20 20ns 26.0ns 30 30ns 44.3ns 40 40ns 64.1ns 100 100ns 200ns n nlogn 可修改
精选文档
n2 2n 100ns 1.0?s 3.6ms 400ns 1.0ms 77.1年 900ns 1.1s 8.4×1013世纪 1.6?s 18.3min 2.6×1029世纪 10?s 4.0世纪 3.0×10139世纪 n! 当一个算法的时间复杂性可以表示为多项式形式时，则称之为多项式时间算法，否则就是一个指数时间算法。从表7.1中可以看出，如果一个算法是指数时间算法（2n或者n!），那么当n大到一定程度时，因为所花费的时间太长了，以至于不可能求解。
一些组合优化问题已经找到了多项式时间算法，如线性规划问题。还有一些被称为难于求解的组合优化问题，至今还没有找到求解这些问题的最优解的多项式时间算法。像旅行商问题、背包问题、装箱问题等，都属于这类难于求解的组合优化问题。由于这些问题都有很强的实际背景，为此人们研究一些不一定能求得最优解，但往往能得到一个满意解的算法，以此来降低算法的复杂性。而实际上很多情况下追求最优解并不一定有意义，一个满意解就已经足够了。这就如同夏天去买西瓜。你没有必要非要买一个北京市最甜的西瓜，甚至于也没有必要买一个西瓜摊中最甜的西瓜，因为这样选择的工作量太大了。你只需从面前的3～5个西瓜中选择一个最好的就可以。当面前的这几个西瓜都感觉不合适时，你可以换一个位置，或者换另一个西瓜摊重新选择。如果你对西瓜的评价是正确的话，那么这样选择出来的西瓜应该是一个令你满意的西瓜，与“最甜的西瓜”差别也不会太多。
7.1.2 邻域
在后面的介绍中经常会用到邻域的概念。我们先给出邻域的定义。
邻域，简单的说就是一个点附近的其他点的集合。在距离空间中，邻域一般定义为以该点为中心的一个圆。在组合优化问题中，距离的概念不一定适用，为此提出其他的邻域定义。
设D是问题的定义域，若存在一个映射N，使得：
N:S?D?N(S)?2D
（7.2）
则称N(S)为S的邻域，称S'?N(S)为S的邻居。 下面举几个例子。
可修改
清华大学人工智能导论课件_第七章
