局部搜索算法1 .局部搜索算法为什么叫局部呢？
1 )一些搜索算法需要返回从初始状态到目标状态的这条路径作为此问题的解，实际上存在很多优化问题。 你不需要知道到达目标的路径。 也就是说，如果不关心路径，只关心状态本身，算法需要找到符合要求的目标状态，那么该目标状态本身就是问题的解决方法。 对于这类问题，我们可以采用局部搜索算法。
2 ) .也就是说，局部搜索算法不记录其搜索过程，仅记录一个或多个当前状态，随后通过持续改进目标约束来纠正当前状态，直到满足目标状态。 这个目标状态本身作为这个问题的解决而返回，之所以被称为局部的理由，是因为只有现在的状态被保存了下来。 那么，如上所述，没有任何系统的记录从初始节点到达后续节点和目标节点的路径存储这些东西。 我只是在当前状态这个局部区域记录了搜索。 这是局部搜索算法的思想及其适用的问题。
2 .该算法有很大的优点。 这意味着对存储空间的要求非常低，只需保存当前状态，而无需记录所有正在行走的节点。 所以，它对于现实世界的问题，一般是无限空间状态的问题。 那个有实用性。 也就是说，它可以用来解决实际的大问题。
3 .那么，让我们看看这里有n皇后问题。
1 ) .用系统化的搜索树搜索算法做怎么样？ 其初始状态是空棋盘，通过在棋盘上一个接一个地放置皇后来制作后续的方法来探索目标状态。 也就是说树搜索算法给出的解会告诉你第一步的第一个棋子放在哪里，第二步的第二个棋子放在哪里，第三步的第三个棋子放在哪里，第四步的第四个棋子放在哪里。
2 ) .实际上，关于这n皇后问题，我们只关心最终皇后是如何安排的，而不是这四位皇后的安排顺序。 所以，可以采用局部搜索的方法。 也就是说，从一开始就随机将配置位置初始化为当前状态。 例如，这是随机的初始状态。 当然，我可以保证一排只能安排一位皇后。 这样的话，这个状态空间就会更小。
3 ) .那么，这种当前状态是通过不断地改进它，例如，通过将这位女王移动到新的位置来产生新的状态，看这个新的状态是否比这个旧的状态好。 如果更好的话，将这个新状态记录为现在的状态，删除这个旧状态，使其不占用内存。 然后，根据新的现在状态进行改善。 也就是说，将第二列皇后移动到第四行的位置，创造新的状态。 也就是说，将第二列皇后移动到第四行的位置，创造新的状态。 然后，他评估这个新状态是否比这个旧状态好，如果更好的话，就把这个新状态记录为现在的状态，然后再删除这个旧状态。
因此，通过这样不断改善，使这种现在的状态逐渐接近目标状态，作为问题的解决找到目标状态。 这是用局部检索问题解决这个n皇后问题的形式化及其思想。
4 .首先，让我们看一下第一个名为爬山搜索的局部搜索算法。 爬山探索意味着不断地向更高的地方前进。 那么，当然，我们的登山是一步一步爬上去的，所以它是一点一点地爬上去的，但是这个登山搜索算法有两个问题。
1 ) .所以，大家看到这句话——，都说就像失忆的人在浓雾中攀登珠穆朗玛峰一样。 这句话是登山搜索算法中两个问题的形象比喻。
2 )这个意思是说某人有健忘症。 那么，他不记得去了哪里。 也就是说，我只记得自己现在在哪里，周边怎么样了。 而且，还是在浓雾中攀登珠穆朗玛峰。 在浓雾中攀登珠穆朗玛峰一定不远。 他只能看到他周边的地形，看不到很远，他有什么问题吧。 也就是说，你可能不知道其他地方有更高的山。
3 ) .所以，我明白为什么在浓雾中登山。 因为，当它走到这个极大点时，他不知道前方更远的地方有更高的山。 因为看不见那个，所以那个会把这个极大点还给你。 还有一个失忆，就是无论何时都只保存了一个现在的状态。 也就是说，只保存了现在的状态。 于是，这个旧的现在状态的旧状态都被删除了，不记得了。 可见，该爬山搜索算法非常依赖于该初始状态，容易陷入局部最高值点。
5 .那么，让我们来看看这个算法。 首先，看这个算法的名字就叫爬山。 那个输入是问题的形式化。 那么，它会返回一个状态。 不像以前那样系统化的搜索会返回一条路径。 那么，这里返回一个状态。 这种状态是一个局部最高值点。 这意味着，只能保证返回一个局部最高值点，不能保证返回一个全局最高值点。
1 ) .那么，让我们看看那个输入是问题的形式化。 而且，它定义了两个局部变量。 一个是当前状态(当前节点)，也就是说，它用于保存当前状态。 而且，另一个是neighbor用于保存这个邻居的节点。 那么，让我们来看看这两个节点分别表示什么。 首先，当前节点的初始化是从问题形式化中的初始状态生成初始节点进行初始化。 这就是说，从初始节点开始，这是我们的当前节点，接下来开始搜索并开始爬山，首先从当前节点产生其后续节点。 当然，该生成方法根据问题的形式化，知道它能生成多少后续节点，从当前节点中寻找具有最大值的后续节点。 因为这个值是你定义的函数用来评价这个节点的优缺点，所以为什么也分类为启发式搜索这个大块呢？ 其理由是
你同样的要定义一个评估函数来评估这些结点的好与坏。在这里便于讲述就认为这个评估函数值越大越好，所以它是挑一个有最大值的后续结点出来，也就是说具有最好的后续结点出来放到neighbor里面去，然后看一下这个neighbor（最好后续）的值，是不是要比当前状态这个结点的值要小，那么要小的话就是说更差。我们刚才讲了这个值越大越好，那么如果你的评估函数值是越小越好你换一下符号就行了，就是这个地方换成大于等于就行了。那么假设我们当前结点产生的后续结点里面，最好的一个后续都比当前结点要更差，也就是说要更差，要更差那就意味着什么，那就意味着我当前这个结点所在的状态就已经是一个局部最值点了，也就是说我周边，我的邻居，我的儿子们，无论我怎么做我都会走向一个更差的结点，那他就不动了，它就把这个结点对应的状态返回去作为问题的解，所以就是返回一个他认为是找到一个最值点了，尽管这个最值点可能是局部最值点返回去了。否则的话，也就是说最好的这个儿子结点比当前结点要更好，那么它就往前走了，它就开始爬山了，我一看我的周边有个更高点，它就走到周边去了，它就走到这个更好的最好的后续结点去了，也就是说当前结点存储的就是这个最好的儿子结点，然后进行下一次的迭代，慢慢的往高处走，知道走到一个地方发现它怎么走都会更差，就把这个状态返回去，这个就是爬山搜索。 2).它是很容易陷于局部最值点的，如果你的目标函数有很多很多的局部最值点，那么用爬山搜索算法是极有可能是找到一个局部最值点，当然有一种方法就是你使用不同的初始状态，多运行几次爬山搜索算法，然后从里面挑一个最大的值作为这个问题的解。
6.那么我们来看一下用爬山搜索算法来解决这个八皇后问题。
1).那么这个八皇后问题，假设我们采用的是这么一个评估函数，这个评估函数定义成互相攻击到的皇后对数，那么当然互相攻击到的皇后对数越多越差，所以这里面就是越多越差。所以我们好的话就应该是这个值小的更好，那么比如说这个状态它的h值就是等于17，也就是说有17对皇后可以互相攻击的到，那么对于这个状态它的评估函数值就等于17。
2).那么像这么一个状态它就是，我们来看一下这个状态，它的评估函数值等于1，也就是说只有一对皇后可以互相攻击的到。那么对于这么一个状态它就是一个局部最值点，为什么呢，不管你怎么动这个皇后，当然我们限定它一次只能动一个皇后，也就是说它的邻居状态是通过对当前这个状态动一个皇后得到的，才是它的邻居状态、后续状态，那么不管你怎么样动一个皇后，它所得到的后续状态都会比当前这个状态要更差，也就是说这个互相攻击到的皇后对数都会更多。
7.summary:所以如果你的爬山搜索到达这个状态，它就会把这个状态返回来，作为这个问题的解，而这个状态其实上只是一个局部最值点，也就是说它还并不是完全符合要求的，也就是说它里目标要求还是差一点，那么这个是爬山搜索的一个问题，它很容易陷于局部最值点。