5.3盲目搜索方法
上一节
下一节
盲目搜索(通用搜索)策略
通用搜索策略主要指深度优先搜索、宽度优先搜索。
这一类算法采用“固定”的搜索模式,不针对具体问题,其优点是适用性强,几乎所有问题都能通过深度优先或者宽度优先搜索来求得全局 优解,但效率往往不高。
通用搜索策略主要指深度优先搜索、宽度优先搜索。
这一类算法采用“固定”的搜索模式,不针对具体问题,其优点是适用性强,几乎所有问题都能通过深度优先或者宽度优先搜索来求得全局 优解,但效率往往不高。
在许多不太复杂的情况下,使用盲目搜索策略也能够取得很好的效果。
深度优先搜索
• 核心要点:
– 首先考虑纵深探索, 如果达到底层,仍然无解, 则“回溯”至上一层 更换其他路线
宽度优先搜索
• 核心要点:
– 首先考虑同级别的状态, 如果同级别均不符合, 则前进至下一层 继续搜索
贪婪搜索策略
• 贪婪搜索策略:总是做出在当前看来最好的选择,或者采用使得当前步骤获利最大的选择,因此也叫做贪婪算法。
– 贪婪搜索策略不考虑整体最优,仅求取局部最优。因而也可以看作是一种“盲目”的策略。
– 贪婪搜索不能保证得到最优解,但搜索速度非常块。
– 对一些特定问题很有效。
小结
• 介绍了“盲目”搜索的策略。
• 深度、宽度优先搜索通用性强,但效率慢
• 贪婪搜索速度非常块,但基本上找不“准”
• 如何既能找的快、还能找的比较“准”?
– 启发式搜索策略

