搜索算法概述：模拟退火算法与爬山法

"常见优化搜索算法小结" 在优化问题中，有两个关键点：代价函数和值域。代价函数是确定问题的形式和规模之后，根据不同的问题，选择要优化的目标。如第一个问题中，优化目标是使得航班选择最优，共计12个航班，要使得总的票价最少且每个人的等待时间之和最小。第二个问题是学生选择宿舍的问题，每个学生可以实现填报志愿，如果安排的宿舍与志愿完全一致，则代价为0，与第二志愿一致，代价为1，如果没有和志愿一致，代价为3。 值域是确定搜索的范围。一个可行解的范围是多少，比如学生选宿舍的问题，一共学校有100间宿舍，编号为1-100，那么这个数值优化问题的每个可行解的范围均在100之内。不同的问题对应不同的可行解，也要具体问题具体分析。 在优化搜索算法中，常见的有随机搜索算法、爬山法和模拟退火算法等。 随机搜索算法是最简单的优化搜索算法，它只适用于代价函数在值域范围内没有任何变化规律的情况。即找不到任何使得代价下降的梯度和极小值点。我们只需要在值域范围内生成足够多的可行解，然后分别计算每个可行解的代价，根据代价选择一个最小的可行解作为随机搜索的最优解即可。 爬山法假设当前解和周围的解是有变化规律的，如，当前解的下方有一个代价较小的解，则我们就认为，沿着这个方向走，解会越来越小。步骤为：首先选择一个解作为种子解，每次寻找与这个解相近的解，如果相近的解中有代价更小的解，则把这个解作为种子解。而如果周围的解都比该解的代价大，则表示已经到达了局部极小值点，搜索停止。 模拟退火算法从一个问题的原始解开始，用一个变量代表温度，这一温度开始时非常高，而后逐步减低。在每一次迭代期间，算法会随机选中题解中的某个数字，使其发生细微变化，而后计算该解的代价。关键的地方在于计算出该解的代价后，如何决定是否接受该解。如果新的成本更低，则新的题解就会变成当前题解，这与爬山法类似；如果新的成本更高，则新的题解与概率P被接受。这一概率会随着温度T的降低而降低。即算法开始时，可以接受表现较差的解，随着退火过程中温度的不断下降，算法越来越不可以接受较差的解，直到最后，它只会接受更优的解。其中P=exp[-（newcost-oldcost）/T]，其中newcost是新解的成本，oldcost是当前成本，T为当前温度。 优化搜索算法的选择取决于问题的特点和代价函数的性质。随机搜索算法适用于没有规律的代价函数，爬山法适用于有规律的代价函数，而模拟退火算法则适用于复杂的优化问题。