Ruby - поиск всех путей через граф из заданной начальной точки - PullRequest
Новая
       23

Ruby - поиск всех путей через граф из заданной начальной точки

4 голосов
/ 30 октября 2019

Карта хеш-памяти заполняется следующим образом: 

{"1"=>["2"], "2"=>["3", "7"], "3"=>["4"], "5"=>["6", "2"], "6"=>["7"], "7"=>["8", "4"]}

, поэтому каждый ключ может иметь несколько значений. Эти значения представляют автобусные остановки из набора маршрутов, например, от автобусной остановки 1 вы можете добраться до 2, от автобусной остановки 2 вы можете добраться до 3 или 7 и так далее.

Я пытаюсь обойти эту структуру графа и найти все возможные пути длиной более 1 от заданной начальной точки. Например, для начальной точки 1 список всех возможных путей будет выглядеть следующим образом: 

[[1,2] , [1,2,3] , [1,2,3,4] , [1,2,7] , [1,2,7,8], [1,2,7,4]]

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

if hash.has_key?(origin.to_s)
  tmp = origin.to_s
  tmp << hash[origin.to_s][0]
  paths.push(tmp)
  expand_node(hash,paths,paths.length-1,tmp[tmp.length-1])
end

Источник - отправная точка. Для начала я добавляю первый путь (в данном случае [1,2]) в массив с именем paths, затем расширяю последнее значение, добавленное к предыдущему пути (в данном случае 2). 

def expand_node(hash,paths,curr_paths_index,node)
curr_node = node
if hash.has_key?(node.to_s)
  counter = 0
  hash[curr_node].each do |child|
    tmp = paths[curr_paths_index]
    tmp << child
    paths << tmp
    curr_paths_index += counter + 1
    puts paths
    expand_node(hash,paths,curr_paths_index,child)
  end
end

end

Аргумент curr_paths_index отслеживает путь, с которого я расширяюсь. Аргумент path - это полный список путей, найденных в данный момент. Аргумент node является текущим раскрываемым значением.

Печать paths после завершения функции дает:

123 123 1234 1234 1234 12347 12347 12347 12347 123478 123478 123478 123478 123478 1234784 1234784 1234784 1234784 1234784 1234784

Есть ли способ изменить этокод, чтобы он выдает желаемый результат (показано выше)? Есть ли лучший способ решения этой проблемы в целом?

Спасибо.

Ответы [ 3 ]

2 голосов
/ 30 октября 2019

Один из способов решения рекурсивной проблемы - сначала разбить ее на один простой для решения случай, а затем обобщить этот один случай. Вот более простой случай:

Учитывая график и путь к нему, определите, какие узлы можно добавить в конец этого пути без создания цикла.

Если мы сможем решить эту проблему, мы легко сможем решить и более крупную проблему.

  1. Начните с пути, который является просто вашим начальным узлом
  2. Найдите все узлы, которые можно добавить к этомупуть без создания цикла
  3. Для каждого такого узла выведите путь, который является вашим начальным путем плюс этот узел, и ...
  4. Рекурсивно повторите с шага 2, используя новый путь

Обратите внимание, что если на шаге 2 не будет найдено ни одного нового узла, рекурсивный вызов будет прерван, поскольку шаги 3 и 4 не имеют ничего общего.

Вот как я решу шаг 2, я 'оставлю рекурсивную часть вам 

def find_next_nodes graph, path
  graph[path[-1]].reject { |node| path.include? node }
end
1 голос
/ 30 октября 2019 
def doit(graph, start)
  return [] unless graph.key?(start)
  recurse(graph, start).drop(1)
end

def recurse(graph, start)
  (graph[start] || []).each_with_object([[start]]) { |next_node, arr|
    recurse(graph, next_node).each { |a| arr << [start, *a] } }
end


graph = { 1=>[2], 2=>[3, 7], 3=>[4], 5=>[6, 2], 6=>[7], 7=>[8, 4] }


doit(graph, 1)
  #=> [[1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 7], [1, 2, 7, 8],
  #    [1, 2, 7, 4]] 
doit(graph, 2)
  #=> [[2, 3], [2, 3, 4], [2, 7], [2, 7, 8], [2, 7, 4]] 
doit(graph, 3)
  #=> [[3, 4]] 
doit(graph, 5)
  #=> [[5, 6], [5, 6, 7], [5, 6, 7, 8], [5, 6, 7, 4], [5, 2],
  #    [5, 2, 3], [5, 2, 3, 4], [5, 2, 7], [5, 2, 7, 8], [5, 2, 7, 4]] 
doit(graph, 6)
  #=> [[6, 7], [6, 7, 8], [6, 7, 4]] 
doit(graph, 7)
  #=> [[7, 8], [7, 4]]     
doit(graph, 4)
  #=> [] 
doit(graph, 99)
  #=> []
1 голос
/ 30 октября 2019

Я бы сделал это следующим образом, уверен, что это можно оптимизировать и, возможно, также возникнет проблема с производительностью. 

require 'set'

dt = {"1"=>["2"], "2"=>["3", "7"], "3"=>["4"], "5"=>["6", "2"], "6"=>["7"], "7"=>["8", "4"]}

def traverse(initial_hash, key_arrays, traversed_keys = [])
  value = []
  key_arrays.map do |key|
    n = [*traversed_keys, key]
    value << n unless n.count == 1 # prevent first key to be added
    another_keys = initial_hash.fetch(key, nil) # try to load the value, fallback to nil if key not found
    if another_keys.nil? # stop condition
      value << n
    elsif another_keys.is_a?(Enumerable) # if key found
      another_keys.map do |ank| # recursive
        value.concat([*traverse(initial_hash, [ank], n)]) # splat operator to unpack the array
      end
    end
  end
  value.to_set # only return unique value, can be converted to array if needed
end

traverse(dt, [1].map(&:to_s)).map { |val| val.join('') }

Извините, но я не отлаживал ваш код, поэтому я думаю, что естьпроблема с временной переменной, поскольку путь, который больше не может быть расширен, переносится на следующую итерацию.

...