数据结构与算法之美
王争
前Google工程师
立即订阅
71591 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?

王争 2019-01-18
魔兽世界、仙剑奇侠传这类 MMRPG 游戏,不知道你有没有玩过?在这些游戏中,有一个非常重要的功能,那就是人物角色自动寻路。当人物处于游戏地图中的某个位置的时候,我们用鼠标点击另外一个相对较远的位置,人物就会自动地绕过障碍物走过去。玩过这么多游戏,不知你是否思考过,这个功能是怎么实现的呢?

算法解析

实际上,这是一个非常典型的搜索问题。人物的起点就是他当下所在的位置,终点就是鼠标点击的位置。我们需要在地图中,找一条从起点到终点的路径。这条路径要绕过地图中所有障碍物,并且看起来要是一种非常聪明的走法。所谓“聪明”,笼统地解释就是,走的路不能太绕。理论上讲,最短路径显然是最聪明的走法,是这个问题的最优解。
不过,在第 44 节最优出行路线规划问题中,我们也讲过,如果图非常大,那 Dijkstra 最短路径算法的执行耗时会很多。在真实的软件开发中,我们面对的是超级大的地图和海量的寻路请求,算法的执行效率太低,这显然是无法接受的。
实际上,像出行路线规划、游戏寻路,这些真实软件开发中的问题,一般情况下,我们都不需要非得求最优解(也就是最短路径)。在权衡路线规划质量和执行效率的情况下,我们只需要寻求一个次优解就足够了。那如何快速找出一条接近于最短路线的次优路线呢?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(34)

  • hua168
    我之前是打算生管理,去个小公司,发现也要会开发,去年就毅然去学java,维护懂java会有帮助,也可以搞下大数据……再学一门本职运维开发需要python……
    我就是这样打算的…
    同学说我们学历低只要大专,问我要大家考研究生不?我感觉我不去大公司的话没什么用吧?但一想很多要求本科,自考研究生不知道承认不?尤其公司,再说就算看完都老了吧……意义有多大?

    作者回复: 看得到@hua168同学对职业规划很迷茫。

    我来逐一回答一下你的问题:

    1. 自考学历对你来说没用。绝大部分卡学历的公司,只看第一学历;不卡学历的那部分公司,你自考本科也没必要。自考学历对一小部分人有用,具体哪部分人适合我就不展开讲了,总之不适合你。但是,你没有因为学历自卑,公司这么多,总有不卡学历的。我见过很多大专文凭,技术去贼拉子好的,照样去大公司。

    2. 不管是大公司还是小公司,都会卡年龄。不过所谓的卡年龄并不是说年龄大了就没人要了。而是能力跟年龄不符,年龄一大把却跟人家工作两三年经验能力差不多,要钱还贼高,那估计确实没人要。

    3. 不要再去学java了。如果你还想走技术路线,那就要专精尖,这个我前一条回复说过了。

    4. 我还是说了,对于技术一般的人来说,如果要升管理岗,还是那句话“要有领导气质”,另外,你要包装一下简历,一些很小公司的领导是识别不出来的:)听起来是不入流的建议,但是,我确实是认真的。

    5. 实际上,年龄大了,技术没有太大竞争力,去个安稳的公司很好,比如国企性质的一些互联网保险公司,具体你自己搜搜吧,我这里不方便说公司名字。

    以上建议只针对你本人的情况,并且是我的个人建议。如有不投,你自己斟酌。

    2019-01-19
    31
  • 传说中的成大大
    今天看了A*算法 反而对dijkstra算法理解得更透彻了....
    2019-01-18
    14
  • hua168
    大神,能问一个题外话吗,关于自己人生规划,水平和眼界所限,想不通,
    都说大神级见识很广也多,能给我这个35岁只维护过四五十台linux服务器的运维指条路吗?
    现在很迷茫和压力大~~
    能力如下:
    一.网络:CCNA水平,自过了CCNP忘记了,当过2年网管
    二、维护过asp.net电商网站,3年,只有简单的,兼职网管
    三、linux运维,只在一家电商做了3年多,会
    1.web:nginx、tomcat配置(少用)+php:nignx的rewirte和反代
    2.数据库:mysql、mongoDB、redis 配置及主从,不会mycat、Cetus之类
    3.反代:会nginx、haproxy简单配置
    4.存储:NFS、fastDFS、hadoop简单看了一下
    5.版本控制:只会git及搭建gitlab+jenkins(简单的CI/CD)
    6.监控:简单配置zabbix+shell脚本
    7.虚拟化:kvm安装及配置、docker(k8s还没学)
    8.云计算:openstack只会安装做过实验
    9.测试:只会ab工具
    10.日志:ELK安装配置,还没结合java(在学中)
    11.大数据:没使用过(不会flume、storm、spark、flink、kafka)
    12.脚本:主要是shell为主、会点python

    四、编程能力:自学,没项目经验
    1.前端:
      1)HTML(HTML5不怎看)
      2)css(laiui、学了一下vue)
      3) js、jquery框架、ES6简单看了一下
    2.PHP:语法简单的thinkphp5框架
    3.java:考虑要维护java web在学
    只看了java、jsp及servet、spring、springMVC、spring Boot(这个为主)
    4.python:考虑运维用到
    python:会简单的脚本
    django:只会官网简单的

    问题是:现在已35岁了,失业,怎办?年龄摆在那里,能力好像不强,学历大专。
    能给个建议吗?非常感谢~~

    作者回复: 我下面说的话,可能会伤害到你,不过,我是非常认真的。

    从你对运维相关的技术点的描述上,可以看出,你应该没有在一个稍微大点的公司工作过吧,所以,很多技术都用的不够深,都只是略知一二,没有自己拿得出手的东西。

    建议你去稍微大点公司锻炼一下技术,同时,也能给你的履历加分。

    不过,以你的年龄和履历,去稍微大点的公司可能也不现实了,因为现在好点的公司都卡学历、背景,更别说技术了。

    所以,我建议你找一个运维领域的风口技术去研究,比如你提到的k8s。这种技术才兴起,会的人不多,所以招聘公司都不会太卡学历、经历,只要会,是个人都要,可以借机去个大点的公司。这会是你的一个转折点。

    而且。现在,经济下行,互联网行业都压缩招聘。你正好利用这1、2年,沉下心来,抓住一个技术方向,研究深、研究透。

    还有一条路,那就是做管理岗位。这个要看你有没有领导气质了:)如果有领导范,年龄大,工作经历多,也可以忽悠到一些小公司的管理岗。实际上,对你来说,这条路也是不错的。

    还有一条路,那就是靠去天使轮的创业公司逆袭。这条路有点赌博的意思。不过,如果公司搞大了,你也会青云直上,这辈子都不愁了:)

    2019-01-19
    1
    12
  • yongxiang
    王争老师,我把代码输入运行,并把过程打印出来,发现代码运行的过程跟您说的A*算法的三点区别中的第三点不一样,不会在遍历到目标顶点时退出while循环。您看是不是27行的break只是退出了for循环,无法退出while循环,是不是需要增加以下的修改:
                    if (nextVertex.id == t) {
                        queue.clear();
                        break;
                    }

    作者回复: 嗯嗯 我更新下,是个bug:)

    2019-01-19
    5
  • Bryce
    我来解释一下更新条件仍然和 dijkstra 算法一致的原因,有错误还请大家指出
    实际上不管当前点从哪一个点经过,它与终点的曼哈顿距离都是不变的,所以这部分不需要管,具体到不等式里就是左右都有这一项,故可以消去:
    if ( minVertex.dist + e.w + nextVertex.g < nextVertex.dist + nextVertex.g )
    2019-04-07
    2
  • 且听疯吟
    仔细阅读了下代码,感觉代码中存在错误点,每次应该是取最小的 min(e.w + e.f),但是在下面的代码中只看到了计算出了估值量f,并没有看到对其进行比较大小,不知道争哥觉得对不对?


    if (minVertex.dist + e.w < nextVertex.dist) { // 更新 next 的 dist,f
            nextVertex.dist = minVertex.dist + e.w;
            nextVertex.f = nextVertex.dist+hManhattan(nextVertex, vertexes[t]);
            predecessor[nextVertex.id] = minVertex.id;

            if (inqueue[nextVertex.id] == true) {
              queue.update(nextVertex);
            } else {
              queue.add(nextVertex);
              inqueue[nextVertex.id] = true;
            }
          }

    作者回复: 你搞错了,f=g+h, g=dist, h=hManhattan

    2019-03-19
    1
    2
  • 皇家救星
    我记得以前看过的a*算法介绍还有close和open表,这里好像没提到?

    作者回复: 那就是俩人造的概念 并没有太大意义。

    2019-01-18
    2
  • 杰妮蛇精病
    这篇代码还是没想起明白,来回看了几遍,发现更新的f始终没有被用到,但理论部分指出f用来替换更新的条件。
    2019-10-15
    1
  • 1
    有一点不明白,希望老师能解答一下。实际上,我们可以换一种抽象的思路,把整个地图分割成一个一个的小方块。在某一个方块上的人物,只能往上下左右四个方向的方块上移动。请问障碍物是怎么绕过的呢?

    作者回复: 也可以,你这个抽象成二维数组喽,那就是邻接矩阵的表示方法,可以站人的用1表示,不能站人的方块用0表示,bfs就能得到最优解。

    2019-08-20
    1
  • 隆隆
    优化a*的话 是走扩大方块好 还是设置中转点好呢?

    作者回复: 这个各有利弊,要具体看呢

    2019-02-13
    1
  • 纯洁的憎恶
    对于有大片无变化的地形环境,是否可以采用更大的方块表示,同时增加其与邻接顶点的权值,已表示距离更远。这样可以减少顶点数,简化图的复杂程度,提高执行效率。不过可能造成行走路线中折线过多,不够平滑。
    2019-01-18
    1
  • 『LHCY』
    真实游戏中也是用的小方块来做的吗?比如要往(1,1)方向走,先把模型角度调整,然后移动是一个个小方格走的,因为方格太小使肉眼分辨不出?

    作者回复: 是的,你说的没错!

    2019-01-18
    1
  • Geek_18b741
    对于dijkastra算法来说,当终点出队列的时候dist已经是最小值。所以找到的是最短路径。终于知道为什么bfs得到的是最短路径了。谢谢老师。

    作者回复: 赞

    2019-10-22
  • Leedom
    真的好想去阿里巴巴啊,最近几天疯狂看你讲的东西,阿里三面hash table我理解成Java中的HashTable,所以回答的很烂,这几天看到你讲的才更加深刻,算法和数据结构真的很美妙,好想找到一份满意的工作啊,真的祈求上天让我能更靠近阿里一点,也不知道三面有没有过

    作者回复: 加油,多准备准备,一定有机会!

    2019-09-14
    2
  • Paul Shan
    Dijkstra复杂度分为两部分,一部分是顶点,每个顶点最多入队列和出队列一次,复杂度是Vlog V,每条边最多更新一次,复杂度是E log V,和起来是(V+E)logV ,老师这样的分析是否正确?
    2019-08-07
  • Paul Shan
    思考题
    迷宫算法不适合A*算法,A*算法的本质是利用了终点的距离这一信息来辅助解决问题。离终点的距离对于能否走出迷宫不是一个有效信息。迷宫问题还是采用经典的遍历算法。
    2019-08-07
  • mrlay
    A* 算法得到的结果不一定是最优解的原因是构建最小优先队列的条件从 dist 变成了 f(i), f(i)的大小是由 dist 和 Manhattan 共同决定的。
    2019-07-21
  • Geek_54edc1
    回头路:如果顶点之间路径是双向的,某个顶点的下一步有可能走到之前已经访问过的顶点
    2019-06-04
  • Geek_54edc1
    个人感觉迷宫问题,可以把A*算法稍微改造下:不用再求f值了,直接用dist就行,构建优先队列也用dist,循环结束条件同A*算法,遍历到终点就结束
    2019-05-31
  • Geek_54edc1
    老师您好,if (minVertex.dist + e.w < nextVertex.dist)这个条件是不是可以避免走回头路??

    作者回复: 回头路怎么定义的呢?

    2019-05-31
收起评论
34
返回
顶部