Class: Longjing::Search::Greedy

Inherits:
Base
  • Object
show all
Defined in:
lib/longjing/search/greedy.rb

Instance Attribute Summary

Attributes inherited from Base

#statistics

Instance Method Summary collapse

Methods inherited from Base

#initialize, #log_progress, #log_solution, #no_solution, #reset_best_heuristic, #solution

Methods included from Logging

#log, #logger, #logger=

Constructor Details

This class inherits a constructor from Longjing::Search::Base

Instance Method Details

#search(problem, heuristic) ⇒ Object 



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/longjing/search/greedy.rb', line 7

def search(problem, heuristic)
  log { "Greedy search" }
  initial = problem.initial
  if problem.goal?(initial)
    return solution(initial)
  end
  initial.cost = heuristic.call(initial)
  frontier = SortedSet.new([initial])
  known = {initial => true}
  until frontier.empty? do
    state = frontier.first
    statistics.expanded += 1
    frontier.delete(state)
    log(:exploring, state)
    log_progress(state)
    problem.actions(state).each do |action|
      new_state = problem.result(action, state)
      statistics.generated += 1
      log(:action, action, new_state)
      if known.include?(new_state)
        logger.debug { "Known state" }
        next
      end
      if problem.goal?(new_state)
        return solution(new_state)
      end
      new_state.cost = heuristic.call(new_state)
      statistics.evaluated += 1
      known[new_state] = true
      frontier << new_state
    end
  end
  no_solution
end