方法1:递归(Recursion)
递归是一极其常用的技巧。在我们的实际生产中也会经常用到,比如树遍历(地址,类目之类的)。
递归是一极其常用的技巧。在我们的实际生产中也会经常用到,比如树遍历(地址,类目之类的)。
我们并非每次都需要一个最优解。对于路径搜索来说,假设我们打游戏每设置一个目标位置就遍历全部的边,那么在需要频繁寻路的游戏中,效率就会很低。在权衡路线规划质量和执行效率的情况下,我们只需要寻求一个次优解就足够了。这时候就需要启发式搜索算法来实现了。
我们已经知道了深度优先搜索和广度优先搜索,适合在无权图搜索的适合使用。而在实际场景中,比如我们想获取A路口到B路口的最短路线,最短时间或者最少红绿灯的路线,就需要对一个有权图就行最短路径搜索了。Dijkstra算法就是处理有权图搜索的算法。
现实生活中的的顺序并不是简单的大小比较,而是一种依赖关系。比如我们穿衣服必须先穿内裤再穿外裤,先穿袜子再穿鞋。再比如,编译文件的时候先编译没有依赖的文件,再编译依赖文件。
图的表达能力很强,图的搜索算法在实际生产中有巨大的用出,不论是游戏寻路,地图导航,路径规划等等方向都有普遍应用。我们生活中很多场景都可以抽象为图结构,这使得图算法一直是一个重点,难点也是热点。