人工智能之集束搜索Beam Search Algorithm
集束搜索是属于人工智能基础知识中的知情搜索，知情搜索是基于启发法的一种搜索方法，由爬山法——>最陡爬坡法——>最佳优先搜索法——>集束搜索，逐步优化算法
通过爬山简单来说下这几种知情搜索算法的区别：
比如甲去爬山，其爬山过程中每到分叉点都有n—m条路径可以走，只不过其过程中可能存在下山的路径
- 爬山法：当经过分叉点时，就会判断k条路径(k<n)，其中若排除掉下山的路径，剩下的路径中，能够到达较高的路径将会被选择。在爬上法中，是没有记录任何的经过路径信息。
- 最陡爬坡法：当经过分叉点时，就会从分岔点中的所有可选择路径中选择一条能够通向最大高度的路径，
- 最佳优先搜索：该算法是我目前入门人工智能中接触到的第一个智能搜索算法，该算法会通过启发法记录爬山过程中的比较好的节点路径，每次都在较好的路径中选择一条走，但该路径不一定能够到达目标节点，也不一定是最优算法，所以后面会经过回溯搜索更好的路径
昨晚在看到集束搜索这部分的时候有点蒙圈，一直不理解薄片宽度是啥。后来在网上查找相关资料之后才得以理解。下面就来谈谈什么是集束搜索？
集束搜索（又名为定向搜索，Beam Search Algorithm），是计算机科学中最重要的32个算法之一，是最佳优先搜索算法的优化，使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现前m个最符合条件的节点，m是固定数字——计数的宽度。
BeamSearch是一种启发式图搜索算法，通常用在图的解空间比较大的情况下，为了减少搜索所占用的空间和时间，在每一步深度扩展的时候，剪掉一些质量比较差的节点，保留下一些质量较高的节点，这样减少了空间消耗，且提高了时间效率。
算法的工作流程如下：
使用广度优先策略建立搜索树，在树的每一层，按照启发代价排序，然后仅留下预先确定的个数（Beam Width-集束宽度）的节点，仅这些节点在下一层次继续扩展，其它节点就被剪掉了。
- 将初始节点插入到list中
- 将给节点出堆，二u过该节点使目标节点，则算法结束
- 否则扩展该节点，去集束宽度的节点入堆，然后到第二步继续循环
- 算法结束的条件是找到最优解或者堆为空
补充：集束宽度可以是预先定好的，也可以是变动的，可以先按照一个最小的集束宽度进行搜索，如果没有找到合适的解，在扩大集束宽度再找一遍。
总结：Beam Search算法是在资源受限系统上运行的，处理大规模搜索问题的算法。整体算法上就类似广度优先搜索BFS+剪枝。