Найти расстояние пути между узлами сети?

Question

Я пишу веб-искатель, и мне нужно найти минимальное расстояние между двумя URL-адресами.

Я представляю сеть с хешем. Каждый узел, который не находится в конце сети, является ключом к вектору узлов, к которому он подключен:

hash = {:v0 => [:v1, :v2, :v3], 
     :v1 => [:v4, :v5, :v6], 
     :v2 => [:v7, :v8, :v9], 
     :v3 => [:v10, :v11, :v12], 
     :v4 => [:v13, :v14, :v15]} 

Это решение не работает. Проблема заключается в том, что я только увеличиваю расстояние (расстояние переменного), когда он находит цель, так что результат всегда 1:

def path src, target, hash, dist 
    return -1 if hash[src] == nil # invalid distance if source is invalid 
    return dist += 1 if hash[src].include? target 

    arr = Array.new 
    for i in hash[src] do 
     arr.push path(i, target, hash, dist) 
    end 
    arr = arr.delete_if {|x| x < 0} # delete invalid values 
    return -1 if arr.empty? 
    return arr.min # return the shortest distance 
end 

Как я могу это исправить, так что будет увеличиваться на каждом уровне сети?

Answer 1

Я установил его. Вот код, если он кому-то поможет.

def distance src, target, hash 
    return 0 if src == target 
    return nil if hash[src].nil? 
    dist = 1 

    if hash[src].include? target 
     return dist 
    else 
     arr = hash[src].map {|x| distance x, target, hash} 
    end 
    arr = arr.delete_if {|x| x.nil?} 

    return dist + arr.min if !arr.empty? 
    return nil 
end 

Answer 2

Похоже, вы еще не полностью поняли идею рекурсии. Для этого сначала запишите определение вашего «пути». Причина, по которой я цитирую, состоит в том, что я ожидаю, что вы либо хотите расстояние, либо хотите путь (где длина пути - это расстояние), но я действительно не знаю, что вам нужно.

Теперь важная причина в том, что в этом случае это, вероятно, нечто вроде «путь - это кратчайшее расстояние от текущего URL до целевого URL». Реализация - это что-то вроде «если целевой URL является прямым соседом, расстояние 1, в противном случае это кратчайшее расстояние от любого из соседей плюс 1». В вашем случае вы проходите на существующем расстоянии, что на самом деле не так, но необычно. После этого, если вы найдете URL-адрес в hash[src], вы увеличиваете это расстояние (это Ruby pass-by-reference, BTW?) и верните его. В этот момент я действительно ожидал, что вы вернетесь 1, потому что это расстояние между текущей позицией и целью. Аналогичным образом, позже вам, вероятно, потребуется также увеличить значение dist, прежде чем передавать его на рекурсивный вызов.

Теперь существует совершенно другая проблема, и это то, что ваш алгоритм неэффективен до такой степени, что он станет бесполезным с более чем несколькими URL-адресами. Предположим, что URL-адреса связаны как «A-X-T», с X началом, T целью. Если вам не повезло, вы сначала спуститесь в A, который может быть облаком тысяч URL-адресов. Каждый из них найдет путь к T после прохождения всего графика. Взгляните на разницу между поиском по ширине (BFS) и поиском глубины (DFS), который даст вам подсказку, как его исправить.

еще две вещи:

• Рассмотрим путь между А и А. Я бы сказал, что их расстояние равно нулю, что ваша функция должна обрабатывать. Расстояние тогда становится: Если S = ​​T, расстояние равно нулю, в противном случае это одно плюс кратчайшее расстояние до любого соседа.
• Я бы постарался избежать использования -1 для «не найден». Я предпочитаю ничего не возвращать (ноль?), Потому что тогда менее вероятно, что вы случайно делаете какую-либо арифметику.