第一百三二章 机器人罗比（下）
洛杉矶神探小说推荐阅读：娇软美人在末世封神了、世界末日之毒液、大佬的小人鱼揣崽跑路了、特案三组、腐烂国度之活下去、末日聚集地、一价氢氯钾钠银、御鬼者传奇、暗影熊提伯斯的位面之旅、这个文字冒险游戏绝对有毒、末世满级大佬有异能空间、从黑科技到超级工程、快穿之养老攻略
“唰唰！”，牛仔从大树上跳下来。
然后，他看见了倒在地上，奄奄一息的小机器人罗比。
“哥们，发生啥事了？”
杨成看了看小机器人，脸上很是诧异。
就在这时，罗比开口了，它的声音很微弱。
“主人...”
“罗比的寻路逻辑被破坏了...”
“想让罗比带你们回家...”
“请先修复...”
杨成听到这里，已经有了些眉目。
这个关卡敢情是考寻路算法啊。
对于要判定地图中两点间的路径，有一种简单粗暴的做法。
使用深度优先遍历！
它的实现方式很简单，但有2点不足：
1.效率低下
2.它找到的路径不一定是最短路径
第二点尤其致命，绕远路白费力气。
所以这个问题应该是寻找图中两点的最短路径。
当前的地图有什么特点？
它并没有“权重”。
对于有权重的地图，寻找最小权重和路径，有一种经典的算法。
迪杰斯特拉最短路径算法。
但这个地图是没有权重的。
事实上，这里也可以应用迪杰斯特拉算法，但效率不高，而且需要大量的额外空间。
怎样找到一种，足够简单，实现方便，而且效率不会很低的最短路径算法呢？
杨成想到了老朋友。
广度优先遍历算法。
这个方法可以做到！
但是，我们得给它做点小小的改变。
-------------------------------
这个最短路径问题，迪杰斯特拉算法经过优化后的时间效率是O（N*logN），而广度优先遍历是O（N）的，而且迪杰斯特拉需要的额外空间也更多。
http://www.luoshanjishentan.com/yt29375/12946758.html
请记住本书首发域名：www.luoshanjishentan.com。洛杉矶神探手机版阅读网址：www.luoshanjishentan.com
然后，他看见了倒在地上，奄奄一息的小机器人罗比。
“哥们，发生啥事了？”
杨成看了看小机器人，脸上很是诧异。
就在这时，罗比开口了，它的声音很微弱。
“主人...”
“罗比的寻路逻辑被破坏了...”
“想让罗比带你们回家...”
“请先修复...”
杨成听到这里，已经有了些眉目。
这个关卡敢情是考寻路算法啊。
对于要判定地图中两点间的路径，有一种简单粗暴的做法。
使用深度优先遍历！
它的实现方式很简单，但有2点不足：
1.效率低下
2.它找到的路径不一定是最短路径
第二点尤其致命，绕远路白费力气。
所以这个问题应该是寻找图中两点的最短路径。
当前的地图有什么特点？
它并没有“权重”。
对于有权重的地图，寻找最小权重和路径，有一种经典的算法。
迪杰斯特拉最短路径算法。
但这个地图是没有权重的。
事实上，这里也可以应用迪杰斯特拉算法，但效率不高，而且需要大量的额外空间。
怎样找到一种，足够简单，实现方便，而且效率不会很低的最短路径算法呢？
杨成想到了老朋友。
广度优先遍历算法。
这个方法可以做到！
但是，我们得给它做点小小的改变。
-------------------------------
这个最短路径问题，迪杰斯特拉算法经过优化后的时间效率是O（N*logN），而广度优先遍历是O（N）的，而且迪杰斯特拉需要的额外空间也更多。
http://www.luoshanjishentan.com/yt29375/12946758.html
请记住本书首发域名：www.luoshanjishentan.com。洛杉矶神探手机版阅读网址：www.luoshanjishentan.com