搜索入门及深搜广搜演示

1、回溯过程演示起始回溯过程演示起始Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;回溯过程演示回溯过程演示1Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;回溯过程演示回溯过程演示2Graph ma

2、p；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;回溯过程演示回溯过程演示3Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;回溯过程演示回溯过程演示4Graph map；Void dfs(位置位置 u) mapu

3、= 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;回溯过程演示回溯过程演示5Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;回溯过程演示回溯过程演示6Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置

4、的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;回溯过程演示回溯过程演示7Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;回溯过程演示回溯过程演示8Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上

5、的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;回溯过程演示到达回溯过程演示到达Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;到到达达广度搜索过程演示起始广度搜索过程演示起始Graph map； int step ;Void bfs(位置位置 u) mapu = 红色；红色； for (本步所能到达的所有位置本步所能到达的所有位置u) for (u 的

6、四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺的右左下上的顺 if (v可访可访 & stepvstepu+1) mapv = 红色；红色； stepv = stepu+1; 0广度搜索过程演示广度搜索过程演示1Graph map； int step ;Void bfs(位置位置 u) mapu = 红色；红色； for (本步所能到达的所有位置本步所能到达的所有位置u) for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺的右左下上的顺 if (v可访可访 & stepvstepu+1) mapv = 红色；红色； stepv

7、 = stepu+1; 011广度搜索过程演示广度搜索过程演示2Graph map； int step ;Void bfs(位置位置 u) mapu = 红色；红色； for (本步所能到达的所有位置本步所能到达的所有位置u) for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺的右左下上的顺 if (v可访可访 & stepvstepu+1) mapv = 红色；红色； stepv = stepu+1; 01212广度搜索过程演示广度搜索过程演示3Graph map； int step ;Void bfs(位置位置 u) mapu = 红色；红色； fo

8、r (本步所能到达的所有位置本步所能到达的所有位置u) for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺的右左下上的顺 if (v可访可访 & stepvstepu+1) mapv = 红色；红色； stepv = stepu+1; 012313233广度搜索过程演示广度搜索过程演示4Graph map； int step ;Void bfs(位置位置 u) mapu = 红色；红色； for (本步所能到达的所有位置本步所能到达的所有位置u) for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺的右左下上的顺 if (v

9、可访可访 & stepvstepu+1) mapv = 红色；红色； stepv = stepu+1; 0123413423344广度搜索过程演示广度搜索过程演示5Graph map； int step ;Void bfs(位置位置 u) mapu = 红色；红色； for (本步所能到达的所有位置本步所能到达的所有位置u) for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺的右左下上的顺 if (v可访可访 & stepvstepu+1) mapv = 红色；红色； stepv = stepu+1; 0123451345235345455广度搜

10、索过程演示广度搜索过程演示6Graph map； int step ;Void bfs(位置位置 u) mapu = 红色；红色； for (本步所能到达的所有位置本步所能到达的所有位置u) for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺的右左下上的顺 if (v可访可访 & stepvstepu+1) mapv = 红色；红色； stepv = stepu+1; 012345134562356345645656广度搜索过程演示到达广度搜索过程演示到达Graph map； int step ;Void bfs(位置位置 u) mapu = 红色；红色

11、； for (本步所能到达的所有位置本步所能到达的所有位置u) for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺的右左下上的顺 if (v可访可访 & stepvstepu+1) mapv = 红色；红色； stepv = stepu+1; 012345134562356734567456到达7567小结广度和深度优先搜索有一个很大的缺陷广度和深度优先搜索有一个很大的缺陷, ,就是他们都是在一个给定的状态空间就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十是很合适的算法，可

12、是当状态空间十分大，且不预测的情况下就不可取了。分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。他的效率实在太低，甚至不可完成。所以，在这里再次强调所以，在这里再次强调“剪枝剪枝”！搜索的魅力-启发式搜索 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 搜索的魅力-启发式搜索 我们先看看估价是如何表示的。 启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n) 其中f(n) 是节点

13、n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) g(n)时，可以省略g(n)，而提高效率。这些就深了。 搜索的魅力-启发式搜索 启发算法有： 蚁群算法，遗传算法、模拟退火算法等 ，其中蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用到组合优化、人工智能、通讯等多个领域。 下面我们看一下启发式搜索与深搜的对比演示，先来看深搜的！深搜过程深搜过程Graph map；Void

14、dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;0深搜过程深搜过程Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;012345深搜过程深搜过程Graph map；Void dfs(位置位置 u) mapu = 红色；红色； f

15、or (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;0123456深搜过程深搜过程Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;01234511109876深搜过程深搜过程Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位

16、置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;01234511 10 987612深搜过程深搜过程Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;01234511109876121314151617深搜过程深搜过程Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for

17、(u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 if (v可访问可访问) dfs(v); mapv = 白色白色;01234567891011121314151617232221201918242526272829到达启发式搜索过程启发式搜索过程Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 do(选出选出u可达的离目标最可达的离目标最 近的位置近的位置v); dfs(v); mapv = 白色白色;0启发式搜索过

18、程启发式搜索过程Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 do(选出选出u可达的离目标最可达的离目标最 近的位置近的位置v); dfs(v); mapv = 白色白色;012345启发式搜索过程启发式搜索过程Graph map；Void dfs(位置位置 u) mapu = 红色；红色； for (u 的四个方向的位置的四个方向的位置 v) /v按照按照u的右左下上的顺序的右左下上的顺序 do(选出选出u可达的离目标最可达的离目标最 近的位置近的位置v); dfs(v); mapv = 白色白色;0123456789到达可以看出w从上可以发现，深搜需要30步到达目的地，而启发式搜索只需10步就可以，不难发现估价函数的重要性，当然，这个例子的估价函数一