Class: CSP::Algorithms::Lookahead::Ac3

Inherits:
Object
  • Object
show all
Defined in:
lib/csp/algorithms/lookahead/ac3.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(problem) ⇒ Ac3

Returns a new instance of Ac3.



9
10
11
 
# File 'lib/csp/algorithms/lookahead/ac3.rb', line 9

def initialize(problem)
  @problem = problem
end

Instance Attribute Details

#problem ⇒ Object (readonly)

Returns the value of attribute problem.



7
8
9
 
# File 'lib/csp/algorithms/lookahead/ac3.rb', line 7

def problem
  @problem
end

Instance Method Details

#arc_consistency(arcs, domains) ⇒ Object 



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/csp/algorithms/lookahead/ac3.rb', line 25

def arc_consistency(arcs, domains)
  queue = arcs.dup

  until queue.empty?
    arc, *queue = queue
    x, y = arc.keys.first
    constraint = arc.values.first

    next unless arc_reduce(x, y, constraint, domains)
    return nil if domains[x].empty?

    new_arcs = find_arcs(x, y, arcs)
    queue.push(*new_arcs)
  end

  domains
end

#arc_reduce(x, y, constraint, domains) ⇒ Object

rubocop:disable Naming/MethodParameterName



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/csp/algorithms/lookahead/ac3.rb', line 43

def arc_reduce(x, y, constraint, domains) # rubocop:disable Naming/MethodParameterName
  changed = false
  x_domains = domains[x]
  y_domains = domains[y]

  x_domains.each do |x_value|
    consistent = y_domains.any? do |y_value|
      sat = constraint.satisfies?({ x => x_value, y => y_value })

      sat
    end

    next if consistent

    x_domains -= [x_value]
    changed = true
  end

  domains[x] = x_domains

  changed
end

#arcs(variables) ⇒ Object

Setup arcs between variables



76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/csp/algorithms/lookahead/ac3.rb', line 76

def arcs(variables)
  variables.each_with_object([]) do |variable, worklist|
    constraints = problem.constraints[variable].select(&:binary?)

    constraints.each do |constraint|
      variables_ij = [variable] | constraint.variables # make current variable be the first

      worklist << { variables_ij => constraint }
    end
  end
end

#call(variables:, assignment:, domains:) ⇒ Object 



13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/csp/algorithms/lookahead/ac3.rb', line 13

def call(variables:, assignment:, domains:)
  new_domains = variables.each_with_object({}) do |variable, domains_hash|
    variable_domains = Array(assignment[variable] || domains[variable])

    domains_hash[variable] = unary_check(variable, variable_domains)
  end

  variable_arcs = arcs(variables)

  arc_consistency(variable_arcs, new_domains)
end

#find_arcs(x, y, arcs) ⇒ Object

Returns all (z, x) arcs where z != y



67
68
69
70
71
72
73
 
# File 'lib/csp/algorithms/lookahead/ac3.rb', line 67

def find_arcs(x, y, arcs) # rubocop:disable Naming/MethodParameterName
  arcs.select do |arc|
    arc.any? do |(first, second), _constraint|
      first != y && second == x
    end
  end
end

#unary_check(variable, variable_domains) ⇒ Object 



88
89
90
91
92
93
94
95
96
 
# File 'lib/csp/algorithms/lookahead/ac3.rb', line 88

def unary_check(variable, variable_domains)
  constraints = problem.constraints[variable].select(&:unary?)

  variable_domains.select do |domain|
    constraints.all? do |constraint|
      constraint.satisfies?({ variable => domain })
    end
  end
end