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