路径搜索算法

算法	en		简介	时间复杂度		全局最优解	缺陷	应用场合
全搜索				( N^T )		√		指数级
维特比算法	Viterbi			T*N^2		√	深度T影响不大，N影响比较大。比如seq2seq中的N是词典大小。因此可采用近似算法	常用于HMM模型，分词、中文输入法
束搜索	beam search	属于贪心算法思想	beam search是一种启发式搜索，没有条件限制，都可以用，利用定义好的代价来剪枝，需要创建一个搜索树，因此每一个结点都与前面所有的父亲结点连接，生成很多结点在搜索树上，而DP是计算最优子问题的结果，保存在一个中间表中。	TNbeam_size	当beam_size=N时，就是Viterbi算法	×		seq2seq，
贪心	greedy search			T*N		×

全局最优

Viterbi算法

近似算法

• 贪心，每一步都贪心。
• 束搜索（beam search）就是引入了类似贪心的策略（每一步都贪心的保留一部分当前最好的结果）