Brains


on Algorithm, 启发式搜索

启发式搜索

最近为了解决一个问题,粗略的学习了一些搜索算法,我真正动手实现的只有里面的2种,忽然感觉饶了一大圈又跑到机器学习的领域上去了。。。

写在前面

为了解决一个关于查找最短路径的问题,我查找了很多资料,学习到了一些新的算法。这篇文章我打算叙述两个部分,一个关于局部最优问题,一个关于启发式搜索问题。

问题的引入

这个问题来源于某公司的一个挑战赛中,是一个NP-hard问题,类似于旅行商问题和邮递员问题。其主要解决的问题就是在指定拓扑图G(V, E)中,找到一条尽量最优的路径,且这条路径不存在回路,且经过指定顶点集。

最短路径问题

想到最短路径问题,立马想到了Dijkstra算法了。。。这是一个非常高效的算法,它是基于贪心的算法思想。但上述题目并不具有贪心选择性质,会陷入局部最优。好的的情况下,会生成一条不是最优的路径;但差的情况下,甚至找不到一条有效路径。。

局部最优的情况

我第一次接触局部最优问题是在机器学习中的,比如逻辑回归在训练的过程中,采用梯度下降法对一些参数的优化的时候,会产生一些局部最优解。这是因为它的损失函数不是凸函数的缘故,因为这个函数有多个极值嘛。

在这个问题中,直接使用Dijkstra算法也会陷入局部最优的情况,如何跳出这个局部最优呢?比较典型的算法,哦不对应该是算法思想吧,模拟退火。这一题我之前就是用这个算法求解的,但效果不太理想。模拟退火算法属于一种启发式的搜素算法。

启发式的搜索

启发式搜索算是一种思想吧,就像动态规划一样,它是一种算法思想。它采用某些反馈措施,影响下一次选择的可能,而不是仅仅着眼于当下。其中我知道的有A*寻路算法、蚁群算法、遗传算法、模拟退火算法,还有最近很火的蒙特卡洛算法。我自己动手实现的就退火还有蚁群算法,它们的思想都很相似,我感悟最深的一句话,来自于百度百科关于蚁群算法的介绍中。

大自然的进化,社会的进步、人类的创新实际上都离不开这两样东西,多样性保证了系统的创新能力,正反馈保证了优良特性能够得到强化,两者要恰到好处的结合。

蚁群算法、遗传、蒙特卡洛算法的思想非常类似于上面两句话。我对启发式的理解也与它类似,就是随机性加上正负反馈。后面我的算法就是根据这句改进的,但目前陷入参数待优化的尴尬情况。。。从3月初到现在,我已经换过2次数据结构,三次算法了。。真是醉了。。总得来说,受益匪浅吧。一路学习的过程中,虽然没有真正掌握几个算法,但多了几种解决问题的思路,还是可以的~

吐槽一下

我看到有些同学开始采用开源的算法引擎库了,不知道效果咋样??找了好多论文都没来得及看,群里面有大神提出一种新的思路求解这道题目,用线性规划的思想找到这个最优解。感觉好牛X的样子,但我完全没思路,怎么破?只能老实的优化自己的代码,然后尝试学习下线性规划方面的知识。还有十几天就要结束了,希望自己能坚持到最后,加油啊 ~_~ 忽然感觉一个人的战斗好累啊。。。

EOF

comments powered by Disqus

纸上得来终觉浅,绝知此事要躬行~