class FifteenPuzzleSolver::AStarSearch
Public Instance Methods
perform()
click to toggle source
# File lib/fifteen_puzzle_solver/a_star_search.rb, line 4 def perform @frontier = [FifteenPuzzleSolver::Node.new(nil, @board, nil)] start while !@frontier.empty? node = @frontier.pop @depth = node.depth @max_depth = @depth if @depth > @max_depth if node.board.valid? @solution = node.path @status = "solved" break end neighbors = node.board.neighbors(node, "udlr") heuristic_sort(@acronym, neighbors) add_to_frontier(neighbors) @explored << node.state end save @frontier.clear end
Private Instance Methods
add_to_frontier(nodes)
click to toggle source
# File lib/fifteen_puzzle_solver/a_star_search.rb, line 35 def add_to_frontier(nodes) nodes.reverse_each do |node| unless @explored.include?(node.state) if @frontier.any? && @frontier.last.astar_function(@acronym) < node.astar_function(@acronym) @frontier.insert(0, node) else @frontier << node end end end end
heuristic_sort(heuristic, nodes)
click to toggle source
# File lib/fifteen_puzzle_solver/a_star_search.rb, line 31 def heuristic_sort(heuristic, nodes) nodes.sort! { |a, b| a.astar_function(heuristic) <=> b.astar_function(heuristic) } end