优化是决策的一般形式，在我们的社会中很常见。它的应用包括从求解数独谜题到婚礼上的座次安排。同样的技术可以调度航班和机组成员，协调钢铁生产，组织铁矿从矿井到港口的运输。人力资源和材料管理上好的决策可以令企业提升上百万的盈利。同样的问题很多也在我们日常生活出现，成为决定每天送货路线，决定学校时间表，传输电力到家里等种种问题的一部分。除了它们的重要性，这些问题如果用传统的本科计算机科学方法难以求解。 这门课程为已经完成离散优化高阶篇的同学设计。 请看这门课程的宣传视频：http://www.cpr.cuhk.edu.hk/cutv/detail/988
3.4.1 局部搜索
Loading...
來自 The Chinese University of Hong Kong 的課程
离散优化算法篇 Solving Algorithms for Discrete Optimization
個評分
從本節課中
局部搜索
这个模块带你进入局部搜索的神奇领域，它可以高效地探索一些大而复杂的搜索空间。你将会学到状态，移动和邻域的概念，还有它们在受约束的搜索空间中如何被应用在基本贪心搜索和最速梯度下降搜索中。你还将学习不同的方法来逃离或者避免局部最小值，包括重启，模拟退火，禁忌表和离散拉格朗日乘数法。最后，你将会看到大邻域搜索把在邻域中找到最优相邻点看作一个离散优化问题来解决，并因此使我们探索更远和更有效地搜索。
與講師見面
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
协助太上老君与哪吒击败通天教主后，
诸葛亮又被时空隧道带到唐朝， 协助唐僧师徒西行取经。
此时师徒一行人路过火焰山， 火焰山终年燃烧，高温令唐僧难以忍受。
诸葛亮建议悟空向深居翠云山 芭蕉洞的铁扇公主借用芭蕉扇，扇走山火。
悟空和诸葛亮来到翠云山， 打算寻找芭蕉洞，山底最低之处。
却发现此处已被铁扇公主布下法术，无法利用筋斗云， 只可在地上行走。
沿四方试探洞穴所在， 翠云山幅员辽阔，
悟空不知如何探路方可尽快找到芭蕉洞，借扇解救师傅受热之苦。
诸葛亮遂召出时空飞龙求助。
>> 孙悟空跟他的师傅快要经过这个火焰山了，
我们都知道呢，这个火焰山它的温度是非常高的。
对于悟空来讲，有可能是 没问题，但是呢，他的师傅是个凡人，绝对不可以忍受那么高的温度的。
所以呢，悟空就准备去问这个铁扇公主呢，去把
她的芭蕉扇可以借来，可以希望把这个火焰山里面的火焰呢，
利用这个芭蕉扇呢，把它扇走。
但是问题呢，就是首先，悟空就可以找到这个 铁扇公主住的地方。
他不知道她是住在哪里。
但是他知道她是住在一个山谷里面， 而且呢，她的芭蕉洞是在这个山谷里面最低的一点。
这个就是悟空知道的东西。
但是问题来了， 这个芭蕉洞，因为在这个山谷里面呢，所以铁扇公主呢，
也施了一些法术，就是来保护这个山谷的。
所以当悟空进到这个山谷里面的时候呢，第一， 他的法术都没有了。
所以他不再可以 搭载这个筋斗云上面去飞天哪，他也没有他的千里眼了。
而且呢，他来到这个山谷的时候呢，也会完全，差不多
完全迷失方向。
他只懂往这个 东西的方向或者是南北的方向呢，可以看到或者去走动。
这个就是他来到这个山谷里面的，对他的一些限制。
所以他现在就要来到这个山谷，要我们帮忙呢，看看他有什么办法可以找到这个芭蕉洞。
好了，我们再看看寻找这个铁扇公主这个问题。
这个悟空呢，一旦进入这个山谷的时候呢，我刚才已经讲过了，他就会失去所有的法力。
而且呢，他因为是迷失了方向呢，所以他只能可以沿着
东西这个方向，或者是南北这个方向去看跟去走。
但是有一件事他是知道的，
他是知道呢，这个山谷里面每一点，它的高度呢，原来是根据这个方程呢，可以计算出来。
他也知道呢，这个公主的这个芭蕉洞呢， 就是在这个山谷的谷底。
而且呢，是在地下面的。
所以呢，我们现在要帮助，给悟空 一个算法，可以帮助他可以找到这个公主的芭蕉洞。
好了，那个当然呢，一看起来就知道是个搜索的问题。
我们在这个课程 里面其实也讲过挺多关于搜索的问题。
我们 之前呢，谈到的搜索的技术呢，我们就其实叫它是 完备的搜索。
是什么意思呢？我们这个完备的 搜索呢，我们的目的是，理论上，我们可以把我们整个问题的
所有的可能的解的点呢，这个赋值呢，都会可以 检查过、 访问过的。
我们通常用的方法就是 从一个我们所谓部分的解，一开始的时候呢是空的。
然后我们一步 一步地，慢慢地把它扩展。
然后呢，在扩展这个过程里面，我们也要保证 就是我们的约束是不会给违反的。
利用这个方法呢，我们理论上 就可以保证，如果这个问题是有最优解的话，
我们就一定可以证明，我们找到这个解呢 就是最优的解。
又或者这个问题呢，根本就没有这个解的，就是不可以满足的，我们也可以 证明的。
那我刚才说，理论上，是因为这个理论呢，有可能你要花 很长很长的时间。
就算我给你现在世界上面最快的计算机，
你也有需要花一年两年这样子的计算的时间，才可以把这个理论的证明呢， 去找出来。
这个就是目前为止，我们所讲过的。
当然呢，这个 完备的搜索里面，我们也介绍过利用这个全部的技术可以把搜索的效率可以提高。
那下面呢，我们就希望可以介绍一个新的搜索的方法呢，给悟空，帮助他去找出这个
铁扇公主她住在哪里的。
我们这个新的搜索的方案呢，我们叫 非完备的搜索。
我们这个非完备的搜索呢，我们的目的就是，不是把 这个问题里面所有可能的解都去访问。
我们通常都只考虑里面 某一些，一部分的可能的解。
而且呢，我们一跳就跳到一个解，然后通常就直接从一个
可能的解，直接移动到另外一个可能的解上面，就不会
像以前一样，慢慢地把一个部分的解，然后把它扩展。
不是的。
我们一开始访问就是一个完全的全局的解，然后看看这个是不是我们的答案。
不是的话，我们希望有一些方法可以告诉我们 可以怎么去下一个点。
希望呢，我们越来越接近 我们要求的最优的解，或者要个满足的解。
但是我们这个方案呢，已经 讲过了，我根本的目的，也没有是考虑我们全部问题的里面所有的解的。
所以呢，理论上，我们这个方案是没有办法证明呢，譬如说，
这个问题有没有最优的解，或者呢，原来这个问题根本就不可以满足的。
我们 没有办法利用这个非完备搜索呢，来做到这一点。
但是那如果是这样子，为什么我们要 看新的不同的搜索的方法。
就是我们这个非完备的搜索呢，有一个非常的
大的好处，就是它相比这个完备的搜索的方案呢，它的效率是提高很多。
所以呢，它可以处理的问题可以更大，效率也提高地非常的多。
好了，我们就来看看，这个刚才悟空要 处理这个问题。
如果我们为这个问题去 为它建模呢，出来的
minizinc 的模型就是那么简单。
这个模型里面呢有 一个非常重要的特点。
虽然我们还是有变量， 这个所谓是变量呢，就是在这个山谷里面的
X 维跟 Y 维度的，到底这个悟空到了哪里。
而且我们也知道 这个山谷的范围的。
所以 X 从这个 - 4 到 4，Y 也是从- 4 到 4 这个范围里面。
这个就是山谷的范围，但是呢，我们这个问题里面是完全 没有这个限制的，没有约束在里面。
但是我们有一个 目标函数。
这个目标函数呢，就是来量你在每一点，到底在这个 山谷里面，它的高度是什么。
因为这个，我们公主的芭蕉洞是在 这个山谷的最低点。
所以呢，我们这个就是一个 最小化的一个问题。
我们就要把这个目标函数呢， 求它的最小的一个值，目标值。
好了，我们要介绍我们的算法之前呢，我们其实
先要介绍几个，其实我觉得比较 简单的一个概念。
这些概念就是帮助我们去介绍 我们将会介绍这个我们叫局部搜索这个算法。
局部搜索呢，是非完备算法里面的 其中一个非常重要的一种。
好了，第一个我们要介绍的概念呢，我们叫状态。
又或者呢，就是在以后我们就叫一个状态，我们就叫它一个点了。
所谓一个点是很简单，就是对我们问题里面所有的决策的变量给它一个赋值。
刚才我们这个问题只有两个变量，就是在这个山谷里面 拿
x 的维度跟 y 这个维度是在什么地方就是来决定你在这个山谷里面哪个地方。
所以如果我们为这个 x 这个变量跟 y 这个变量都给它 一个赋值呢，我们就叫这个就是一个点或者是一个状态。
好了，另外一个概念我们要介绍呢就是所谓一个移动
就是说在我们这个局部搜索里面我们所谓走一步是什么意思。
那不同的情况不同的问题，我们有可能会设计不同的移动的方案的，
譬如说在我们将会看到的例子里面呢，
我们的所谓一个移动呢，就是我们可以把我们问题里面其中一个变量它的值把它
改变，我们就呢叫这个所谓是一个移动。
譬如说，如果我们 x 的值从这个负 4 变成这个负
3，而 y 的变量的值是保留的话，我们
就说我们从一点移动到另外一点，所以通常移动呢都是 就是某一些的角色变量值的一个变化。
那我们刚才给这个例子呢就好象是这个问题 里面只有一个变量可以改变它的值，
但是其实呢我们在未来可以看到呢有一些所谓是移动的方案呢 是允许我们是多于一个变量都给它改变的它的数值的，
所以我们之后我们可以慢慢看到不同的移动的方案。
有了移动之后呢，我们就可以 定义一个非常重要的概念，这个就是邻域这个概念。
这个邻域的概念是相对于 我们现在在搜索当中的一个点，我们现在譬如说在这个点
然后他的邻域是什么呢？就是所有可以移动到的
其他的点一个集合，我们就把它叫做我们这个点它的邻域。
所以我从这个点根据我们的移动的定义， 可以移动到的其他的点，把它放到同一个集合里面，
这个集合就是我们现在在处于这个点 的它的邻域了。
有了这三个 概念之后呢，我们就可以介绍一个局部搜索的一个算法了。
我们要介绍这个局部搜索这个算法呢我们叫贪心局部搜索。
我们假设呢我们要
解决的问题呢就是一个最小化的问题，我们知道如果我们要
利用这个同一个技术一个算法去解决最大化的问题呢，其实只需要把这个目标函数
取它的赋值就可以了。
好了，我们就叫我们 这个算法这个函数呢叫
greedy_local_search，就是贪心局部搜索。
一开始的时候呢，我们就将会要调用一个函数，叫 initial_valuation，
它的一个参数呢就是我们问题里面所有的变量它们的值域。
我们就是利用所有知道每一个变量它的 值域呢来决定一个初始的一个点。
所谓 initial_valuation 呢就是返回一个初始的点，你可以用
里面用不同的算法来找出这个初始的点，很多时候呢我们这个 initial_valuation
这个 函数呢就是利用这个随机的方法，随便在我们要搜索的范围里面随便找一个点 这个也是可以的。
我们就用一个 d 这样子的变量呢 来放起我们现在的初始的一个点。
然后我们就进入一个循环
里面了，这个循环我们做到什么情况会停止呢？
我们就是另外的一个可以调用的函数叫 stoppingcondition，就是所谓是要停止
的条件，就是如果我们要停止的条件还没到的时候，我们就继续做这个循环吧。
那所谓是停止的条件是什么呢？通常都是说我们看看我们有
多少的资源可以帮助我们去做这个搜索的，很多时候我们就看看，譬如说
我们最多可以访问的点呢就是多少个，如果我们超过
这个我们可以访问的点的上限的话，那我们就要停止了。
然后如果我们还 没有用完我们的资源的话，我们就做下面的三个非常简单的一个步骤。
第一个步骤呢就是我们要把我们目前现在在的点，那一开始的时候当然呢这个现在在的点呢
就是我们的初始的点，为这个现在在的这个点呢算出它的邻域，就是什么呢？
根据我们定义的这个移动，就是从这个现在这个点可以移动到
一步之内可以移动到其他的点，它们的一个集合，我们称这个邻域呢就是叫大 N。
然后呢我们就再调用另外一个函数我们叫呢这个 choose_neighbour，就是从这个大
N 这个邻域里面呢 选取其中，邻域里面有很多点的，我们选取其中一个点。
怎么选取另外一个点呢，其实 有不同的方案的，有一个可能性就是随便随机的在这个
邻域里面随便选取一个新的点。
也有可能呢 下面我们也会介绍另外的一个不同的方案呢来选取
从邻域里面选取新的一个点，我们就叫这个新的这个点叫 e
吧 然后呢就是看看呢我们要比较一下，我们新的在邻域里面选取这个点
e 跟我们现在目前 为止，我们在这个点要比较一下它们的
f， 就是我们的目标函数，就是要比较一下它们的目标函数的值。
我们说如果这个 e 这个目标函数的值呢是小于
d 这个目标函数的值呢，就是说我们新的在邻域里面选的点如果它的目标函数的值呢是比
我现在这个点的目标函数的值呢比较好，因为我们在解决最小化 问题嘛，所以越小的目标函数呢的值呢是越好的。
所以如果我们发现我们新的点呢是比现在的点它的是更好的话
那我们就要为我们现在的点呢更新，更新到新这个点。
就是那么简单，我们就是重复重复重复，把三个步骤呢去做，直到
我们已经访问了太多的点了，我们够了，我们把所有的资源已经用完了 那我们就要停止了。
停止了我们就把我们目前为止 在现在在的这个点返回，这个就是我们这个贪心
的局部搜索这个算法呢就是这样子的。
好了，我们就下面就可以看看悟空怎么可以利用我们这个贪心
局部搜索呢来尝试去找不找到这个芭蕉洞。
我们要记住这个呢就是我们要最小化的这个目标
函数，也代表了在就是这个整个山区里面每一点的 它的高度。
初始的这个状态或者是初始这个点，我们刚才可以
讲过是可以很多方案计算出来的，为了简单一点我们 就说譬如说悟空就从这一点开始搜索吧，
也有可能的悟空就一跳跳进这个山谷里面随便的一点，随机的一点也可以。
但是我们在这个例子里面 这个演示里面我们假设呢，悟空就是从这个
(-4, 4)这个点开始他的搜索。
我们跳到这个点之后，第一件事情呢就要看看 它的高度是多少，我们发现呢它现在的高度呢是 36。
而且你们也看见呢我们把这个 36 的背景呢放到
一个绿色，其实呢我们将会在每一个点我们计算了它们的 高度的时候呢，我们也会给它一个背景的颜色。
有可能是绿色慢慢变成黄色慢慢变成这个红色
来代表给大家容易看一点，其实现在这个点是一个高的点呢，绿色就是高的点，黄色就是中间点
比较中间的高度，如果是红色的话就是比较一个低的点了。
所以我们可以看见呢，这个现在初始的点呢是高度比较高的。
好了，有了这个之后呢，我们现在为这个问题
设计这个邻域就是什么呢？我们允许这个悟空，因为悟空呢在里面
到了这个山谷之后呢，他只可以往这个横向去看
或者是纵向去看，这个是他可以看到的地方，这个就是他可以有可能跳
到的地方，这个就是所谓我现在目前这个初始的点的一个邻域。
然后呢， 我们怎么 choose_neighbour 呢？我们怎么怎么从这个邻域里面那么多点选择其中一个新的点，希望
考虑要不要跳去这里呢？我们就利用这个随机的方案随便选择这个点，
但是呢，随便选择了一个点之后，譬如说我们选了这个点，我们呢也需要
需要呢看看这个点呢是不是比我现在这个点呢为低的。
所以呢如果为低我们才采用这个新的点，因为我们希望呢我们每一个移动呢都
需要是个下坡的一个移动来的。
我们发现呢新的 点呢它是黄色的，所以就比我们绿色这个点呢高度为低。
所以呢悟空可以跳去这个新的地方的。
然后我们就把我们刚才这个算法里面的循环的部分
就重复再做，就是到了一个新的点，就看看这个新的点的它的所有邻域。
所谓邻域呢就是 就是这个点它的在同一行或者是同一个列上面的其他的点，然后我们也随机的
选择一个新的点。
但是我们发现这个新的点呢它的高度是 44，是绿色的，当然就是比我们现在这个
黄色为高，所以呢我们就不，如果我们移动到这个新的点呢不是一个下坡的
一个移动，所以我们就不做了。
现在可以做什么？我们重新从这个邻域里面再 随机的去选择新的一个点。
新的这个点呢我们发现呢它的高度是 3，所以当然比这个是 为低。
所以呢我们就可以，悟空就可以移动到这个点。
然后到了一个新的点，我们也看看它旁边的 它的相邻的点就是在同一行，同一个列的。
然后又随机的找一个，我们发现新的这个呢 出来这个点呢，它的高度跟我们现在点的高度是一模一样的。
如果你们还记得刚才告诉你们的这个算法里面
我们需要新的点呢是比现在我们在的点呢是为好的，就是为低的地方我们才移动的。
所以呢这个点我们也不会去。
我们再随机 找另外一个点吧。
我们发现这个点呢它的高度为 0 所以呢悟空当然呢再去一个新的更低的一个点。
然后我们再看看它的 邻域在有什么其他的点，然后也随机找一个
我们发现呢原来新的点呢更 低，-4，所以当然悟空会移动到这一边。
好了，找了 那么，走了挺多步了，我们有可能、
有可能 我们当然可以继续的搜索下去，但是也有可能的说
我们已经把我们所有可以搜索的资源已经用完了，就是悟空呢
已经太累了，所以呢它就会说我们的搜索完成了。
所以呢我们这个算法呢就返回了这个（1，-2）
这个点作为这个说，这个就有可能就是 芭蕉洞啊。
就是这样子。
好了，基于这个目标函数 我们要为它最小化。
我们刚才呢，我们的贪心局部搜索的这个算法呢， 返回的就是这个（1，-2）这个点，到底这个是不是最优的解呢？
因为我们的问题其实也不是太大，如果大家有兴趣的话呢，可以把每一点它们的高度都算出来。
我们其实发现呢在（2，-2）这个点呢，它的目标函数根据这个来算出来呢 其实它是
-6，其实呢比这个现在目前的点 -4 更低，在地下面的。
所以呢，其实我们刚才，如果我们已经把我们所有的 资源已经用完的话，要返回这个点呢
这个就不是我们的要找的最优的解。
好了，那当然呢对于悟空来讲，他真的需要把这个芭蕉洞 找出来的，这个就不太好了。
其实我们刚才这个算法呢是没有办法为他 找到这个芭蕉洞的。
但是对很多时候我们要解决一个优化的问题的时候呢，
我们也不一定要把这个最优的解求出来的，很多时候呢
我们只需要一个比较好的解就可以的，所以其实这个贪心局部搜索这个方法呢
也是挺有用的一个方法，而且呢它的效率也挺高的。
其实在我们刚才介绍这个贪心局部搜索的方法呢
里面有一个非常重要的一个我们要调用的一个函数。
这个函数呢就叫 choose_neighbor。
就是说我们目前这一点之后，我已经算了目前的点它的所有相邻的点的一个
集合，就是我们的邻域。
我们要用什么方法把 里面的另外、
下一个点找出来呢？我们刚才用的就是 用随机的方法。
但是其实呢，有一个方案就是什么呢？我们去检查我们邻域里面
每一个可能的点，然后把每一个点呢它的高度，它的目标函数的值呢
都计算出来，然后我们就把这个目标函数值最好的一个相邻的点
就用这个点来作为我们下一个要去的点。
这个也是一个可行，我们 choose_neighbor 这个一个方案。
这个方案的好处呢就是 我们可以比较快一点，就是我们每一趟要选择我们的路线就是最快的路线，对于我们目标函数
的值呢下降的最快的一个新 的点。
当然利用这个方法呢我们也有一个取舍的，
就是什么呢？我们需要把所有邻域里面的所有的点，
它的目标函数的值都要计算一遍，这个在计算方面来讲呢要求是
其实是挺高、 挺贵的一件事情。
但是呢我们花多了一点 计算的力度，但是呢我们应该也可以最快的
就可以提高，或者是降低我们目标函数的值的。
好了，我们就看看如果我们利用这个最速下降这个方案来希望帮助这个
悟空，看看出来的搜索的行为会怎么样。
我们一开始也是用刚才这个好不好？ 就是（-4,4）这个点，然后我们已计算出呢原来它的高度是 36。
好了，我们下一个点呢怎么找呢？我们就是把它邻域里面
所有的点的高度都计算出来，我们发现呢下降的最多的
就是这个点，所以我们就跳到这个新的这个点。
然后从这个点呢我们也计算 它同一行、
同一列的所有的点它的高度，我们发现呢这个两个点就是 最低的。
如果有多于一个点我们可以去，都是最低的话，我们就随便找一个。
譬如说，我们就 跳到这个新的点好不好？来到这个之后我们又重复我们的
循环就是把同一行、 同一列的所有的
可能的点呢它们的高度呢都计算出来，我们发现呢这个 -5 就是 最低的点。
所以我们一跳就可以跳到这个 -5 这个点，然后我们再重复刚才的动作。
然后在同一行、 同一列、 同一行也计算，我们发现呢这个
-6 是比这个 -5 更好的， 所以悟空就跳到这个点了。
然后跳到这个点呢，我们发现呢 我们同一行、 同一个纵列、
同一行 里面上面所有的相邻的点，它们的高度都是比我，不比我
现在为低的，所以呢我们利用刚才这个
算法呢就不可以再移动了，其实呢我们 这个
-6 就是我们刚才提过的最优这个解，这个也就是这个芭蕉洞 所在的地方。
好了，那是不是
最速的下降就是可以保证我们一定可以把我们这个问题里面的全局的最优
解找出来呢？这个其实呢，刚才对我们要解决这个问题，因为呢它的地形呢
是凸的，就是一个凸优化问题呢我们可以保证，但是一般来讲呢我们刚才这个问题的答案是 不是的。
而且呢我们刚才也看到 我们利用这个最速的下降的局部
搜索的方法呢，我们几步就已经把这个最优的解找了出来了。
但是呢我们有另外一件事情呢要讨论就是
原来这个邻域它的定义也直接会影响呢我们到底可不可以
把这个最优的解找出来，而且呢也会这个影响呢我们找到这个最优解的
这个效率的，所以下面我们就看看，如果我们还是用这个
最速下降这个局部搜索这个方法，但是我们改变我们邻域的
一个定义，看看出来的效果会怎么样吧。
好了，还是同一个问题要最小化
这个目标函数，我们还是从同一个初始的点开始我们的搜索。
好了，计算出来它的高度了，但是这一趟呢，我们的邻域的定义呢，我们还是
允许就是把其中一个变量它的值改变，就是还是呢
可以可以，悟空还是可以跳到同一行的另外一个点，或者同一列的另外一点
但是他不是可以跳到同一行的所有其他的点 或者是同一列的所有同，其他的点，因为我们限制呢
我们为这个变量的值改变呢，它的改变量只可以为1，你可以
加1，或者是减1，就是所以呢，悟空可以跳到另外的点呢，只是他旁边的点
所以在这个情况，因为他刚好在一个角落呢，所以他只有两个
相邻的点，所以呢，发现呢，这个是30，这个是31，所以呢
他就跳到30这个点，然后呢，他就到了一个新的点，然后就他要利用这个新的邻域
的定义呢，来计算他的相邻的点呢，他的他们的高度 这个是黄色的，所以呢，他就可以跳到这个黄色这个点
来的黄色这个点呢，他的邻域因为现在已经不在这个 边缘化的角落上面呢，所以他的，他有相邻的有4个
有4个的相邻的点，我们也看看，哪一个相邻的点呢，比现在的为低
我们发现呢，他可以往右走，然后其实我们每一步 都是这样子做了，去到一个新的点，看看到相邻的地方的高度
然后我选取一个比我们现在的高度为低，而且是相邻里面最低的一个点，就移动到这个新的
点，然后一直一直一直这样子走，当然呢，你看我们也走了挺多步了，你们有可能说：
啊，他，悟空有可能累了，我们就停止，就把现在的点呢，返回。
但是，假设吧 悟空这一趟，他，他的资源非常多，他也无限的
力量，他就可以继续去，去做这个搜索，继续搜索吧
啊然后呢，利用相同的方法继续的搜索呢，他最后其实呢，也是可以来到这个点
发现呢，在他的邻域上面，每一个点呢，都不比
他现在这个点呢，更好的，其实他现在呢，也是找到最优这个点
但是当然呢，跟之前不同的一个地方呢，就是悟空其实也走了一个
挺长的一个路径，才找到这个这个最优的解，所以我们可以知道呢
啊这个邻域的定义呢，可以直接影响我们这个这个搜索的这个效率的
所以我们刚才已经知道了，这个邻域
邻域呢，这个对于这个局部搜索的有效性跟他的效率呢
是影响可以很大的，我们就刚刚，我们从前两个不同的
邻域的定义吧，开始的时候，第一个邻域的定义呢就是我们
容许呢，任意的为其中的一个变量到他的值呢，可以更改
所以悟空呢就可以跳到同一行，或者是同一个列，任何一点，当然呢
就是最好的一点啦，但是我们刚才看见这个邻域呢，它的定义呢就是，只容许呢悟空
跳到他旁边，旁边的一个点，因为我们限制了这个改变量呢为1，可以
加1，现在这个点，加1或者是减1，这样去跳，可以往上下，或者是左右
但是只可以跳旁边的点，啊我们，当然呢第2个邻域呢，是比第1个
邻域呢，有更多的限制，但是呢，我们新进的邻域呢
的一个好处呢，就是我们每一步需要检查的点的数量
啊，为更小，所以呢我们要计算的
力度呢就不需要那么多，但是出来的效果就是，我们最后，还是找到我们的最优的这个解
但是我们出来的这个路径呢，就是比 第1个邻域呢，来讲呢，是强的非常多
无论怎么样呢，我们就算是利用这个最速下降局部 搜索这个算法的话，我们只是在这个
凸的地形里面，才可以保证可以一定可以找到最优解，如果这个地形
不是凸的话，会怎么样呢？譬如说这个就是，啊，一个
不是凸的这个地形呢，最大的问题就是，在这样子的个地形里面呢
我们有很多，我们看见红色的地方呢，我们叫它们是局部的最小点
但是我们要解决我们的问题，我们根本就对 最，红色这样子的局部最小点呢，是没有兴趣的
我们真的有兴趣，希望找到的，就是蓝色的这个最小点，就是我们的 整个问题的，全局的最小点。
所以呢 要一个，一个好的局部搜索的个方法呢，它的关键就是有没有，有没有办法
可以，如果我们来到一个局部的最小点，来到这个点的问题是什么？发现它旁边的点呢
都是比它高的，就是，不比它好的，所以我们利用我们刚才这个局部搜索方法
根本就走不动的，所以呢我们一般，我们的局部搜索的方法呢
我们都有一些方案，帮助我们可以逃离这样子的局部最小点
但是呢，其实呢，这个不是最坏的一个情况，最坏的情况呢，就是我们还有，其实我们有两类
不同的局部最小点，这个红色、 红色的地方 我们之前已经看过啦，但是黄色的地方是什么呢？
就是一个平原，在这个平原上面呢，就是我如果在这里的话，我
旁边的点呢，不是比我差劲，但是也不比我好，所以我旁边的点呢，根本就
没有一件，技术可以告诉我，帮助我，下一步
我应该跳到哪里，所以呢其实，我们也是，刚才讲过了，就是
一个好的，一个局部搜索的算法呢，一定有一些方案可以帮助我们逃离
无论我们刚才介绍过红色的我们所谓是强的局部最小点，或者黄色的，我们所谓的是弱的局部
最小点，要逃离这样子的地方，最终呢希望 来到一个地方呢，可以帮助我们，啊，就找到我们真的希望的就是
啊找到这个蓝色的啊全局最小点了，啊我们来一个总结
在这一节课里面呢，我们就介绍了一个所谓是局部搜索的一个方案，啊这个是一个
非完备的一个搜索的一个方案来的，啊而且我们介绍，这个这个算法呢
虽然看起来非常简单，其实呢里面有4个函数，我们需要调用的函数呢
是非常重要的，其实也是我们这个算法的一个，也可以说它这些函数呢就是我们的
算法的参数来的，第一个就是initial_valuation，就是呢我们开始搜索的-
时候，要从 哪一个点，作为一个初始的点来开始我们的搜索呢
我们说，其中的方法呢，就是利用一个 随机的方法，也有可能就随便吧，譬如说我们
刚才从，在这个山谷里面，我们就随便从这个 一个角落，开始吧。
另外一个重要的函数呢 就是neighbourhood，就是呢，我现在到了一个点，这个点到底根据我们设-
计的移动 我们一步可以移动到什么其他的点呢，所有这样子其他的点的
一个集合呢，就是我们现在这个点的neighbourhood，就是它的邻域了
有了邻域之后我们当然需要有一个函数的choose_neighbour，就是帮助在- 邻域里面
看看所有的点，我们希望可以选择一个好的点 给我作为我们下一个要跳到，移动到的一个点。
啊choose_neighbour我们其实呢 也看过两个不同的方案，第一个方案呢就是我们
也是随机的，在所有的相邻的点里面，随机找一个出来 看看是不是比我现在的点比较好，好的话我就移到这个新的点
不好的话我们就重新再从这个邻域相邻的点里面
再找另外一个新的点吧，另外一个呢
就是我们的stopping condition，就是我们这个循环，做到什么地步，我们要停止下来啦
啊一般来讲，就是基于我们，可以给我们做搜索的资源用了多少，譬如说
资源包括我们访问了多少个点，也或者是 就是我们把这个要计算，啊邻域里面
如果我们用这个最速下降这个局部搜索的方法呢，我们这个choose_neighbou- r就需要把邻域里面所有的点
它的目标函数的值的也计算出来，如果我们把这个计算 需要的资源也计算呢，啊我们与可以帮助我们定义
什么时候我们已经把我们所有的资源已经做完，或者是悟空是不是已经太累了，没有这个气力
再继续的搜索下去，那我们就要停止，然后我们这个这个 算法呢，就把目前我们在的一个点返回，这个就是我们
找到目前最好的一个点，我们发现呢，虽然我们这个故事里面的这个要解决这个问题
非常简单，因为它的地形呢是个凸的这个地形
但是刚才已经讨论过了，一个有效的一个成功的局部
搜索的一个算法呢，要面对两个非常大的挑战 第一个呢就是有效的要处理这个约束
我们刚才这个问题里面根本就没有约束，只有这个变量，变量的范围
还有一个目标函数，就没了，没有约束的，那我们应该怎么可以处理
如果我们问题里面有约束的话怎么处理它呢？另外就是我们刚才讨论的就是，我们怎么有效的
去逃离一个局部的最小点呢，这个就是我们在接下来的
章节里面呢会跟大家进行这个探究的。
