10|搜索算法: 一起来写一个简单的爬虫?
黄清昊
该思维导图由 AI 生成,仅供参考
你好,我是微扰君。
你玩过井字棋的游戏吗?在一个九宫格中,双方轮流用 X 和 O 占领一个格子,某一方的 O 或者 X 三个连成一线时即可获胜。
这样一个简单井字棋的游戏,如果要让你自己写代码实现一个 AI,你会怎么做呢?怎么把博弈过程清晰地表示出来呢?
实际上,许多博弈类游戏的过程,我们都可以用树来表示。根节点就是棋盘为空的状态,终点就是各个棋下完的状态,这样的树也被称为博弈树。下图是井字棋某个局面 3 步内的树状展示:
一般来说,对弈双方在做的事情,其实就是找到这棵树上对于自己最优的一种落子方式,使得之后的每条路径,自己都有必胜或者必不败的策略。如果你想要找出一个 AI 策略,最暴力的方式就是直接遍历每一种情况,找到最优的下法,这就是一个典型的搜索问题了。
事实上,这类博弈的游戏要么是先手必不败,要么是后手必不败,所以对全空间的搜索一定是可以写出一个无敌 AI 的,对证明感兴趣的同学可以去搜索“策梅洛定理”了解。
如果暴力遍历,有多少种情况呢?相信你也发现了,就是这么一个简单的井字棋小游戏,终局的数量非常多,达到了 255168 种。我们可以这样来简单地估计它,第一步有 9 种下法,第二步有 8 种下法,显然通过排列组合的知识,占满棋盘一共有 9!=362880 种下法,当然还需要去掉一些中间获胜不应该继续进行对弈的情况。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
搜索算法在爬虫编写中的应用是本文的重点。文章详细介绍了广度优先搜索算法(BFS)和深度优先搜索算法(DFS)在爬虫领域的实现思路和适用性,并以井字棋游戏和豆瓣用户关系为例进行了生动阐述。通过简单易懂的例子,阐述了BFS和DFS的实现思路和时空复杂度分析,并提供了Python代码示例。总的来说,本文深入浅出地阐述了搜索算法在爬虫编写中的应用,为读者提供了宝贵的技术指导和实践经验。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《业务开发算法 50 讲》,新⼈⾸单¥59
《业务开发算法 50 讲》,新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(3)
- 最新
- 精选
- 第一装甲集群司令克莱斯特2022,勉励自己!
编辑回复: 哈哈加油,希望能在留言区经常看到你
2022-01-032 - qinsi2. 力扣126 3. 力扣794
作者回复: 那可以抓紧补一下题目哦
2022-01-012 - Daneil老师新年快乐!
作者回复: 新年快乐! 可以+v: constant_variation 一起跨年学习~
2022-01-01
收起评论