A*寻路算法需要用到的优先队列

浮云半仙

RT。A*寻路算法中有一步是取出期望代价最小点。用数组的min方法是很缓慢地，会遍历整个数组才返回最小值。可以使用优先队列来优化这个过程。
下面给出一份用ruby实现的大顶堆(我这个是大顶堆，写A*需要的是小顶堆，把两个数的比较符号反过来就好了...)，用法很简单啦，看看下面的那个说明就吼了。
欢迎更神奇的斐波那契堆，配对堆出场(他们两个跑A*貌似会更快哦

RUBY 代码复制下载

class PriorityQueue
    def initialize()
        @heap_size = 0
        @heap_tail = 0
        @heap_data = [0]
    end
    def empty
        @heap_tail == 0
    end
    def size
        @heap_size
    end
 
    def push(value)
        @heap_tail += 1
        @heap_data[@heap_tail] = value
        f = @heap_tail
                #把新插入的节点往上提
        while f != 1 && value > @heap_data[f>>1]  #可以向上去
            @heap_data[f] = @heap_data[f>>1]
            @heap_data[f>>1] = value
            f >>= 1
        end
    end
    def top
        @heap_data[1]  #最大元素在顶端
    end
    def pop
        @heap_data[1] = @heap_data[@heap_tail]
        f = 1
        tmp = @heap_data[@heap_tail]
        @heap_tail -= 1
        while (f << 1) <= @heap_tail
            d = @heap_data[f<<1] - @heap_data[f<<1|1]
 
            #左右节点都比自己小，终止循环
            if d > 0  
                break if @heap_data[f<<1] <= tmp
            else
                break if @heap_data[f<<1|1] <= tmp
            end
 
            if d > 0  #左孩子大就与左孩子交换，否则和右孩子交换
                @heap_data[f] = @heap_data[f<<1]
                @heap_data[f<<1] = tmp
                f <<= 1
            else
                @heap_data[f] = @heap_data[f<<1|1]
                @heap_data[f<<1|1] = tmp
                f = f<<1|1
            end
        end
    end
end
 
#test
q = PriorityQueue.new
gets.split.map{|e| e.to_i}.each {|e| q.push(e)}
while !q.empty
    puts q.top
    q.pop
end

class PriorityQueue


    def initialize()


        @heap_size = 0


        @heap_tail = 0


        @heap_data = [0]


    end


    def empty


        @heap_tail == 0


    end


    def size


        @heap_size


    end


 


    def push(value)


        @heap_tail += 1


        @heap_data[@heap_tail] = value


        f = @heap_tail


                #把新插入的节点往上提


        while f != 1 && value > @heap_data[f>>1]  #可以向上去


            @heap_data[f] = @heap_data[f>>1]


            @heap_data[f>>1] = value


            f >>= 1


        end


    end


    def top


        @heap_data[1]  #最大元素在顶端


    end


    def pop


        @heap_data[1] = @heap_data[@heap_tail]


        f = 1


        tmp = @heap_data[@heap_tail]


        @heap_tail -= 1


        while (f << 1) <= @heap_tail


            d = @heap_data[f<<1] - @heap_data[f<<1|1]


 


            #左右节点都比自己小，终止循环


            if d > 0  


                break if @heap_data[f<<1] <= tmp


            else


                break if @heap_data[f<<1|1] <= tmp


            end


 


            if d > 0  #左孩子大就与左孩子交换，否则和右孩子交换


                @heap_data[f] = @heap_data[f<<1]


                @heap_data[f<<1] = tmp


                f <<= 1


            else


                @heap_data[f] = @heap_data[f<<1|1]


                @heap_data[f<<1|1] = tmp


                f = f<<1|1


            end


        end


    end


end


 


#test


q = PriorityQueue.new


gets.split.map{|e| e.to_i}.each {|e| q.push(e)}


while !q.empty


    puts q.top


    q.pop


end

喵呜喵5

想起了自己以前a*的二叉堆实现，但是实际测试的时候发现速度不如已有二叉堆a*的速度快……

1. class Heap < Array  
   
2.   def [](index); index == 0 ? nil : super(index - 1); end
   
3.   def []=(index,value); return if index == 0; super(index - 1, value); end
   
4.   def initialize *args; super *args; @index = 0; end
   
5.   def value(ele); return ele.value; end
   
6.   def push(ele)
   
7.     child_index = (@index += 1)
   
8.     loop do      
   
9.       parent = self[ (parent_index = child_index / 2) ]
   
10.       break unless parent
    
11.       break if value(parent) <= value(ele)
    
12.       self[child_index] = parent
    
13.       child_index = parent_index
    
14.     end
    
15.     self[child_index] = ele
    
16.   end
    
17.   def shift
    
18.     result = self[1]; self[1] = self.pop
    
19.     @index -= (parent = 1)   
    
20.     loop do
    
21.       child1 = ( child2 = parent * 2 ) + 1
    
22.       break if @index < child1
    
23.       if @index < child2 then child = child1
    
24.       else child = value(self[child1]) < value(self[child2]) ? child1 : child2
    
25.       end
    
26.       break if value(self[parent]) <= value(self[child])
    
27.       self[parent], self[child] = self[child], self[parent]
    
28.       parent = child
    
29.     end
    
30.     return result
    
31.   end  
    
32. end

复制代码

唯道集虚

记得外站有一个很著名的寻路脚本（好像是Khas写的），我记得好像也有用优先排列？（

不过话说目前仍没有更改的主题标签问题……是我的失误。这里表示很抱歉～我这里会尽快联系安安的。