Brains


Algorithm、Machine Learning、Search、cloud computing
on Algorithm, 启发式搜索

启发式搜索

最近为了解决一个问题,粗略的学习了一些搜索算法,我真正动手实现的只有里面的2种,忽然感觉饶了一大圈又跑到机器学习的领域上去了。。。 写在前面 为了解决一个关于查找最短路径的问题,我查找了很多资料,学习到了一些新的算法。这篇文章我打算叙述两个部分,一个关于局部最优问题,一个关于启发式搜索问题。 问题的引入 这个问题来源于某公司的一个挑战赛中,是一个NP-hard问题,类似于旅行商问题和邮递员问题。其主要解决的问题就是在指定拓扑图G(V, E)中,找到一条尽量最优的路径,且这条路径不存在回路,且经过指定顶点集。 最短路径问题 想到最短路径问题,立马想到了Dijkstra算法了。。。这是一个非常高效的算法,它是基于贪心的算法思想。但上述题目并不具有贪心选择性质,会陷入局部最优。好的的情况下,会生成一条不是最优的路径;但差的情况下,甚至找不到一条有效路径。。 局部最优的情况 我第一次接触局部最优问题是在机器学习中的,比如逻辑回归在训练的过程中,采用梯度下降法对一些参数的优化的时候,会产生一些局部最优解。这是因为它的损失函数不是凸函数的缘故,因为这个函数有多个极值嘛。 在这个问题中,直接使用Dijkstra算法也会陷入局部最优的情况,如何跳出这个局部最优呢?比较典型的算法,哦不对应该是算法思想吧,模拟退火。这一题我之前就是用这个算法求解的,但效果不太理想。模拟退火算法属于一种启发式的搜素算法。 启发式的搜索
Read More