Блог

Я работаю с графами, и я хотел бы подсчитать все возможные пути от заданной вершины X до заданной вершины Y.

Это алгоритм, который я придумал:

 class Graph
  def paths_from(vertex_a, vertex_b, count = 0, visited = Array.new(@vertices.length, false))
    return count if @vertices.none?(vertex_b) || @vertices.none?(vertex_a)

    count  = 1 if vertex_a == vertex_b
    visited[@vertices.index(vertex_a)] = true
    @net[@vertices.index(vertex_a)].each do |vertex|
      paths_from(vertex, vertex_b, count, visited) unless visited[@vertices.index(vertex)]
    end

    count
  end
end
 

Используя рекурсию, я ожидаю прохождения df по графу. Тем не менее, я продолжаю получать 0 вместо ожидаемого значения, приведенного ниже графика:

 describe Graph do
  context 'can output all possible from vertex a to vertex b.' do
    let(:subject) { Graph.new(%w[a b c d e]) }
    before(:each) do
      subject.add_edge(0, 1)
      subject.add_edge(0, 2)
      subject.add_edge(0, 4)
      subject.add_edge(1, 2)
      subject.add_edge(1, 4)
      subject.add_edge(2, 3)
      subject.add_edge(3, 1)
    end
  
    it 'example #1' do
      expect(subject.paths_from('a', 'f')).to eql 0 # => should output 0 and it does.
    end

    it 'example #2' do
      expect(subject.paths_from('f', 'a')).to eql 0 # => should ouput 0 and it does.
    end

    it 'example #3' do
      expect(subject.paths_from('a', 'b')).to eql 2
    end
  end
end
 

Сомнение № 1: я проверил советы по подходу geeksforgeeks относительно алгоритма: в нем говорится, что я должен вернуться. Что это такое и как я могу это сделать? Я предполагаю, что они ссылаются на переменную visited … но я понятия не имею, как это сделать.

Я отброшу определение класса на всякий случай.

 class Graph
attr_accessor :net, :vertices

  def initialize(vertices = [])
    @net = Array.new(vertices.length) { [] }
    @vertices = vertices
  end

  def add_edge(vertex_a, vertex_b)
    return if @net[vertex_a].nil? || @vertices[vertex_b].nil?

    @net[vertex_a] << @vertices[vertex_b]
  end
end
 

Сомнение № 2: если я печатаю переменную count прямо перед циклом @net, она печатает 0, затем ‘1’ четыре раза, но возвращает 0. Почему это так? Я полагаю, это потому, что он возвращает #paths_from из первого вызова … если это так, как я могу вернуть переменную count #paths_from из последнего вызова?

Я предполагаю, что граф направлен и не содержит циклов.

Предположим, что граф описывается следующим хэшем.

 graph = { :A=>[:C, :D], :B=> [:D], :C=>[:D, :E, :F], :D=>[:G], :E=>[:F, :H],
          :F=>[:D, :G, :I, :H], :G=>[:H, :I], :H=>[], :I=>[] } 
 

Узлы являются ключами, а дуги задаются ключами и каждым элементом значения ключей. Есть, например, дуги :A->:C , :A-->:D , :B->:D и так далее.

Мы можем отобразить этот график следующим образом.

Учитывая два узла, обозначенных как origin и terminus , задача состоит в том, чтобы определить количество путей от origin до terminus .

Предположим

 origin   = :A
terminus = :H
 

Видно, что существует девять путей от A до H:

 A-C-E-H
A-C-E-F-H
A-C-E-F-G-H
A-C-E-F-D-G-H
A-C-F-H
A-C-F-D-G-H
A-C-F-G-H
A-C-D-G-H
A-D-G-H
 

Я приведу два решения. Первый — это рекурсия, которая требует мало кода, но перечисляет все пути. Однако число таких путей может экспоненциально расти с увеличением количества узлов. Второй более сложный, но намного быстрее для больших графиков. Его вычислительная сложность, по-видимому, составляет всего O (n ²), где n — количество узлов.

Перечислять пути от origin до destination

 def tot_paths(graph, terminus, node)
  graph[node].reduce(0) do |tot, n|
    tot   ((n == terminus) ? 1 : tot_paths(graph, terminus, n))
  end
end
 

 tot_paths(graph, :H, :A)
  #=> 9
 

Более сложное, но гораздо более эффективное решение

Второй подход требует двух шагов. Первый — выполнить топологическую сортировку узлов графа.

Любой массив sorted , представляющий собой массив топологически отсортированных узлов, обладает тем свойством, что для любой пары узлов ni = sorted[i] и nj = sorted[j] нет пути от nj к ni if j > i . Ориентированный граф без циклов гарантированно будет иметь хотя бы один топологический вид узлов.

Я использовал алгоритм Куна (описанный по ссылке выше) для получения топологической сортировки, заданной следующим массивом:

 [:B, :A, :C, :E, :F, :D, :G, :I, :H]
 

Как показано ниже, если эти узлы рассматриваются как находящиеся на линии, все дуги направлены слева направо. (На данный момент не обращайте внимания на числа, указанные над узлами.)

Моя реализация алгоритма Куна заключается в следующем.

 nodes = graph.keys
  #=> [:A, :B, :C, :D, :E, :F, :G, :H, :I] 
incoming = graph.each_with_object(nodes.map { |n| [n, []] }.to_h) do |(k,v),h|
  v.each { |n| h[n] << k }
end
  #=> {:A=>[], :B=>[], :C=>[:A], :D=>[:A, :B, :C, :F], :E=>[:C], :F=>[:C, :E],
  #    :G=>[:D, :F], :H=>[:E, :F, :G], :I=>[:F, :G]}
 

incoming[:H] #=> [:E, :F, :G] , например, показывает, что дуги, направленные в узел :H , являются :E->:H , :F->:H и :G->:H .

 no_incoming_nodes = incoming.select { |k,v| v.empty? }.keys
  #=> [:A, :B]  
sorted_nodes = []
until no_incoming_nodes.empty?
  n = no_incoming_nodes.pop
  sorted_nodes << n
  graph[n].each do |next_node|
    incoming[next_node].delete(n)
    no_incoming_nodes << next_node if incoming[next_node].empty?
  end
end
sorted_nodes
  #=> [:B, :A, :C, :E, :F, :D, :G, :I, :H]
 

Второй шаг заключается в реализации алгоритма динамического программирования для подсчета количества путей от узла :A к узлу :H . Я объясню, как это работает, объяснив значение чисел над каждым узлом на диаграмме непосредственно выше.

Количество путей от узла I (за элементом sorted_nodes которого следует конечный пункт) равно 0 (число выше I), потому I что не является конечным пунктом и не имеет исходящих узлов.

Возвращаясь на один узел sorted_nodes , количество путей от G до 1 конечной точки равно тому, что за ним следуют terminus ( 1 ) и узел I, у которого есть 0 пути к конечной точке.

Количество путей от узла D до конечной 1 точки связано с тем, что за D следует только один узел, G, и G имеет 1 путь к конечной точке.

Узел F имеет 3 пути к конечной точке, 1 которая ведет непосредственно к конечной точке, 1 которая проходит через D, 0 проходит через I и 1 проходит через G.

Аналогично, существуют 4 пути от узла E до конечной точки, 8 путей от узла C до конечной точки и, наша цель, 9 пути от A, начала координат, до конечной точки. Вычисление может быть реализовано следующим образом (с использованием sorted_nodes вычисленного ранее).

 origin   = :A
terminus = :H

tot_to = graph.each_with_object({}) do |(k,v),h|  
  (h[k] = k == terminus ? 1 : 0) if v.empty?
end
  #=> {:H=>1, :I=>0}

(sorted_nodes.index(terminus) - 1).downto(sorted_nodes.index(origin)).each do |i|
  n = sorted_nodes[i]
  tot_to[n] = graph[n].sum { |m| tot_to[m] }
end
tot_to[origin]
  #=> 9
 

Наконец, я хотел бы упомянуть, что алгоритм динамического программирования мог быть организован по-другому, с примерно равной вычислительной эффективностью. Вместо того, чтобы начинать с конечной точки и работать в обратном направлении, мы могли бы начать с начала координат и продвигаться вперед, пока не будет достигнута конечная точка, на каждом узле вычисляя количество путей от A до данного узла.

Похоже, вы не записываете результат рекурсии.

можете ли вы попробовать что-то вроде:

 count  = paths_from(vertex, vertex_b, count, visited) unless visited[@vertices.index(vertex)]
 

вообще не проходит подсчет:

 class Graph
attr_accessor :net, :vertices, :visited

  def initialize(vertices = [])
    @net = Array.new(vertices.length) { [] }
    @visited = Array.new(vertices.length, false)
    @vertices = vertices
  end

  def add_edge(vertex_a, vertex_b)
    return if @net[vertex_a].nil? || @vertices[vertex_b].nil?

    @net[vertex_a] << @vertices[vertex_b]
  end

  def paths_from(vertex_a, vertex_b)
    return 0 if @vertices.none?(vertex_b) || @vertices.none?(vertex_a)
    count = 0

    count  = 1 if vertex_a == vertex_b
    @visited[@vertices.index(vertex_a)] = true
    @net[@vertices.index(vertex_a)].each do |vertex|
      count  = paths_from(vertex, vertex_b) unless @visited[@vertices.index(vertex)]
    end

    count
  end
end