class Shortest::Path::AStar
Public Class Methods
new(dist, cost, graph, start, goal)
click to toggle source
# File lib/shortest/path/astar.rb, line 21 def initialize(dist, cost, graph, start, goal) @graph = graph @dist = dist ; @cost = cost @start = start ; @goal=goal end
Public Instance Methods
search()
click to toggle source
# File lib/shortest/path/astar.rb, line 27 def search been_there = {} pqueue = Shortest::Path::PriorityQueue.new pqueue << [1, [@start, [], 0]] while !pqueue.empty? spot, path_so_far, cost_so_far = pqueue.next next if been_there[spot] newpath = path_so_far + [spot] return newpath if (spot == @goal) been_there[spot] = 1 @graph.neighbors(spot).each do |newspot| next if been_there[newspot] tcost = @cost.call(spot, newspot) next unless tcost newcost = cost_so_far + tcost pqueue << [newcost + @dist.call(@goal, newspot), [newspot, newpath, newcost]] end end return [] end