原来 BFS + DFS = A* 😱

作者: Pope怯懦懦地 | 来源:发表于2022-07-05 16:58 被阅读0次

原来 BFS + DFS = A* 😱
Binary Tree(2)
LeetCode 第104题：二叉树的最大深度
133. Clone Graph 复制无向图
BFS和DFS
用Python实现树的BFS与DFS
树的DFS与BFS
DFS BFS
什么时候用BFS，什么时候用DFS
剑指 Offer II 113. 课程顺序

前几天看到一个视频，才知道原来 A* 不过是融合了一下「广度优先搜索」（Breadth First Search）&「深度优先搜索」（Depth First Search），而已😱。三种搜索算法结构都是相似的：

把待搜索的状态放进某个容器⚱️；
以某种方式（队列、栈、优先队列）取出其中一个状态；
检查是否是终点🏁；
以此循环……

虽然不想淌搜索🔍这凼浑水，但还是忍不住「提升一口气」。

来个简单题练练手吧：只允许三种运算 ✖ 2 + 5 -3 ，问如何由 4 得到 56 ？不是去解三元一次不定方程（ $4 + 2x + 5y - 3z = 56$ ）哦，∵和顺序有关😎。

BFS 篇

算上空行，66 行搞定。算法不难理解，但坑🕳️还是蛮多的，调了一晚上🪲。

class BreadthFirstSearch
    def initialize(s, e)
        @queue = 「」
        @visited = 「」
        @edge_from = Hash.new
        @s = s
        @e = e
    end

    def enqueue(v)
        unless @visited.include? v
            @queue << v
            @visited << v
        end
    end

    def dequeue
        @queue.shift
    end

    def get_next_states(v)
        [
            [v * 2, "✖2"],
            [v + 5, "+5"],
            [v - 3, "-3"]
        ]
    end

    def bfs
        return @e if @s == @e

        enqueue(@s)
        
        until @queue.empty?
            if @queue.include? @e
                return @e
            else
                v = dequeue()

                get_next_states(v).each do |u|
                    vv, op = u
                    @edge_from[vv] = [v, op] unless @visited.include? vv
                    enqueue(vv)
                end
            end
        end
    end

    def path_to(s, e)
        if s == e
            return s
        else
            return [path_to(s, @edge_from[e].first), @edge_from[e].last]
        end
    end

    def find_the_path
        path = path_to(@s, @e).join(" ")
        return "🎯: #{path} ➡️ #{@e}"
    end
end

# *2 +5 -3, 4 ➡️ 56
b = BreadthFirstSearch.new(4, 56)
b.bfs
puts b.find_the_path    # 🎯: 4 ✖2 ✖2 +5 +5 -3 +5 ✖2 ➡️ 56

跑 benchmark 发现，上了 10,0000 就跑不动了。

Benchmark.bm do |m|
    5.times do |n|
        big_n = 10**n
        m.report(big_n) do
            b = BreadthFirstSearch.new(4, big_n)
            b.bfs
            b.find_the_path
        end
    end
end

n	user	system	total	real
1	0.000027	0.000003	0.000030	0.000025
10	0.000030	0.000001	0.000031	0.000030
100	0.000486	0.000047	0.000533	0.000583
1000	0.005104	0.000152	0.005256	0.005571
10000	1.429062	0.023612	1.452674	1.497075
100000	172.746792	0.288834	173.035626	173.562669

A* 篇

有了 bfs 的框架之后，小改就可以得到 A* 。引入 class PriorityQueue （36 行），共 107 行。

class PriorityQueue
    def initialize()
        @queue = 「」
    end
    
    def add(priority, item)
        @queue << {priority: priority, item: item}
        @queue.sort_by! { |e| e[:priority] }
        self
    end

    def <<(pritem)
        add(*pritem)
    end

    def empty?
        @queue.empty?
    end

    def include?(v)
        @queue.map { |e| return true if e[:item] == v }
        return false
    end

    def deq
        @queue.shift
    end

    def to_s
        @queue.to_s
    end

    def size
        @queue.size
    end
end

class AstarSearch
    def initialize(s, e)
        @s = s
        @e = e

        @pqueue = PriorityQueue.new
        @visited = 「」
        @edge_from = Hash.new
    end

    def estimate(v)
        (@e - v).abs
    end

    def enqueue(v)
        unless @visited.include? v
            @pqueue << [estimate(v), v]
            @visited << v
        end
    end

    def dequeue
        @pqueue.deq
    end

    def get_next_states(v)
        [
            [v * 2, "✖2"],
            [v + 5, "+5"],
            [v - 3, "-3"]
        ]
    end

    def bfs
        return @e if @s == @e

        enqueue(@s)
        
        until @pqueue.empty?
            if @pqueue.include? @e
                return @e
            else
                v = dequeue()[:item]
                
                get_next_states(v).each do |u|
                    vv, op = u
                    @edge_from[vv] = [v, op] unless @visited.include? vv
                    enqueue(vv)
                end
            end
        end
    end

    def path_to(s, e)
        if s == e
            return s
        else
            return [path_to(s, @edge_from[e].first), @edge_from[e].last]
        end
    end

    def find_the_path
        path = path_to(@s, @e).join(" ")
        return "🎯{#{@depth} steps}: #{path} ➡️ #{@e}"
    end
end

b = AstarSearch.new(4, 56)
b.bfs
puts b.find_the_path # 🎯{8 steps}: 4 ✖2 ✖2 +5 +5 -3 +5 ✖2 ➡️ 56

n	user	system	total	real
1	0.000051	0.000006	0.000057	0.000053
10	0.000080	0.000006	0.000086	0.000086
100	0.000666	0.000088	0.000754	0.000784
1000	0.007072	0.000265	0.007337	0.007460
10000	0.031566	0.001131	0.032697	0.032835
100000	32.630846	0.800102	33.430948	33.487605

确实比 bfs 好一点，但也谈不上神器🪄。

好戏才刚刚开始🥳

A* 真的比 bfs 好吗？我们来看看算 4 ➡️ 1,0000 ：

A* 耗时 0.036s；
bfs 耗时 1.39s 。

看似 A* 完胜，但我们再来看看步数^[1]：

4 ➡️ 1,0000 的散点图（横轴是「步数」，纵轴是「值」）

A* 看似算得快，却需要 172 步，远不是最优解；而 bfs 只用 15 步，虽慢但准。可见，启发式算法也不是银弹🚄。启发式规则没选好，还会南辕北辙。

为什么 (@e - v).abs 这条规则不适合本题？观察一下就可以得到答案。最快的步数应该是搭上了 ✖2 的便车，而我们选用的这条启发式规则虽然前面跑得慢，但后面∵步长过大，只能用线性走，因此反而变慢。那么如何改进这条启发式规则呢？

试试这条呢，让 v 尽量靠近穿过 @e 的 2 的幂线：

def estimate(v)
    if v < 1 or v > @e
        (@e - v).abs
    else
        (@e - v * (2 ** Math.log2(@e / v.to_f).floor)).abs
    end
end

算法	步数	耗时
A*(1,0000)	19	0.001
bfs(1,0000)	14	1.254

可见，A* 速度那是没得说，但它不准啊！∴还是适合那些精度要求不高的地方。

我们来考察下前九的「可能」最短路径长度：

⛳️起点	🏁终点	「可能」最短路径
0	3	1 +5 -3 -3
1	0	1
2	1	1 ✖2
3	2	1 +5 -3
4	2	1 ✖2 ✖2
5	4	1 ✖2 ✖2 ✖2 -3
6	1	1 +5
7	2	1 ✖2 +5
8	3	1 ✖2 ✖2 ✖2
9	3	1 ✖2 ✖2 +5

几乎没有什么趋势，这就是为什么本题的启发式难写的原因吧。

我们甚至可以尝试用「可能最短路径的数学解」作为评估函数，但效果仍然不理想，反而拉低了速度（还比不上 bfs ）：

算法	步数	耗时
A*(1,0000)	18	2.06
bfs(1,0000)	14	1.24

而且误差大到不能看：

4→[5..1000] 的误差

def exgcd(a, b)
    # solve a * x + b * y = gcd(a, b)
    return [1, 0] if b == 0
    x, y = exgcd(b, a % b)
    [y, x - (a / b) * y]
end

def solve_lde_positive(a, b, c)
    # solve the linear Diophantine equation: a * x + b * y = c
    # s.t. min{ x + y }
    gcd = a.gcd(b)
    x_0, y_0 = exgcd(a, b)
    x_0 *= (c / gcd)
    y_0 *= (c / gcd)

    # x >= 0 and y >= 0
    t = (gcd * y_0 / a.to_f).ceil

    x = - x_0 - t * b / gcd
    y = - y_0 + t * a / gcd
    
    [x, y]
end

def estimate(v)
    if v < 1 or v > @e
        (@e - v).abs
    else
        steps_2n = Math.log2(@e / v.to_f).floor
        p_2n = @e / 2 ** steps_2n
        steps_linear_v2p = solve_lde_positive(5, -3, p_2n - v).sum
        steps_linear_s2v = solve_lde_positive(5, -3, v - @s).sum
        # v -> p_2n -> @e"

        steps_linear_s2v + steps_linear_v2p + steps_2n
    end
end

可以笔算吗？

问题一：可以遍历任一数吗？

答一：可以的。只要 $a x + b y = c$ 中满足 $gcd(a, b) \ | \ c$ 。具体的证明懒得写了。然后可以用「扩展辗转相除法」解这个二元一次不定方程。只要满足 $min \{ x + y \}$ 就行了。接着需要去贴近穿过终点🏁的 2 次幂线。但这种解法的缺点是不能保证路径最短。

问题二：如果允许用括号改变计算顺序，如何得到最短路径？

答二：想不出来😖。

思考🤔

一开始 @pan🍳 给我出这题的时候，本不以为意，结果复盘起来还挺有嚼劲。浅，可以凑出来。中等难度，可以试试搜索算法 & 数据可视化。深，可以尝试用数论去解。最重要的是，让我重新认识了启发式算法的优缺点 & 适用场景。

贴个带 debug 的版本吧（可以通过 DEBUG 开关调试信息）：

require "benchmark"
DEBUG = true

class PriorityQueue
    def initialize()
        @queue = 「」
    end
    
    def add(priority, item)
        @queue << {priority: priority, item: item}
        @queue.sort_by! { |e| e[:priority] }
        self
    end

    def <<(pritem)
        add(*pritem)
    end

    def empty?
        @queue.empty?
    end

    def include?(v)
        @queue.map { |e| return true if e[:item] == v }
        return false
    end

    def deq
        @queue.shift
    end

    def to_s
        @queue.to_s
    end

    def size
        @queue.size
    end
end

class AstarSearch
    def initialize(s, e)
        @s = s
        @e = e

        @pqueue = PriorityQueue.new
        @visited = 「」
        @edge_from = Hash.new
        @depth = 0 # 🔎检查递归深度用。
    end

    def estimate(v)
        (@e - v).abs
    end

    def enqueue(v)
        unless @visited.include? v
            @pqueue << [estimate(v), v]
            @visited << v
        end
    end

    def dequeue
        @pqueue.deq
    end

    def get_next_states(v)
        DEBUG && puts("q ⬅ <#{v} ✖ 2 = 🧩#{v * 2} >, <#{v} + 5 = 🧩#{v + 5} >, <#{v} - 3 = 🧩#{v - 3} >")

        [
            [v * 2, "✖2"],
            [v + 5, "+5"],
            [v - 3, "-3"]
        ]
    end

    def bfs
        DEBUG && puts("🚛: #{@pqueue}")
        DEBUG && puts("🚩: #{@visited}")
        DEBUG && puts("🗺: #{@edge_from}")
        DEBUG && puts

        return @e if @s == @e

        enqueue(@s)
        
        until @pqueue.empty?
            DEBUG && puts("🚛: #{@pqueue}")
            DEBUG && puts("🚩: #{@visited}")
            DEBUG && puts("🗺: #{@edge_from}")
            DEBUG && puts

            
            if @pqueue.include? @e
                return @e
            else
                v = dequeue()[:item]
                
                get_next_states(v).each do |u|
                    vv, op = u
                    @edge_from[vv] = [v, op] unless @visited.include? vv
                    enqueue(vv)
                end
            end
        end
    end

    def path_to(s, e)
        @depth += 1
        DEBUG && puts("#{'🪆' * @depth}\t<#{s}, #{e}>")

        if s == e
            return s
        else
            return [path_to(s, @edge_from[e].first), @edge_from[e].last]
        end
    end

    def find_the_path
        path = path_to(@s, @e).join(" ")

        DEBUG && puts
        DEBUG && puts("#🚛: #{@pqueue.size}")
        DEBUG && puts("#🚩: #{@visited.size}")
        DEBUG && puts("#🗺: #{@edge_from.size}")
        DEBUG && puts("#{'🪆' * @depth}")

        return "🎯{#{@depth} steps}: #{path} ➡️ #{@e}"
    end
end

# *2 +5 -3, 4 ➡️ 56
b = AstarSearch.new(4, 56)
b.bfs
puts b.find_the_path # 🎯{8 steps}: 4 ✖2 ✖2 +5 +5 -3 +5 ✖2 ➡️ 56

最后贴个地图🗺的 A* （最后输出实在解决不了，硬编码了下😅）：

require "open-uri"

class PriorityQueue
    def initialize()
        @queue = 「」
    end
    
    def add(priority, item)
        @queue << {priority: priority, item: item}
        @queue.sort_by! { |e| e[:priority] }
        self
    end

    def <<(pritem)
        add(*pritem)
    end

    def empty?
        @queue.empty?
    end

    def include?(v)
        @queue.map { |e| return true if e[:item] == v }
        return false
    end

    def deq
        @queue.shift
    end

    def to_s
        @queue.to_s
    end

    def size
        @queue.size
    end
end

class Point
    attr_accessor :x, :y

    def initialize(ary)
        @x, @y = ary # Should be [x, y] .
    end
    
    def ==℗
        self.x == p.x &&
        self.y == p.y
    end

    def to_a
        [@x, @y]
    end

    # def to_s
    #   "📍<#{@x}, #{@y}>"
    # end

    # def inspect
    #   "📍<#{@x}, #{@y}>"
    # end
end

class AstarSearch
    def initialize(map2d, s, e)
        @map2d = map2d
        @s = s
        @e = e

        @pqueue = PriorityQueue.new
        @visited = 「」
        @edge_from = Hash.new
    end

    def estimate(v)
        [(@e.x - v.x).abs, (@e.y - v.y).abs].max + @map2d[v.x][v.y]
    end

    def enqueue(v)
        unless @visited.include? v
            @pqueue << [estimate(v), v]
            @visited << v
        end
    end

    def dequeue
        @pqueue.deq
    end

    def get_next_states(v)
        x, y = v.x, v.y
        [
            Point.new([x - 1, y - 1]), Point.new([x - 1, y]), Point.new([x - 1, y + 1]), 
            Point.new([x, y - 1]),                            Point.new([x, y + 1]),
            Point.new([x + 1, y - 1]), Point.new([x + 1, y]), Point.new([x + 1, y + 1])
        ]
    end

    def bfs
        return @e if @s == @e

        enqueue(@s)
        
        until @pqueue.empty?    
            if @pqueue.include? @e
                return @e
            else
                v = dequeue()[:item]
                
                get_next_states(v).each do |vv|
                    @edge_from[vv] = v unless @visited.include? vv
                    enqueue(vv)
                end
            end
        end
    end

    def path_to(h, s, e)
        if s == h[e]
            return [s]
        else
            return path_to(h, s, h[e]) << h[e]
        end
    end

    def find_the_path
        h = {}
        @edge_from.map { |k, v| h[k.to_a] = v.to_a }
        path = path_to(h, @s.to_a, @e.to_a) << @e.to_a

        return path
    end
end

# Movement Cost for Terrain:
#   Non-walkable:
#     N/A = Water (~🌊)
#   Walkable:
#     1 = Flatlands (. or @ or X )
#     2 = Forest (*🌲)
#     3 = Mountain (^⛰️)

# Test Map:
#   @*^^^    @ = User start ⛳️
#   ~~*~.    X = The goal tile 🏰
#   **...
#   ^..*~
#   ~~*~X

# ⛳️☁️🌲☁️☁️
# ☁️☁️🌊☁️☁️
# ☁️☁️⛰️☁️🏰
#
#      ⬇️
#
#=> 🚩🚩🚩☁️☁️
#=> ☁️☁️🌊🚩☁️
#=> ☁️☁️⛰️☁️🚩

# m = <<~EOF
#   @.*..
#   ..~..
#   ..^.X
# EOF

m = open("http://www.rubyquiz.com/large_map.txt").read

ASCII2INT = {
    "@" => 1,
    "X" => 1,
    "." => 1,
    "*" => 2,
    "^" => 3,
    "~" => 9999
}

INT2EMOJI = {
    1 => "☁️",
    2 => "🌲",
    3 => "⛰️",
    9999 => "🌊"
}

def preprocess_map(m)
    map2d = 「」

    # 四周注水🌊🌊🌊🌊
    map2d << Array.new(m.split(/\n/).first.size + 2, ASCII2INT["~"])

    start, goal = nil
    m.each_line.with_index do |line, I|
        ary = [ASCII2INT["~"]]
        line.chomp.each_char.with_index do |e, j|
            ary << ASCII2INT[e]
            start = [i + 1, j + 1] if e == "@"
            goal = [i + 1, j + 1] if e == "X"
        end
        ary << ASCII2INT["~"]
        map2d << ary
    end
    map2d << Array.new(m.split(/\n/).first.size + 2, ASCII2INT["~"])
    [map2d, start, goal]
end

map2d, start, goal = preprocess_map(m)

b = AstarSearch.new(map2d, Point.new(start), Point.new(goal))
b.bfs

emoji_map = map2d.map { |row| row.map { |v| INT2EMOJI[v] } }
b.find_the_path.each { |u| v = Point.new(u); emoji_map[v.x][v.y] = "🚩" }

s = Point.new(start)
e = Point.new(goal)

emoji_map[s.x][s.y] = "⛳️"
emoji_map[e.x][e.y] = "🏰"

emoji_map.each do |row|
    puts row.join
end

🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊
🌊⛳️⛰️☁️⛰️🌊🌲🌲🌲🌲⛰️🌲🌊🌊☁️🌊⛰️🌊☁️☁️🌊🌊🌊⛰️🌊☁️⛰️🌊☁️🌲🌊🌲🌲☁️⛰️⛰️🌲⛰️🌲⛰️🌊☁️☁️🌲⛰️⛰️☁️☁️🌊⛰️☁️🌊
🌊🌲🚩🌲🌊🌲☁️🌊⛰️⛰️⛰️🌊🌊☁️🌲🌊🌲☁️🌲🌲☁️🌊🌊⛰️🌲⛰️🌲🌲☁️⛰️🌊🌲⛰️⛰️☁️🌲⛰️☁️☁️☁️⛰️☁️☁️⛰️☁️🌲🌲☁️🌊⛰️🌲🌊
🌊⛰️⛰️🚩🌲🌲🌊☁️🌲⛰️🌲⛰️☁️☁️⛰️🌲🌲☁️🌊🌊🌊☁️🌊🌲☁️🌊⛰️⛰️🌊⛰️🌊⛰️☁️⛰️🌊⛰️🌲🌊🌲🌲☁️🌊🌲⛰️☁️⛰️🌲🌲☁️🌲☁️🌊
🌊🌲🌊🌊🚩🌊⛰️☁️🌊🌲🌊⛰️🌊⛰️⛰️🌲⛰️🌲🌲☁️🌊☁️🌲⛰️⛰️🌲🌊🌊⛰️⛰️🌲🌊☁️⛰️☁️🌲⛰️⛰️🌲⛰️☁️⛰️☁️🌊🌊⛰️⛰️⛰️🌲🌊☁️🌊
🌊🌲☁️⛰️🌊🚩⛰️☁️🌊⛰️☁️⛰️☁️⛰️⛰️🌲🌊⛰️🌊🌊🌲⛰️☁️☁️⛰️🌊⛰️🌊🌊⛰️☁️🌲⛰️⛰️☁️☁️🌲🌲☁️🌲🌲🌊☁️🌊🌊⛰️🌊🌲🌊🌲🌲🌊
🌊⛰️☁️⛰️⛰️🌊🚩☁️🌲🌊🌲🌲☁️🌲🌊🌲⛰️🌲🌊⛰️🌲🌊🌊⛰️☁️⛰️☁️🌊☁️🌊⛰️🌲🌲🌊☁️⛰️⛰️⛰️⛰️🌲☁️🌊☁️🌊🌊🌊⛰️⛰️☁️⛰️☁️🌊
🌊🌲🌊🌊☁️🌲☁️🚩🌊🌊🌊⛰️🌲☁️⛰️🌲🌊🌊🌊🌲⛰️☁️⛰️🌲🌲⛰️🌲⛰️☁️⛰️☁️⛰️🌊🌊🌲🌲🌲⛰️⛰️🌲⛰️☁️🌊⛰️⛰️☁️⛰️⛰️☁️🌊☁️🌊
🌊☁️🌊☁️🌲🌊🌊⛰️🚩☁️🌲🌲☁️🌊⛰️⛰️🌊🌲🌲⛰️☁️⛰️☁️⛰️🌊🌊🌊⛰️☁️🌊☁️⛰️🌊🌊⛰️⛰️☁️🌊⛰️⛰️☁️⛰️⛰️🌊☁️🌊☁️🌊☁️🌲⛰️🌊
🌊☁️⛰️⛰️⛰️🌊🌊🌲🌊🚩⛰️☁️🌊☁️🌲🌊☁️🌊🌊☁️☁️🌊🌲🌊⛰️☁️🌊🌲🌲🌊☁️☁️⛰️🌲🌲🌲🌲🌊☁️🌲🌊⛰️🌊🌊🌲🌊🌲🌲⛰️🌊⛰️🌊
🌊⛰️⛰️⛰️🌲⛰️⛰️🌲🌲☁️🚩🚩🌲☁️⛰️⛰️🌲⛰️⛰️⛰️☁️🌲🌊🌲🌊⛰️⛰️🌊🌲🌊🌊☁️🌊🌲🌲🌲🌲🌊🌊🌊🌊🌲🌲🌲☁️⛰️⛰️🌊🌊⛰️🌊🌊
🌊☁️☁️🌲⛰️⛰️⛰️⛰️⛰️☁️⛰️🌊🚩⛰️🌊☁️⛰️☁️⛰️⛰️🌊🌲🌊⛰️🌲🌊🌲🌲⛰️🌲⛰️☁️🌊🌊🌊🌲⛰️☁️⛰️⛰️🌊🌲🌲🌊🌲🌊☁️☁️☁️☁️☁️🌊
🌊🌲🌲☁️⛰️🌊🌊🌊⛰️🌊🌲🌊🚩🌲🌲🌲☁️🌲🌲⛰️🌊☁️⛰️☁️🌲⛰️⛰️⛰️🌊☁️⛰️☁️☁️☁️🌊☁️🌲🌲⛰️⛰️⛰️⛰️🌊⛰️☁️🌊⛰️🌊☁️🌊🌲🌊
🌊⛰️🌲🌊☁️🌲☁️🌊🌲⛰️☁️🌊🚩⛰️⛰️⛰️⛰️⛰️🌲🌊☁️🌲🌲🌊⛰️☁️🌲⛰️🌲☁️🌊🌊☁️☁️⛰️🌊🌊🌊🌲🌊🌲⛰️☁️🌊🌊⛰️🌲⛰️🌲⛰️⛰️🌊
🌊🌊🌲⛰️☁️⛰️☁️☁️🌲🌲🌊🌲🌲🚩🚩⛰️🌊🌲🌲🌲⛰️🌊🌊🌲⛰️🌲☁️🌲🌊☁️☁️🌊⛰️⛰️🌲🌲🌲⛰️☁️🌲🌊☁️⛰️🌲⛰️⛰️⛰️⛰️☁️🌊☁️🌊
🌊🌲🌊⛰️🌊⛰️🌲🌲⛰️⛰️🌲⛰️⛰️🌊⛰️🚩🌊⛰️⛰️🌲🌊🌊🌊🌲⛰️🌲🌊🌊🌊🌊🌲🌊⛰️⛰️⛰️🌲🌊☁️☁️🌊🌊🌊🌊🌊☁️🌲🌊⛰️🌊🌲☁️🌊
🌊⛰️☁️🌲☁️⛰️🌲⛰️🌲🌲⛰️⛰️⛰️🌊🌲🌲🚩🌲☁️🌊⛰️🌊🌊🌊⛰️☁️☁️🌊🌊🌊🌲🌊🌊⛰️🌲🌊☁️☁️⛰️⛰️☁️⛰️🌊🌲☁️⛰️🌊⛰️🌊🌲🌲🌊
🌊☁️🌲🌲🌲⛰️☁️☁️🌲⛰️🌊🌊🌊🌊⛰️🌊☁️🚩⛰️🌊🌊☁️🌲☁️🌊⛰️☁️⛰️⛰️🌲☁️🌲🌲🌲⛰️🌊⛰️☁️🌲☁️☁️☁️☁️🌊☁️⛰️☁️🌲🌊⛰️⛰️🌊
🌊⛰️⛰️🌊🌊🌊🌊☁️🌲🌲☁️🌲☁️⛰️⛰️🌲🚩⛰️🌊🌊⛰️☁️☁️☁️☁️🌲🌊🌲⛰️🌊🌲⛰️⛰️☁️⛰️🌊🌊🌊⛰️🌲☁️🌊⛰️⛰️⛰️🌊🌲🌲⛰️🌊🌊🌊
🌊⛰️🌊🌊🌲⛰️🌲☁️🌊☁️🌲⛰️⛰️⛰️🌲⛰️☁️🚩🚩☁️🌊🌲☁️☁️☁️🌊🌲🌲⛰️☁️⛰️⛰️🌊☁️⛰️⛰️☁️⛰️☁️☁️⛰️☁️⛰️🌲🌲☁️⛰️⛰️☁️☁️🌲🌊
🌊🌊⛰️🌲🌲🌲🌊⛰️☁️🌊☁️🌊⛰️⛰️⛰️🌲🌊🌊🌊🚩🌲☁️☁️⛰️🌊⛰️⛰️☁️🌊⛰️☁️🌊☁️🌲🌲☁️☁️☁️🌊⛰️🌊🌲🌲🌊⛰️🌊🌊🌲🌲⛰️🌊🌊
🌊🌊🌊🌊⛰️🌊☁️⛰️🌲☁️⛰️🌲☁️🌊🌲☁️🌲🌊🌊⛰️🚩☁️🌊🌲⛰️⛰️🌊🌊🌲🌲☁️🌲☁️🌲☁️🌊⛰️⛰️⛰️☁️☁️⛰️☁️🌊⛰️☁️🌲☁️⛰️🌊🌊🌊
🌊⛰️⛰️🌊☁️☁️☁️⛰️☁️🌲🌊☁️⛰️⛰️🌲🌲🌊⛰️🌊🌲☁️🚩⛰️🌊⛰️🌊🌲☁️☁️☁️☁️⛰️☁️⛰️⛰️🌲🌲🌊☁️🌲☁️⛰️⛰️🌲☁️☁️🌊🌲🌊☁️🌲🌊
🌊⛰️☁️☁️⛰️☁️☁️☁️🌊☁️🌊☁️🌲☁️🌊🌲🌲🌲🌊🌲🌊🌊🚩🚩☁️🌊🌲🌊⛰️⛰️🌊🌊⛰️🌊🌲🌲⛰️🌊🌊⛰️🌲⛰️⛰️🌊🌲☁️🌊🌲⛰️🌲⛰️🌊
🌊🌲⛰️☁️🌲🌲⛰️🌊🌲🌲🌲🌲🌲☁️🌊🌊🌊☁️☁️🌊⛰️🌊☁️🌲🚩⛰️🌲🌊⛰️☁️⛰️⛰️🌲⛰️☁️☁️🌲🌊⛰️☁️⛰️☁️⛰️🌲☁️⛰️☁️🌊⛰️⛰️🌲🌊
🌊🌊☁️☁️☁️🌊🌲⛰️☁️☁️☁️☁️🌲⛰️☁️🌲⛰️⛰️🌲☁️☁️☁️⛰️🚩🌊🌊☁️☁️⛰️☁️🌲🌊☁️🌲🌊☁️🌲⛰️☁️⛰️🌲⛰️🌲⛰️☁️🌲🌲🌲🌲⛰️🌊🌊
🌊⛰️☁️☁️🌊🌲🌲🌲⛰️☁️🌲⛰️🌊🌊☁️🌲🌲🌲🌲☁️🌊🌲⛰️🚩🌊🚩⛰️🌊🌲☁️🌊⛰️🌲⛰️🌊⛰️☁️🌲🌲🌲🌲🌊☁️☁️🌊🌲☁️☁️🌲⛰️🌊🌊
🌊☁️🌊⛰️🌊🌲🌲🌊⛰️⛰️☁️☁️🌊🌊🌊⛰️☁️☁️🌲🌊🌲☁️⛰️🌲🚩🌊🚩☁️⛰️⛰️🌲☁️🌊☁️🌲☁️☁️🌲🌊🌊🌲🌊☁️⛰️🌊☁️🌊🌲🌊🌊☁️🌊
🌊☁️🌲🌲🌲🌊☁️☁️🌊🌲🌲⛰️☁️🌊☁️🌊☁️🌊🌲☁️🌊🌊🌲🌲☁️☁️⛰️🚩⛰️🌊☁️☁️🌊🌲🌊🌊🌊🌊🌲☁️🌲🌲🌊🌊⛰️☁️☁️⛰️☁️⛰️⛰️🌊
🌊🌊☁️🌲☁️🌊⛰️🌲⛰️🌲🌊⛰️☁️🌊🌲☁️☁️🌲🌊⛰️🌊🌊☁️🌲☁️🌲☁️☁️🚩☁️🌲☁️☁️⛰️🌊☁️🌲🌊⛰️⛰️🌲☁️🌊⛰️☁️⛰️🌊⛰️🌲🌲⛰️🌊
🌊☁️🌲⛰️🌊⛰️⛰️🌲☁️⛰️🌲☁️🌊🌲☁️☁️☁️🌲🌊🌊🌊🌲☁️🌲🌲☁️🌊☁️☁️🚩🌲☁️🌲⛰️☁️⛰️🌲☁️⛰️🌲🌊🌲☁️⛰️🌊⛰️🌲🌲⛰️🌲☁️🌊
🌊☁️🌊☁️☁️🌲☁️☁️☁️☁️🌊☁️☁️🌊☁️🌲🌲🌲🌊☁️☁️🌊⛰️☁️☁️🌊🌊⛰️🌲⛰️🚩⛰️🌊⛰️⛰️🌊🌊🌲🌲⛰️☁️🌲🌊🌲🌲⛰️🌲🌲⛰️⛰️🌲🌊
🌊⛰️☁️🌲☁️🌊☁️⛰️☁️🌲🌲⛰️🌲⛰️☁️🌊⛰️⛰️🌲☁️🌊☁️☁️🌲⛰️🌊🌲⛰️🌲🌲🌲🚩🌊🌲🌲☁️☁️⛰️☁️🌊🌊🌲☁️☁️⛰️🌲⛰️🌊🌲☁️🌊🌊
🌊⛰️🌊🌊⛰️🌊🌊🌲☁️🌊⛰️⛰️🌊🌊⛰️🌲🌲☁️⛰️☁️⛰️⛰️⛰️🌲⛰️☁️🌲⛰️⛰️🌊🌊🚩⛰️🚩🌲🌊⛰️🌲⛰️⛰️☁️☁️🌲🌲☁️☁️🌲🌲☁️☁️⛰️🌊
🌊⛰️☁️⛰️🌲☁️🌲⛰️☁️☁️🌲☁️🌊🌊☁️⛰️⛰️🌲🌲🌲⛰️☁️🌲🌊☁️☁️🌊☁️🌲🌲⛰️🌲🚩🌊🚩☁️☁️☁️⛰️⛰️🌊🌲☁️🌊⛰️🌊⛰️☁️☁️🌊🌊🌊
🌊🌊⛰️⛰️☁️⛰️☁️☁️🌲⛰️⛰️☁️🌲🌲☁️🌊🌊⛰️🌲🌊🌲⛰️🌊🌲🌊⛰️🌊🌊☁️🌊🌲☁️⛰️🌊🚩🌊🌲⛰️🌊🌲☁️🌲☁️☁️⛰️☁️⛰️⛰️🌲⛰️🌲🌊
🌊⛰️⛰️☁️🌊🌲⛰️🌊🌊🌲☁️🌊🌊🌲🌊☁️⛰️☁️☁️🌊🌲☁️⛰️☁️🌊🌲🌲☁️⛰️🌲⛰️☁️⛰️🌊☁️🚩🚩☁️🌊🌲☁️🌊☁️☁️☁️🌊🌊☁️☁️🌲☁️🌊
🌊☁️🌊☁️☁️⛰️☁️🌊☁️🌊☁️⛰️🌲☁️🌊⛰️🌲🌊☁️🌊☁️🌲⛰️🌲🌊🌊🌲☁️⛰️☁️🌲🌲🌲🌲🌲🌲🌊🚩🌊🌊🌲⛰️🌊🌊🌊⛰️☁️🌊🌊🌲🌊🌊
🌊🌊☁️🌲☁️☁️⛰️⛰️🌲⛰️🌊🌲☁️🌊🌊☁️🌊☁️⛰️🌊☁️☁️🌊☁️🌊⛰️⛰️⛰️☁️🌲🌊🌲☁️🌲🌲🌊⛰️🚩🌊🌲⛰️🌲⛰️⛰️🌊☁️☁️⛰️🌊⛰️⛰️🌊
🌊🌲☁️⛰️🌲⛰️🌲🌲⛰️🌲☁️⛰️⛰️🌲☁️☁️☁️☁️🌲🌲☁️☁️🌊⛰️⛰️🌊☁️⛰️🌲⛰️☁️🌲🌊🌲⛰️🌲🌲⛰️🚩🚩🚩🌲☁️⛰️⛰️🌲⛰️⛰️⛰️☁️🌊🌊
🌊⛰️🌲⛰️🌊⛰️⛰️🌲☁️🌊🌲🌊⛰️🌲🌊⛰️🌊🌊☁️🌲☁️⛰️🌲⛰️🌊🌲⛰️⛰️🌊☁️🌲🌊☁️🌲🌊☁️🌲🌲☁️🌲🌊🚩🌊🌊☁️🌊🌲⛰️🌊🌊🌲🌊
🌊🌊🌊🌲🌲🌊🌲☁️⛰️☁️🌲🌊☁️☁️🌊🌊⛰️⛰️⛰️🌊⛰️⛰️⛰️☁️🌊🌲🌲🌲⛰️🌲☁️⛰️🌲🌊⛰️🌲🌊⛰️🌊🌲🌊🚩🌲☁️☁️☁️🌊☁️☁️🌊☁️🌊
🌊🌲🌊🌲🌲⛰️🌊🌊☁️⛰️☁️🌲☁️🌊⛰️🌲🌲🌊🌲⛰️⛰️☁️🌲⛰️🌲☁️⛰️🌊🌊🌲🌊🌊🌊🌲⛰️☁️🌲☁️☁️🌊🌊⛰️🚩⛰️☁️🌲⛰️☁️⛰️☁️🌲🌊
🌊☁️🌲⛰️🌊☁️☁️🌲🌊☁️🌲⛰️⛰️⛰️⛰️⛰️🌊🌊⛰️⛰️🌲☁️🌊🌲☁️🌊🌊🌊☁️🌲🌲🌲🌊⛰️☁️🌲☁️☁️🌊🌊🌲🌲🌲🚩🚩🌲🌊🌊⛰️🌲☁️🌊
🌊☁️⛰️⛰️☁️☁️⛰️☁️⛰️🌲⛰️🌊⛰️☁️🌊🌲☁️☁️☁️🌲🌲🌊🌊🌊☁️🌲🌲⛰️🌲🌊🌊🌊🌲⛰️🌲🌲🌲🌊⛰️🌲⛰️🌊⛰️🌊🌊🚩⛰️⛰️🌲☁️🌲🌊
🌊🌲🌲☁️🌲🌲🌊☁️🌲🌲🌊☁️🌲☁️🌲⛰️🌊🌊☁️🌊⛰️☁️🌲⛰️☁️🌊🌊🌲☁️⛰️🌲☁️🌊☁️🌲🌲🌲🌊🌲⛰️⛰️☁️☁️🌊🌲🚩🌊🌲⛰️🌲⛰️🌊
🌊🌊☁️☁️⛰️☁️🌲🌲🌲🌲⛰️☁️🌲🌲🌲🌲🌊⛰️🌊🌲🌲🌲☁️☁️⛰️⛰️⛰️⛰️🌲⛰️☁️🌊🌲⛰️⛰️🌲☁️🌊🌊☁️⛰️🌲🌲⛰️🌲🌊🚩🌲☁️🌊🌊🌊
🌊⛰️🌲🌊⛰️☁️🌊🌲☁️☁️☁️⛰️⛰️☁️⛰️🌊☁️⛰️⛰️☁️☁️🌊⛰️☁️☁️☁️🌲🌲☁️☁️☁️⛰️🌲🌲🌲🌲⛰️🌲🌊🌲🌊🌲⛰️☁️☁️🌊⛰️🚩🌊☁️🌊🌊
🌊☁️☁️☁️⛰️🌊⛰️☁️🌊⛰️⛰️🌊🌊🌊🌊☁️🌲⛰️🌊☁️⛰️🌊🌲🌲🌲🌊🌊⛰️⛰️⛰️☁️🌲⛰️⛰️☁️🌊☁️⛰️🌲🌊🌲🌊🌲🌲⛰️🌲🌲🚩⛰️🌊⛰️🌊
🌊☁️🌊🌊🌊🌊🌊⛰️⛰️☁️🌊🌊🌲⛰️☁️🌊⛰️⛰️⛰️🌲🌲🌊⛰️🌊☁️⛰️🌊⛰️🌊🌲☁️☁️⛰️🌲🌊⛰️⛰️🌲☁️☁️🌲🌊⛰️🌊🌲🌲☁️🌲🚩🚩☁️🌊
🌊🌊⛰️🌲🌲☁️🌊🌲🌲☁️☁️🌲⛰️🌊⛰️⛰️⛰️☁️⛰️🌲⛰️🌊⛰️🌊🌲⛰️☁️🌊🌲🌊☁️⛰️☁️🌲🌲☁️⛰️☁️⛰️⛰️☁️🌊🌲🌲⛰️🌊🌊⛰️🌊⛰️🏰🌊
🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊🌊

Ref:

「用散点图来观察」这个荣誉属于 @pan🍳 。虽然 A* 本身就是以算地图🗺最短路径闻名，但我就是没有联想到😓。我经常说 @pan🍳 是野路子，但不得不承认悟性是真的高😱。 ↩

原来 BFS + DFS = A* 😱
前几天看到一个视频，才知道原来 A* 不过是融合了一下「广度优先搜索」（Breadth First Search）...
Binary Tree(2)
BFS vs DFS for Binary Tree What are BFS and DFS for Binar...
LeetCode 第104题：二叉树的最大深度
1、前言 2、思路采用 DFS 或者 BFS 都可以。 3、代码 DFS： BFS：
133. Clone Graph 复制无向图
bfs dfs
BFS和DFS
DFS BFS
用Python实现树的BFS与DFS
一、BFS与DFS简介在理解动态规划、BFS和DFS一文中，已经集合具体例子，介绍了图的BFS与DFS。但是比较...
树的DFS与BFS
Data DFS BFS
DFS BFS
BFS DFS Dijkstra
什么时候用BFS，什么时候用DFS
参考什么时候用dfs，什么时候用bfs 参考什么时候用DFS，什么时候用BFS? BFS的缺点适用情况 BFS的一...
剑指 Offer II 113. 课程顺序
拓扑排序 bfs dfs