← COMP5511 全部讲次
L02a-3 · 第 2 周

L02a-3 DFS:一条路走到底,撞墙再回头

从栈讲起,用和 BFS 同一棵树一帧一帧跑一遍深度优先搜索,再看它为什么省内存、为什么会陷进去,最后把 BFS 和 DFS 摆在一起比怎么选。

一句话版

DFS(深度优先搜索)从起点出发,挑一个孩子一直往下走,走到没路了再退回最近的岔口,换下一个孩子接着往下。它只需要记住脚下这一条路,所以很省内存;代价是可能一头扎进一条很深的死胡同。

BFS 怎么一层一层扫,见上一页 L02a-2。这一页把 BFS 的队列换成栈,看看会发生什么。

先认识这几个词

词 全称 / 读法 一句人话
DFS Depth-First Search,深度优先搜索 一条路走到底再回头的找法
栈 stack,LIFO(Last In First Out) 一摞盘子:最后放上去的最先拿走
栈顶 top 栈里最后放进去、下一个要被拿走的位置
回溯 backtrack 走到死路后退回上一个岔口,换一条路
完备 complete 只要有解,一定找得到
d / b / m 本课件的记法 树的深度 / 每个节点几个孩子 / 最浅解在第几层

一个类比:在迷宫里贴着一面墙走

进了一个迷宫,你决定每到一个岔口就先走最左边那条。一路往里走,碰到死路就原路退回上一个岔口,换左边第二条。

你只需要记住从入口到现在这一条路,以及路上每个岔口还有哪些没试过。脑子里装的东西很少。

麻烦在于,如果最左边那条通道特别长,长到走不完,你会一直在里面走下去。出口可能就在入口右手边第二个门后面,你永远轮不到它。

类比在哪里失效:

  • 真迷宫的通道总有尽头。搜索树可以无限深,DFS 往下走可能真的永远停不下来。
  • 人在迷宫里会认出「这个路口来过」。算法要靠 Close 表专门去记,不记就会在环里打转。

从零讲起

1. 先补一块:栈(补充)

它解决什么问题

DFS 要求「最新发现的节点最先处理」。这需要一个容器,每次吐出来的都是最后放进去的那个。栈就是干这个的。

直觉

食堂洗好的盘子摞成一摞。新洗的放在最上面,拿的时候也从最上面拿。最后放上去的最先被拿走,英文叫 LIFO,Last In First Out,后进先出。

一步一步看

目标:让 A、B、C 依次入栈再出栈一次,看栈为什么总是先吐出最后放进去的那个。

  1. A 入栈,栈里只有 A。

  2. B 入栈,压在 A 上面。

  3. C 入栈,压在 B 上面。现在从栈顶到栈底是 C、B、A。

  4. 出栈一次,拿走的是栈顶的 C,剩 B、A。

    四行格子演示栈:A 入栈;B 入栈放在左边栈顶;C 入栈放在最左;出栈一次,拿走的是最后放进去的 C,剩 B、A。下方标注左边是栈顶,放进去和拿出来都在这一头

栈只有两个动作:入栈(push,放到栈顶)和出栈(pop,从栈顶拿走)。

怎么判断

拿到一个容器,问一句:最后放进去的,是不是最先出来?是,就是栈。

意思是:栈和队列都是往一头放,区别在从哪头拿。栈从同一头拿,队列从另一头拿。

常见误解

以为函数递归和栈没关系

课件给了 DFS 的递归写法,看起来没有栈。其实每调用一次函数,系统就把它压进函数调用栈,返回时再弹出来,本质和手写的栈一样。

试一下

依次让 P、Q、R 入栈,出栈一次,再让 S 入栈,再出栈一次。两次出栈的分别是谁?最后栈里剩什么?

第一次出栈拿走 R,剩 Q、P。S 压到栈顶,变成 S、Q、P。第二次出栈拿走 S,最后剩 Q、P(Q 在栈顶)。

2. DFS 怎么走

它解决什么问题

和 BFS 一样,手上只有起点、目标和「每个节点能走到哪」。BFS 扫得稳,但要存一整层,层数一深就装不下。DFS 换一种顺序:先往深处走,只存一条路。

从哪来(补充)

DFS 的一个版本,19 世纪就被法国数学家 Charles Pierre Trémaux 研究过,用作走迷宫的策略。迷宫里一条道走到黑、走不通再退回来,正是 DFS 的样子。

出处:Wikipedia: Depth-first search

直觉

把 BFS 的队列换成栈,其余一行不改。

每次从栈顶取一个节点:是目标就停;不是,就把它的孩子压回栈顶。刚压进去的孩子马上又被取出来,所以它总是先往下钻,钻到底才轮到兄弟。

一步一步看

目标:在和 BFS 同一棵树上跟着栈走,看 DFS 先钻完 B 的孩子才轮到 C,Close 顺序和 BFS 不同。

用和 BFS 同一棵树:起点 A,目标 F,孩子从左到右选。栈顶写在左边,压栈时把最先要访问的孩子放在栈顶。青绿粗圈是正在展开的节点,黑圈在 Open 里等着,灰底的进了 Close。

  1. 开始:Open 只有 A。

    第 0 帧:一棵三层的树,根 A,A 的孩子 B、C,B 的孩子 D、E,C 的孩子 F、G。只有 A 是黑圈在 Open 里;Open 栈只有 A,Close 为空

  2. A 出栈,不是目标,孩子 B、C 入栈,B 在栈顶。

    第 1 帧:A 是青绿粗圈正在展开,B、C 变成黑圈;Open 栈从栈顶起是 B、C,旁边注明栈顶在左;Close 是 A

  3. B 出栈,孩子 D、E 压在 C 上面。Open 变成 D、E、C。这一步和 BFS 不一样:BFS 下一个处理的是 C,DFS 先钻进 B 的孩子。

    第 2 帧:B 是青绿粗圈,A 灰底,C、D、E 是黑圈;Open 栈从栈顶起是 D、E、C,Close 是 A、B

  4. D 出栈,没有孩子,进 Close;E 出栈,也没有孩子。B 这一支走完了,栈里只剩 C。

    第 3 帧:A、B、D 灰底,E 是青绿粗圈刚处理完,C 是黑圈;Open 栈只有 C,Close 是 A、B、D、E

  5. C 出栈,孩子 F、G 入栈,F 在栈顶。

    第 4 帧:C 是青绿粗圈,A、B、D、E 灰底,F、G 是黑圈;Open 栈从栈顶起是 F、G,Close 是 A、B、D、E、C

  6. F 出栈,是目标,结束。倒推父节点:F 是 C 生成的,C 是 A 生成的,路径 A-C-F。

    第 5 帧:F 出栈是目标,A 到 C 到 F 的路径描成青绿,G 仍是黑圈留在栈里;Close 是 A、B、D、E、C、F

同一棵树,BFS 的 Close 是 A B C D E F,DFS 是 A B D E C F:DFS 把 B 的孩子查完才轮到 C。

怎么算

把上面的过程写成伪代码,和 BFS 只差一个词:

DFS(start, goal):
    Open = 栈 [start]
    Close = 空
    while Open 不空:
        n = 出栈(取栈顶)
        if n 是 goal: 顺着父节点倒推出路径,返回
        if n 在 Close 里: 跳过
        把 n 的孩子按「最先要访问的最后压」的顺序压栈,记下父节点是 n
        n 放进 Close
    返回 失败

意思是:每一轮取栈顶、查一下、孩子压回栈顶、它进 Close。孩子从左到右访问,压栈就要从右往左压,最左边的孩子才会落在栈顶。

手算时不用真的倒着压。直接把孩子按访问顺序写在栈的最左边,效果一样。

常见误解

以为孩子的顺序无所谓

DFS 的结果完全取决于先走哪个孩子。课件默认从左到右选,题目改成按字母倒序或从右到左,访问顺序整个会变。做题先看题目给的顺序。

以为 Close 表的顺序和路径一样

Close 记的是访问顺序,上面那题是 A B D E C F;路径要从目标倒推父节点,是 A-C-F。两者要分开写。

试一下

同一棵树,目标改成 G,孩子仍然从左到右选。访问顺序是什么?路径是什么?

A、B、D、E、C、F、G。F 出栈不是目标、没有孩子,接着 G 出栈,是目标。路径 A-C-G。

同一棵树,目标还是 F,孩子改成从右到左选。访问顺序是什么?

A 出栈后 C 在栈顶;C 出栈后 G 在栈顶;G 出栈没有孩子;接着 F 出栈,是目标。访问顺序 A C G F,路径 A-C-F。

3. DFS 为什么会陷进去

它解决什么问题

DFS 省内存,但它的完备性有缺口。这一节讲清楚它在哪里会失败、Close 表能补到什么程度,以及为什么它找到的路常常不是最短的。

直觉

DFS 不到死路不回头。只要左边那支一直有孩子,它就一直往下,右边的兄弟永远排在栈底。

如果左边那支是无限深的,或者图里有环让它绕回原处,DFS 就永远出不来。

一步一步看

目标:在左支无限深、目标只在第 2 层的树上跑 DFS,看它怎样一直往左钻,永远轮不到 G。

  1. 根 A 有两个孩子:左边 B,右边 C。目标 G 是 C 的孩子,只在第 2 层。

  2. DFS 先取 B,B 的孩子压在 C 上面。

  3. 左边这一支每个节点都有孩子:B 下面是 D,D 下面是 E,E 下面还有,一直没有尽头。

  4. 栈顶永远是左边那支新生成的节点,C 一直压在栈底,G 永远轮不到。

    一棵树:根 A 的左孩子 B、右孩子 C,C 的孩子 G 是目标、只在第 2 层;左边 B、D、E 用青绿描出 DFS 走的路,E 下面一条虚线表示一直往下没有尽头;旁注 DFS 先钻左边回不来,BFS 第 2 层就能碰到 G

  5. BFS 在同一棵树上,第 2 层就碰到 G 了。

怎么判断

问 DFS 完不完备,分三种情况答:

空间 不检查重复 沿路检查重复(Close 表)
有限、无环 完备 完备
有限、有环 可能绕圈,不完备 完备
无限深 不完备 仍然不完备

意思是:Close 表只挡得住环,挡不住无限深。课件的说法是 complete in finite spaces,「有限空间」这个前提要一起写。

最优性也不保证。DFS 交出的是它第一条碰到的路,那条路不一定最短。

常见误解

以为加了 Close 表 DFS 就完备了

Close 表让 DFS 不会在环里打转,所以在有限空间里完备。树如果无限深,每个节点都是新的,Close 表挡不住,DFS 照样一路往下。

试一下

一张图 S–A、A–B、B–S 三条边构成一个环,另有 S–G。从 S 出发,邻居按字母顺序,DFS 不检查重复状态会怎样?检查了呢?

不检查:S 先走 A,A 走 B,B 又走回 S,S 再走 A……一直在环里绕,永远轮不到 G。检查重复:B 的邻居 S、A 都见过,退回去;最后从 S 走到 G,找到了。

4. DFS 要花多少时间、多少内存

它解决什么问题

DFS 存在的全部理由是省内存。这一节算出它到底省多少,以及时间上要付出什么。

直觉

DFS 任何时刻只关心从根到当前节点这一条路,外加路上每个节点还没试过的兄弟。一个节点的后代全部查完,它就可以从内存里删掉。

时间就没这么好了。最坏情况下目标藏在最右边那支的最底下,DFS 得把整棵树扫完才碰得到。

一步一步看

目标:数 DFS 走到最深处时栈里有多少节点,看它为什么空间只要 O(d·b),时间最坏却到 O(b^d)。

假设每个节点 b 个孩子,树深 d,最浅解在第 m 层。

  1. DFS 往下走到第 d 层时,脚下这条路上有 d 个节点。

  2. 路上每一层,最多还有 b 个兄弟在栈里等着。

  3. 所以栈里最多大约 d × b 个节点,这是空间。

  4. 最坏时目标在最右下角,整棵树的节点都要碰一遍,第 d 层就有 b^d 个,这是时间。下图左边是 BFS 存的一整层,右边是 DFS 存的一条路。

    同一棵分支因子为 2 的搜索树画两遍。左边 BFS 高亮最底下一整层八个节点,同时要存 b^(m+1) 个,空间 O(b^(m+1));右边 DFS 只高亮从根到叶子的一条路径加沿途三个兄弟,空间 O(d·b)

怎么算

空间 O(d·b),时间最坏 O(b^d)。

意思是:空间是 d 乘 b,是乘法,随树深线性增长;时间是 b 的 d 次方,是指数。

和 BFS 对比:BFS 时间、空间都是 O(b^(m+1))。DFS 的空间小得多。时间上,指数里 DFS 是 d、BFS 是 m,而 d 可以远大于 m,所以 DFS 的时间通常更差。

注意 O(d·b) 说的是不保存全局 Close 表的树式 DFS。要是把访问过的节点全部存下来,空间就不止这些了。

常见误解

以为 DFS 又省内存又快

省内存是真的,快不一定。它可能一头扎进一条没有解的深分支,在里面浪费大量时间。课件对 DFS 的那句评价就是这个。

试一下

b = 3、d = 20、m = 4。DFS 的空间量级 d·b 是多少?BFS 的空间量级 b^(m+1) 是多少?

DFS:20 × 3 = 60。BFS:3⁵ = 243。DFS 的空间只有几十个节点,BFS 要几百个;树再大一些,差距会按指数拉开。

5. BFS 和 DFS 怎么选

它解决什么问题

两个算法代码只差一个容器,性质却几乎处处相反。考试常把它们摆在一起问,实际用时也得挑一个。这一节把两者并排放好。

直觉

BFS 是先查兄弟再查孩子,一圈一圈往外推。DFS 是先查孩子再查兄弟,一条路钻到底。

一个占内存换来「最短」,一个省内存但什么都不保证。

一步一步看

目标:按数据结构、访问顺序和四把尺子逐条对照 BFS 与 DFS,看两者性质几乎处处相反。

  1. 先看数据结构:BFS 用队列,DFS 用栈。
  2. 再看访问顺序:BFS 先兄弟后孩子,DFS 先孩子后兄弟。
  3. 再拿四把尺子逐条比:
BFS DFS
完备性 有限分支、有有限深解时完备 有环或无限深时不完备;加 Close 表后在有限空间完备
最优性 一定找到边数最少的路 不保证
时间 O(b^(m+1)) 最坏 O(b^d),通常更差
空间 O(b^(m+1)),很糟 O(d·b),很好
典型用途 两点间最短路径、找所有连通分量 需要回溯的问题、找环、拓扑排序
  1. 最后按题目条件挑。

怎么判断

三条规则按顺序问:

  • 要保证边数最少,而且解不深:选 BFS。
  • 内存吃紧,又不要求最短:选 DFS。
  • 有像样的启发函数:直接上 A*,见 L02b-2。

意思是:先看题目要不要最短,再看内存够不够。两条都卡住时,就该考虑带估计的启发式搜索。

常见误解

答「BFS 慢、DFS 省内存」就当答完了

要点名维度。BFS 的死穴是空间,时间反而通常比 DFS 好;DFS 省空间,但不完备、不最优、最坏时间更差。

试一下

迷宫很大、内存很紧,只要找到任何一条出路就行。选 BFS 还是 DFS?换成「要找最少步数的出路,迷宫不大」呢?

第一种选 DFS:只要一条路、不要最短,内存又紧,DFS 正合适。第二种选 BFS:要最少步数,迷宫不大,内存撑得住。

把它们串起来

DFS 和 BFS 的代码只差一处:Open 用栈,不用队列。

栈后进先出,刚生成的孩子马上被取出来,所以 DFS 总是先往深处钻,钻到底才回头查兄弟。这个顺序让它只需要存一条路和沿途兄弟,空间是 O(d·b)。

同一个顺序也带来它的毛病。左边那支要是无限深,或者图里有环,它就出不来;Close 表能挡住环,挡不住无限深。它交出的是第一条碰到的路,不保证最短;最坏要扫完整棵树,时间 O(b^d)。

两者一对照就是一张表:BFS 拿内存换最短,DFS 拿保证换内存。题目要最短选 BFS,内存紧又不要最短选 DFS。两样都不想放弃,就得给搜索加上「离目标还有多远」的估计。

课件里的坑

  • [页码提醒] p.32–33 是同一页动画的两帧,页脚都印着「31」;那棵树里有个节点就叫 S,但起点是 A,别被字母混淆(p.32–33)
  • [读题提醒] DFS 的结果依赖孩子的排列顺序,课件默认从左到右选;题目改成别的顺序,答案整个会变(p.29)
  • [完备性限定词] 课件写的是 complete in finite spaces,加了 Close 表也只在有限空间完备(p.36)
  • [空间口径] O(d·b) 是不额外保存全局访问集合的树式 DFS 的空间(p.38)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写栈的四个字「后进先出」;再拿 21 个节点那棵树,自己画 Open 栈一步步写出访问顺序,对照完整例题;然后过一遍三道课件例题;最后回查两个最容易错的地方:Close 表只让 DFS 在有限空间完备,DFS 的时间通常比 BFS 差。

必背

  1. DFS 的 Open 表是栈(LIFO):从栈顶取、孩子也压回栈顶,所以先访问孩子、再访问兄弟
  2. DFS 结果依赖孩子的顺序,课件默认从左到右选;压栈时把最先要访问的孩子放在栈顶
  3. DFS 在无限深或有环的空间里不完备;沿路检查重复状态(Close 表)后只在有限空间完备,而且不保证最短
  4. 不保存全局 Close 表的树式 DFS 空间 O(d·b):只存一条路径加沿途兄弟;最坏时间 O(b^d),d 可以远大于 m
  5. BFS 用队列、费内存、保证边数最少;DFS 用栈、省内存、不保证最短;内存吃紧又不要求最短选 DFS

课件例题

例 1(课件 p.32–33):按 DFS 写出一棵 21 个节点的树的访问顺序

见下方完整例题。

例 2(课件 p.34):八数码用 DFS 展开是什么形状?

题面:同一个八数码问题改用 DFS 展开,课件批注 Never come back until there is a dead end。和 BFS 的展开图比,形状有什么不同?

提示

想一想 BFS 每次扫完哪一部分才往下,DFS 呢。

解答

DFS 不到死路不回头,展开图是又细又长的一条线。BFS 一层扫完再下一层,展开图是又宽又浅的扇形。同一个问题,Open 表换个容器,搜索树的形状就完全不同。

例 3(课件 p.35):DFS 在小图上找到的是哪条路?

题面:一张无向图,边是 S–A、S–B、A–B、A–C、C–G、B–G。从 S 出发找 G,用 DFS。课件给出的解是哪条路?它是最短的吗?

六个节点的小图:S 在顶端,A、B 在中间,C、G 在底部;双向绿箭头连着 S–A、S–B、A–B、A–C、C–G、B–G,目标 G 被红圈圈出
图片来源:COMP5511 Lecture 2, p.35
提示

邻居按字母顺序,S 先走哪个?从那里再一路往下走。

解答

课件里 DFS 从 S 先走 A,再从 A 走到 C,再从 C 走到 G,得到 S-A-C-G,共 3 条边。

图上还有 S-B-G,只有 2 条边,更短。这道题说明 DFS 找到的第一条路通常不是最短的,所以 DFS 不保证最优。

完整例题

题面(课件 p.32–33):一棵 21 个节点的树,起点是 A。A 的孩子是 B、C、D;B 的孩子是 E、F;E 的孩子是 K、L;K 的孩子是 S;L 的孩子是 T;F 的孩子是 M;C 的孩子是 G、H;G 的孩子是 N;H 的孩子是 O、P;P 的孩子是 U;D 的孩子是 I、J;I 的孩子是 Q;J 的孩子是 R。孩子从左到右选,用栈做 DFS,写出访问顺序。

起点为 A 的有向树:A 指向 B、C、D;B 指向 E、F,E 指向 K、L,F 指向 L、M;C 指向 G、H,H 指向 O、P;D 指向 I、J,I 指向 P、Q,J 指向 R;K、L、G、P 往下分别指向 S、T、N、U
图片来源:COMP5511 Lecture 2, p.32

约定:栈顶写在最左边。展开一个节点时,把它的孩子按「最先要访问的放在栈顶」压回去。

解法:

  1. Open 只有 A。取 A 展开,Open 变成 B, C, D。
  2. 取 B 展开,Open 变成 E, F, C, D。
  3. 取 E 展开,Open 变成 K, L, F, C, D。
  4. 取 K 展开,Open 变成 S, L, F, C, D。这里的 S 只是一个节点名,不是起点。
  5. 取 S,没有孩子。Open 变成 L, F, C, D。
  6. 取 L 展开,Open 变成 T, F, C, D。取 T,没有孩子。
  7. 取 F 展开,Open 变成 M, C, D。取 M,没有孩子。B 这一整支走完了。
  8. 取 C 展开,Open 变成 G, H, D。取 G 展开得 N,取 N。
  9. 取 H 展开,Open 变成 O, P, D。取 O;取 P 展开得 U,取 U。
  10. 取 D 展开,Open 变成 I, J。取 I 展开得 Q,取 Q;取 J 展开得 R,取 R。Open 空了。
  11. 答案:A B E K S L T F M C G N H O P U D I Q J R。 一共 22 步,最后一步的 Close 表正好就是这个顺序。

要点:DFS 先访问孩子,再访问兄弟。B 下面所有后代访问完,才轮到 B 的兄弟 C。

答题格式:画一张三列表「步 / 展开 / Open」,每行写一次取栈顶;最后单独一行写访问顺序。

变式题(先自己做)

(1) 改编自课件 p.32–33:同一棵树,孩子改成从右到左选,DFS 的前五个访问节点是什么? (2) 改编自课件 p.35:同一张图 S–A、S–B、A–B、A–C、C–G、B–G,DFS 改成邻居按字母倒序访问。找到的路径是什么?是最短的吗? (3) 自编情境:一棵分支因子 b=3 的树,最浅解在第 m=4 层,树深 d=20。BFS 和 DFS 哪个更可能先撑爆内存?哪个更可能跑很久?

提示

(1) 孩子顺序反过来,栈里压回去的顺序也跟着反。(2) 倒序时 S 先走 B。(3) 把 b、m、d 代进 O(b^(m+1))、O(b^d)、O(d·b)。

判分点与答案(非官方评分标准)

判分点:① (1) 要按栈的顺序推,不能凭感觉写;② (3) 时间和空间要分开答,各自点名公式。

(1) A D J R I。A 的孩子从右到左先走 D,D 先走 J,J 往下是 R,R 没有孩子,再回到 D 的另一个孩子 I。

(2) S-B-G。S 的邻居倒序是 B、A,先走 B;B 的邻居倒序是 S、G、A,S 已见过,走 G,到达目标。这次碰巧是最短的 2 条边,但这是孩子顺序凑巧,DFS 本身不保证。

(3) 内存:BFS 的空间是 O(b^(m+1)),要同时存一整层,更容易撑爆;DFS 只存一条路加兄弟,O(d·b)。时间:DFS 最坏 O(b^d),d 远大于 m,可能一头扎进没有解的深分支,更可能跑很久;BFS 只到解那一层。

闪卡自测

1. 栈是什么规则?DFS 为什么用栈?

后进先出(LIFO)。刚生成的孩子最先被取出,所以 DFS 总是先往深处走(p.31)。

2. 把 BFS 改成 DFS 要改哪一处?

只需把 Open 的数据结构从队列换成栈,其余代码几乎一模一样(p.22、p.31)。

3. DFS 的递归写法里栈在哪?

在函数调用栈里。每次递归调用压栈,返回时出栈,本质和手写的栈一样(p.30)。

4. DFS 在什么情况下不完备?加了 Close 表之后能完备到什么程度?

在无限深的空间里、或者有环的空间里会失败。沿路径检查重复状态之后,只能保证在有限空间里完备,无限深的树照样陷进去(p.36)。

5. DFS 的空间为什么是 O(d·b) 而不是指数?

只需要存从根到当前叶子的一条路径,外加路径上每个节点尚未展开的兄弟。路径最长 d 层,每层最多 b 个兄弟,所以是 d × b(p.38)。

6. 为什么 DFS 的时间是 O(b^d),而 BFS 是 O(b^(m+1))?

最坏情况下 DFS 的目标在最右边那支上,得扫完整棵树,所以指数是 d;BFS 不碰比解更深的层,指数是 m。d 可以远大于 m(p.15、p.37)。

7. DFS 和 BFS 谁先访问兄弟、谁先访问孩子?各适合什么用途?

BFS 先兄弟后孩子,适合找两点间最短路径;DFS 先孩子后兄弟,适合需要回溯的问题、找环、拓扑排序(p.39)。

8. p.35 那张图上 DFS 找到哪条路?说明了什么?

S-A-C-G,3 条边;图上有 2 条边的 S-B-G。说明 DFS 不保证最短(p.35、p.36)。

下一讲

盲目搜索讲完了。下一页给搜索加上「离目标还有多远」的估计,从最简单的爬山法开始,见 L02b-1。

下一讲 →
L02b-1 L02b-1 启发式与爬山法:雾里只看脚下往高处走

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。