算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
深搜之寻路问题
Loading...
From the course by Peking University
算法基础
271 ratings
From the lesson
深度优先搜索（1）
想象我们在一座迷宫里，如何才能找到出口呢？最直观的方法是从入口开始沿着一条路一直走到底，如果遇到分叉路口就选择其中一条道路走下去，如果遇到死胡同就退回到上一个分叉路口，选择另一条道路走下去，如果遇到出口就成功走出迷宫了。这种尽量往深处走的做法即是深度优先搜索(深搜）。深搜算法编程简单，简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，如果不加以优化，时间效率无法忍受。本模块将通过实例继续讨论深度优先搜索算法中优化程序的基本方法“剪枝”，即在设计剪枝判断方法的基础上，避免一些不必要的遍历过程，从而提高算法效率。
Meet the Instructors
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
好，下面我们再讲一个稍微有一点难度的这个深搜问题，叫做这个
寻路问题。呃，这个寻路问题它是POJ上的1724啊。
它说的是呢有N个城市，然后编号呢是
是1到N，城市之间有R条单向的道路，那每一条单向的道路它连接两个城市，有长度和过路费两个属性。
呃，然后这个Bob他要从1号城市走到N号城市，然后他一共只有K块钱
然后这个问题就是要问你，最短共需要走多长的路，就能够到达N。
当然有可能他钱不够，他就到不了N，对吧？那就这个时候呢你就应该输出一个-1。
>> 对，这个题等于就是不，区别于以往的这种最短路问题，啊它这考虑还有一个费用的限制在里面。
>> 对，啊，那这个规模就是城市呢是最多100个。
呃，这个Bob最多有10000块钱，路呢最多有10000条。
>> 那这个对应的话呢，因为
每一条路有一个长度L和一个过路费T，所以我们在输入数据的时候呢首先当然就输入，输入这个
K，N，R，这样三个分别是，呃城市数、Bob的钱数和这个
路，路一共有多少条。之后的话呢就是对每一条路
都会有这样的一个描述，啊分别是这个路的起始。>>起点是s号。
>> s，啊然后呢这个，呃，e就是终，终点的这个，路连接
的这个终点的城市，啊以及这个对应这条路的长度以及
和它本身的这个费用。>>呃，过路费。那这个路它是单向的，就是说 比如这样一个描述就说明从s有路连到e，从s可以走到e。
但是从e不能走到s，它是单向路。
嗯，那这个题目
到底怎么解决呢？可以用深搜的思路来想，那一个基本的思路就是说，我可以从
以1作为起点，做深度优先搜索 遍历整个图，我肯定会，能够找到一条走到N的路对吧？
>> 对。>>但是我们走到N的路可能有很多很多条。>>那就中间选一个最优的呗。
>> 对，那看起来就应该把所有从1到N的路全部都找出来，然后找一个最短的。
可是这样做的时间复杂度看起来 吓人。>>就TLE了。>>对啊，因为你想从1到N它有多少种走法呀，看着像是一个
这种阶乘级别的事情，啊，所以我们得想两个办法。
>> 那我们最直观想就是，呃大家不知道还记不记得
当时我们在做枚举的时候讲那个什么讨厌的青蛙，啊讲提到
说如果我们本身找到的这个，呃就是你已经
知道当前所走过的这个路径的长度，它已经超过了在之前所找到的这个
呃最优的这个路径长度L，就是说你目前可能还没有达到目标的终点N，就已经超过了
已经达到之前达到N这个终点城市所用的那个最优路径L
那么这个时候的话，你现在所走的这条路其实就已经是，呃不可行的。>>对，没必要再走下去了。
>> 所以那我们，就可以直接，直接就放弃就不用往下走了。>>对。>>所以这是一个重要的一个
呃提前终止这个搜索的一个条件限制。>>呃，那这个条件限制还算
比较好想，但是你光写了这个限制呢实际上还是会超时，啊
这个限制关键就是在于你在探索一条路径的时候，你是时时刻刻
每走到一个城市你就会记录从1走到这个城市花了多少钱，以及
以及走，一共你走了多长，对吧?所以你发现这个长度如果已经超过了 我们前面找过的最优路径的长度，我们就不再往下找了。
这个简之，呃这个称之为简之吧，这个或者说优化，这个优化条件还不够强，所以
我们还得另外再想一个这个优化的条件出来，啊否则就会超时。
那这个优化的条件是什么呢？就是，就是我们啊，还可以用一个二维数组
midL[k][m]啊，这个midL[k][m]这个元素呢它表示
我们走到城市k的时候 如果总的路费是m，正好是m啊，在这种情况下
最优路径的长度，我们把它记在midL[k][m]里面
反正你可能会经过好多条路都能到达k，而且到达k的时候
呃总费用都是m，这就有可能对吧？那在这么多种情况下
那个最优路径的长度，实际上就最短路径的长度我们还记在这个变量里面。>>就是说你实际上就是提前记录了一下对应这个
呃到达城市所对应费用下的这个最短的路径，啊。>>对。那，那由于我们很可能
会多次到达同一个城市，而且多次达到同一个城市的时候我们所花的费用都可能是一样的，对吧。
>> 对。>>那这样的话，如果我下次再走到k的时候，我发现总路费恰好为m
但是这一遍我走到k的时候，总路径长度已经超过了前面记下来的那个
最优值啦，那我们当然就不必再走下去了，对吧。
>> 对。>>那这就是一个优化的办法了。>>所以就可以认为说第二个简之实际上是
对于第一的一个，第一个情况的一个中图版的一个考量。>>呃对，就在每一步骤 呃就是
>> 只要达到某一个城市和某一个费用下，就是看一看说它是不是能够已经 呃pk一下我当前的这个
>> 已前找到的 >> 费用、路径、以及这个长度，啊。
>> 那这个思路有了以后，呃程序呢还算比较好写啦，啊。
那我们来看这个程度哦，呃 这个struct Road它代表一条路，那我们起点呢不用记，只记它的终点
费用，呃长度以及这个费用 然后我们要把这个城市的地图给它存下来，然后我们城市
地图用的是邻接表这种存储方式。
呃我们是用一个vector套vector的这个办法，最终这个地图里面每个元素呢都是一个Road啊
那，那这个比如cityMap[i]它就是一个vector
这个vector里面呢每一个元素都记录着一个城市的信息
这个城市是什么啊？就是从i这个城市有路连过去的那个城市
然后那个城市它当然编号就是d对吧，然后，然后从i到d的费，呃长度是L
费用是t，啊。所以对于每一个
城市，i，我们把从i能一步走到的
经过一条路能走到的那些城市全部都塞到这个cityMap[i]这个
数组，也就是vector里面去。>>对，它表达的是跟i相邻的 那些城市的所有的集合。>>哎，对对，相邻这个词用的很准确哦
嗯，好吧，这个下面我们看这里面minLen这个东西是
嗯，代表我们求得的最优径，一开始我们初始化成无穷大，啊
这个，这个代表的是我当前求得的最优路径的这个长度，就是从1到N的最优路径。
而这个totalLen呢是我正在探索的这条路，呃已经走了多长，啊
然后totalCost就是我正在探索的这条路它已经花了多少钱。
呃visited当然就是说用来标记每一个城市它是不是已经走过
然后这个minL就是我们前面所说的minL[i][j]表示从1到i点的，花销为j的
各种走法里面最短的那条路的长度。
好，接下来我们就做这个深搜啦。
啊我iii，你接着讲。>>我们应该先看那个函数啊。>>好，啊对
要有全局观念啊。>>呵呵，我们首先的话呢，在这个微函数里头当然就是首先让它去输入这个
K，N，R这三个值啦，分别就是，呃
>> 钱、城市数和路的数量，嗯。>>郭老师就，上来就钱。>>呵呵。
>> 这个，接着的话呢我们因为有了对应的这个所有的路是吧？所以我们依次的话呢会分别把这个
对应这个路中间的这个，呃，起始，诶不对，是这个
呃路，这个是路的终点，啊对，我们在这个r.d这个struct里面去定义了终点
呃这个长度和费用，啊。然后这个时候的话呢，我们会去判断一下，如果说呢
我们在这个数据当中可能会出现说，起点和终点是绕圈这样的情况下下，闭锁啦。
那么当这个起点和终点不一致的时候，也就是它确实描述的是把一个
城市和另外一个城市连接起来的时候呢，我们就把这个对应的这个 呃
R这个，这个点呢，就把它放到这个cityMap里面去了，啊。然后呢，完了之后呢我们就会呃
首先去初始化一下这个minL，然后这个minL对应的这个每一个值呢都变成是
呃 >> 一个大数。>>一个大数。之后的话呢还要再去初始化一下这个，呃visit
visited，然后呢也让它都先初始化为0，就是都标记为还没有被访问到。之后这个totalLen
和totalCost呢也会被置为是0，啊。>>正在探索的路它的已经走过的长度和花销。
>> 嗯，然后接着的话呢我们就从这个第一个，呃城市出发。>>对。>>标记一下它的这个visited是
1，表示就是我们就访问到了。>>嗯。>>然后的话呢，这个时候的
它的这个minLen，就是目前位置到达这个目标的
长度，最优长度呢是这个，是一个大数。
之后呢我们就可以去调用这个Dfs函数，啊就是递归地去看这个深搜的过程，然后呢它是从这个
第一个城市出发，那么当你呢这个，如果说确实找到了一条这个
呃最优的路径，那么它是，呃本身是会有一个值的，就会去更新之前的这个，minLen的这个
长度的这个数值，啊。如果它本身，它本身计算出来是有具体的值的话呢，它就会去cout这个minLen的长度
就是我们找到那个最优路径的长度。否则的话呢，就让它去输出，就是如果它没有更新，就始终还是这个
我们自己初始化掉的那个大数的话呢，那么就会cout -1。
>> 就说明找不到从1到N的，呃走得起的路，对吧？>>嗯，对。>>啊，关键这个Dfs
呃。>>您来吧。>>那Dfs啊，就是从s开始向
N进行行走，对吧？那我们看一下如果s已经等于N，那就
这就说明我们已经走到了目标城市了。>>嗯。>>那这个时候当然任务就结束了。
不是说结束了，就我们已经找到了一条路了，这个时候我们就要>>比比>>看看我们找到的这条路，
它总的长度是totalLen，跟我们前面记下来的最优路径MinLen去比较一下，看看要不要更新这个MinLen， 然后我们就返回了。
好了，那如果这个S它不等于它，就说明我还正在行走中，那我就要从S出发，
继续往N这个方向走，那怎么走啊，那当然是要考察所有跟S相邻的那些城市。对吧。
那跟S有路连到的那些城市我们是放在CityMap(s)这个
vector里面了，所以我们就便利这个vector，所以这vector里面的每一个元素，
比如说CityMap(s)[i]实际上它就进入了一个城市，这个城市的标号是d，
那我们把D的值取出来放在这个编程里面，那当然这时候S是有路连到d的，
那我们就看Visited里的d，如果d没有被访问过，我们才试图直接，试图再继续从D往下走对吧，D访问过我们就不管它了。
啊，如果D没有被访问过，那我们要从D再往下走了，那我们要从D再往下走的话，这时候产生的费用是多少呢？ 当然就是totalCoast
再加上从这个S走到D的费用，就是这个CityMap(s)[i]变T对吧。>>嗯>>这是，这是 我们从1走到D的费用，就是cost，如果这个cost都已经超过K了，
>> 就超过了这个本身所有的这个用的所有的钱了>>对，包括所有的钱了，对吧，那你就不可能
走到D的这个点了，那我们就直接continue，continue的意思就是说我从i试图去，呃，从
这个S出发，不走D了，我走下一个点看看会怎么样，是吧。那如果这个钱数还够的话，那我们就接着往下，这个时候我们就要判断
如果钱数还够，那这个时候走到D一共会走了多远呢？ 当然就是这个totalLen再加上从S走到D
的这个长度。对吧。这个就是相当于从1号键走到D
的总长。然后我们发现这个总长，它已经超过前面我们找过的，找到的成功的那个最优路径的这个
长度了，那你再走下去显然是没有意义的。对吧。
所以，如果满足这样一个条件我们就会continue。
continue的意思就是说我不走，不走这个D了，这个D走下去没前途。
那还有可能满足另外一个条件也会导致我不走这个D，啊，不走这个D。
呃，另外一个条件是什么呢？就是totalLen+CityMap(s)[i].L，
这是什么，这是跟刚才一样，这还是一个长度对吧.>>嗯。>>这个长度如果已经大于
等于这个MinL[D](cost)，这个MinL[D](cost)是什么啊，复习一下。
>> 就是我们刚刚看到的这个自己定义好的这个二维数组用来保存说
到达D这个城市然后对应使用cost的这样一个花费能够使用到的这个最优路径的程度。>>嗯，对，那就是说，
>> 就是说以前，>>啊，对，我们以前找到了一条路，它走到D，而且走到D的时候
它的cost花费是，>>恰好也是cost.>>那这条路它，它的这个
总长度是MinL，啊，就是最优的情况，那你现在走的这个
走到D的时候情况跟刚才那个是一样，但是你的 总长度已经超过前面的这个最优值了，那我们当然也就没必要>>没必要去走下去了>>没必要再走下去了对吧，所以这样就continue了。>>对，有了这样两个
限制的话呢可就大大提高这个。>>这个速度就足够快了，就不会超时了。好了，那如果前面这两个那条件你都能过，
那就说明我现在真得要往d这个方向去走了对吧，那我们这个当前正在探索这条路的总长度就要增加，
呃，总开销也要增加。
那当然我们这个MinL[d][cost]也要需要更新一下对吧，你当初就是因为这个totalLen
是比这个值要强话，>>强化 >> 才会走到这对吧，如果大的话，前面就肯定没有了，所以我们要更新一下这个值。
包括这个D被访问过这个事情，我们要把它记下来。然后我就从D这个点
继续去进行深度优先搜索，好，那么深度优先搜索结束，
就回到这的时候呢，我们就需要把d这个点访问过的标记给它清零，为什么啊？
因为我们Dfs(d)就意味着从那个S这个点 我走D
再接下去的各种走法对吧。那实际上从S这个点我还可以不走D的，
我要是不走D，也会有另外一种走法，而且在另外一点的走我要不走D我还有另外一个走法，一种走法说不定又回>>走回D>>又会绕回D这个地方，是吧。>>嗯
>> 所以说对于D我们在从D进行，以D为起点进行深度优先搜索之前
我要把它访问标记定位1，但是我们从D回来以后呢，我们还要把D的访问标记记成零，这样以便
从其他路走的时候让它还可以绕回到D啊。
那包括，我们现在 不走D了对吧，因为我们就要进行下一个循环就说的意思就是这个循环的下一次就说我要走下一个点。
>> 其他点。>>呃，我不从D走，我从另外一个点走对吧，那既然不从D走的话，那这个totalCost和totalLen都要恢复到
走到D之前的那个值，所以我们要把它剪掉。然后这样才做好了
呃，从D以外的其他点继续走的这个准备。
呃，那么这个Dfs就是这样了。
其他的部分。>>所以这就是我们这个寻路问题基本的一个
描述。>>对，这最关键的问题就是，最关键的地方就是我们有这个所谓的这个
叫做什么啊？可以称之为简值，实际上就是一种优化，就是使得你能够尽早得，
>> 尽早得结束搜索。>>结束搜索过程，啊这样子 节约了大量的时间，啊这个思路是非常重要的，我们后面还会有更难的
题目，更花俏的这个简之方式，很快就要看到。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
