лучший путь для проектирования канализации

Question

Есть ли какой-либо алгоритм, который может найти все пути между источником и приемником в заданном, ненаправленном, взвешенном графике/сети? Сеть состоит из нескольких исходных узлов и одного узла-приемника. Путь должен быть свободен от петель

Answer 1

Я бы применил это с алгоритмом A * со следующими отличиями от базового поиска пути.

• Старт из раковины, а не от источника, поскольку существует только одна раковина
• Каждый узел представляет собой набор позиций вместо одной позиции. На каждой итерации добавьте соседей всех позиций в очередь. Также создайте ветви для всех соседей, чтобы в следующем наборе была еще одна позиция. Ограничьте максимальное количество позиций на количество источников в качестве оптимизации.
• Отслеживай, какие источники вы достигли в каждом пути
• пройденной функция стоимости должна быть общее пройденное расстояние со всеми разветвленными путями в сочетание
• функция оценки должен объединить все остальные источники

Это должно дать оптимальные пути, если алгоритм A * используется правильно.

Answer 2

Если вы ищете все контуры без петли, то breadth-frist search должен выполнить эту работу. В итерации для каждого текущего пути не продолжайте его, когда он достигает точки, уже находящейся на пути или в раковине.

Answer 3

Он похож на Minimum Spanning Tree.