北大公开课-人工智能基础 26 局部搜索与群体智能算法（三）禁忌算法

禁忌搜索的本质，是搜索的限制条件

禁忌搜索也是一张局部搜索，但是拓展后继节点是基于禁忌表的有选择性的拓展

三种禁忌表

禁止表，释放表，短期表（使数据在禁止表和释放表之间交换）

禁忌表搜索算法逻辑

将s'输入禁忌搜索中，返回一个最好的候选节点

初始定义，将s‘放入s中，也作为sbest 的值

初始定义禁忌表tabulist为空

     主循环: 如果找到一个最好的候选节点后，返回该节点作为解。

这些问题本身都是具有限制条件的

比如，旅行推销员问题，TSP，要求推销员不走重复的城市

图着色问题，四色定理，相邻的区域，不能使用相同的颜色。这些都是tabu禁忌要求。

在不同的路径中设置了禁忌规则

通过遍历，寻找从a点出发，到达e点的最小代价