График поиска с ограничением веса

Question

У меня есть ненаправленный взвешенный граф с объектами произвольного типа в качестве узлов.Вес ребра между двумя узлами A и B представляет собой сходство этих двух узлов в интервале (0, 1]. Сходство 0 приводит к отсутствию связи между узлами, поэтому граф может быть разбит на части.

Учитывая заданный вес w и начальный узел S, который является алгоритмом для нахождения всех узлов, которые имеют вес> w. Подузлы (если смотреть из S) должны иметь произведение всех весов на пути. Т.е.:

S --(0.9)-- N1 --(0.9)-- N2 --(0.6) -- N3

Начиная с S, узлы будут иметь следующие значения подобия:

N1: 0.9 
N2: 0.9 * 0.9 = 0.81
N3: 0.9 * 0.9 * 0.6 = 0.486

Таким образом, при заданном S и целевом весе 0,5 поиск должен возвращать N1 и N3. Если поиск начинается с N2вернул бы S, N1 и N3.

Есть ли у них какие-либо алгоритмы, которые соответствуют моим потребностям?

Answer 1

обратите внимание на следующее:

1. log(p1 * p2) = log(p1) + log(p2)
2. если p1 < p2, то log(p1) < log(p2) и, таким образом: -log(p1) > -log(p2)

Заявление [на основе 1,2, упомянутого выше]: нахождение наиболее похожего маршрута от s до t, фактически находит минимальный путь от s до t, где веса -log оригинала.

Я предлагаю следующий алгоритм, основанный на алгоритме Дейкстры и приведенном выше утверждении.

1. define for each edge e: w'(e) = -log(w(e)) //well defined because w(e) > 0
2. run Dijkstra's algorithm on the graph with the modified weights.
3. return all vertices v that their weight is dijkstra(v) < -log(needed)

Answer 2

Вы можете попробовать использовать алгоритм Беллмана-Форда, поскольку он отлично работает как с суммированием и умножением ребер, так и с минимумами и максимумами (вы вычисляете самые длинные пути - используйте максимум - выполняя инвертированную операцию).

Кроме того, если вы берете логарифм всех ваших путей, проблема уменьшается от умножения к суммированию.После этого вы можете поменять знаки весов (чтобы превратить задачу от нахождения минимума до нахождения максимума) и использовать алгоритм Беллмана-Форда на этом графике.Поскольку все ваши веса изначально находятся в диапазоне от 0 до 1, после обоих этих преобразований вы, вероятно, сможете использовать и Дейкстру.

Затем, после расчета путей, просто верните преобразования назад и проверьте, какие «расстояния»тебе подходит.