龙空技术网

人工智能--启发式搜索(贪婪算法)

沈聪工作室 236

前言:

眼前各位老铁们对“信息检索算法与启发式方法”大体比较着重,朋友们都想要剖析一些“信息检索算法与启发式方法”的相关文章。那么小编在网摘上收集了一些对于“信息检索算法与启发式方法””的相关知识,希望兄弟们能喜欢,各位老铁们快快来学习一下吧!

启发式搜索的代表算法为贪婪最佳优先搜索和A*搜索。下面通过一个示例说明贪婪最佳优先搜索和改进贪婪优化算法具体过程。

下图展示了城市之间的路径图,该图包含了城市节点,城市之间的路径以及路径的大小。

问题的是寻找节点1至节点19的最短路径。

贪婪算法:其思路从节点1开始,每次都选择最短的路径,直到到达节点19。

可以看出路径经历了3次死循环后,得出了最后的路径。

改进贪婪算法:其思路从节点1开始,每次选择N个最短路径进行比较,然后选择N个叠加后的最短路径。以N=2为例,其选择路径为:

Matlab程序和仿真结果

贪婪算法:该程序的难点在于贪婪算法能搜索到很多不可行的路径,程序需要返回到原来的节点重新进行搜索。

结果为:

改进贪婪算法(N-型贪婪算法),该程序的难点是遇到不可行解后,怎么退回找到原来的路径。这个算法对于大型的图或者树来说,能够提高搜索速度。但对于小地图来说,会引起算法的震荡(最终的目标那个节点是中间过程中的点)。

程序为:

运行结果:

可以看出当N=2时候,把20也加入了最后的结果。由于仿真程序较多,这里只附上主程序,如需要其他函数程序可以私信。

标签: #信息检索算法与启发式方法