在Ruby中实现DFS

Question

我正在尝试使用深度优先搜索算法解决水桶问题。 但是，我遇到了一个问题，即有时会得到无法达成的状态。 目前，我只实现了填充和倒空这两种操作。

Example:
  2 jugs, 3l, 4l, I need 4
input :> 2,3,4,4
Output :> inf. loop of [[3,3],[3.3]]

我正在使用Node类。

class Node
 attr_reader :parent, :state, :childrens

 def initialize(parent, state, childrens)
   @parent = parent
   @state = state
   @childrens = childrens
 end

end

还有一个主要的类应该实现深度优先搜索（DFS）

require_relative 'node'

$solutions = Array.new

def DFS(node, bag, target)

  puts "Starting Function"
  node.state.each do |s|
    s.size.times do |b|


=begin
     FILL FUNCTION
=end

      # Loome uue seisu
      n_state = Marshal.load(Marshal.dump(s))
      n_state[b][1] = n_state[b][0]
      n_state = [n_state]
      # Kontrollime, kas on juba olnud
      if bag.has_key?(n_state)
       return bag
      end

      # Kontrollime, kas on lahendus
      solution = n_state.select{|k| k.any?{|v| v[1] == target}}[0]

      if solution
        $solutions.push(n_state)
        return bag
      end


      bag[node.state] = n_state.to_s + " FILL "
      child = Node.new(node, n_state, nil)
      puts child.state.to_s + " : " + bag.to_s
      bag = DFS(child, bag, target)

=begin
     EMPTY FUNCTION
=end

  # Loome uue seisu
  kann = Marshal.load(Marshal.dump(s))
  kann[b][1] = 0
  n_state = [n_state]
  # Kontrollime, kas on juba olnud
  if bag.has_key?(n_state)
    return bag
  end

  # Kontrollime, kas on lahendus
  solution = n_state.select{|k| k.any?{|v| v[1] == target}}[0]

  if solution
    $solutions.push(n_state)
    return bag
  end


  bag[node.state] = n_state.to_s + " Empty "
  child = Node.new(node, n_state, nil)
  puts child.state.to_s + " : " + bag.to_s
  DFS(child, bag, target)



end
end



end

=begin
Sisendi Muster järgimne :
"a , a * [x] , d" ,
kus a on veekannude arv,
 a*[x] on veekannued mahud
  ja d on soovitud lõpptulemus
Näide:
2 , 3 , 4 , 2
Mul on 2 veekannu 3l ja 4l. Tulemuseks tahan saada 2l.
=end

# Küsime sisendi

input = gets.split(/,/).map{|p| p.to_i} # Saame sisendi lõigume tükkideks "," järgi ja muudame kõik osad intideks (to_int)

# Määrame ära keskkonna.

count = input.shift # saame koguse
start = (1..count).map{[input.shift, 0]} # saame iga veekannu mahu
target= input.shift # viimane element on meie soovitud tulemus

step = 0
states = {start => ""} # Hashmap, kus start on võti ja "" väärtus.

 current = states.keys
start_node = Node.new(nil, current, nil)
 states = {start => ""}

puts "GIVING STATE : " + current.to_s
DFS(start_node, states, target)
puts "SOLUTIONS FOUND :"
puts $solutions.to_s

- Fiedberg Nichenko

---

我有一个使用广度优先搜索的解决方案。 - Fiedberg Nichenko

Answer 1

我无法弄清楚问题出在哪里，特别是在我不理解的语言注释中，所以我从头开始做了。

• 将生成新状态的代码与处理已尝试过的状态的代码分离。这使得确保您生成的状态有效变得更加容易。
• 我没有使用节点的概念，因为在这种情况下它们是不必要的。
• 每个状态由一个数组表示，其中包含每个桶中数量的值；
• DFS返回一个状态数组，该数组将您从目标状态带回到起始状态。如果需要，您可以更改排序方式。

def drop_onto(state, from_max, to_max, from, to)
  
  if (state[from] == 0 || state[to] == to_max)    #From is empty or To is full
      return state        
  end
  
  new_state = state.dup
  missing_to = to_max - state[to]
  if state[from] > missing_to then    #Fill to
      new_state[from] -= missing_to
      new_state[to] += missing_to
  else                                #Empty from
      new_state[to] += new_state[from]
      new_state[from] = 0
  end
  
  return new_state
end


def DFS(buckets, visited, state, goal)
  
  return false if visited[state]
  return [[state]] if state == goal   #We reached our goal!
  visited[state] = true

  state.each_with_index do |from_quantity, from|
      state.each_with_index do |to_quantity, to|
          next if from == to  # Don't drop onto itself
          
          new_state = drop_onto state, buckets[from], buckets[to], from, to
          try_dfs = DFS buckets, visited, new_state, goal
          return try_dfs.push state if try_dfs    #In case we found something, add state to the list
          
      end
  end
  
  return false
end

buckets = [3, 5, 8]
visited = Hash.new
start = [0, 0, 8]
goal = [0, 4, 4]
print DFS buckets, visited, start, goal

- SlySherZ