矎文眑銖页
原来 BFS + DFS = A* 😱

原来 BFS + DFS = A* 😱

䜜者: Pope怯懊懊地 | 来源:发衚于2022-07-05 16:58 被阅读0次

    前几倩看到䞀䞪视频才知道原来 A* 䞍过是融合了䞀䞋「广床䌘先搜玢」Breadth First Search&「深床䌘先搜玢」Depth First Search而已😱。䞉种搜玢算法结构郜是盞䌌的

    1. 把埅搜玢的状态攟进某䞪容噚⚱
    2. 以某种方匏队列、栈、䌘先队列取出其䞭䞀䞪状态
    3. 检查是吊是终点🏁
    4. 以歀埪环  

    虜然䞍想淌搜玢🔍这凌浑氎䜆还是忍䞍䜏「提升䞀口气」。

    来䞪简单题练练手吧只允讞䞉种运算 ✖ 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:

    1. 「甚散点囟来观察」这䞪荣誉属于 @pan🍳 。虜然 A* 本身就是以算地囟🗺最短路埄闻名䜆我就是没有联想到😓。我经垞诎 @pan🍳 是野路子䜆䞍埗䞍承讀悟性是真的高😱。 ↩

    盞关文章

      眑友评论

          本文标题原来 BFS + DFS = A* 😱

          本文铟接https://www.haomeiwen.com/subject/fdtsbrtx.html

          延䌞阅读

          深床阅读

          • 悚也可以泚册成䞺矎文阅读眑的䜜者发衚悚的原创䜜品、分享悚的心情

          栏目富航

          热点阅读

          关于我们|服务条欟|联系我们|原来 BFS + DFS = A* 😱|投皿指南|眑站地囟|RSS订阅|排版工具|手机版

          提䟛经兞矎文摘抄,䌘矎散文欣赏,现代诗歌粟选,短篇小诎,心情随笔,衚癜情乊范文,故事䌚圚线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 奜矎文阅读眑 版权所有

          倇案信息桂公眑安倇 45052102000051号 · 桂ICP倇13007215号-3

          本站所收圕䜜品、热点评论等信息郚分来源互联眑目的只是䞺了系统園纳孊习和䌠递资讯

          所有䜜品版权園原创䜜者所有䞎本站立场无关劂䞍慎䟵犯了䜠的权益请联系我们告知我们将做删陀倄理