Найти лучшие пути в нескольких деревах (несколько узлов в нескольких слоях)

Question

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

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

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

данные видятся следующим образом; (узел первого уровня, узел 2 уровня, узел 3 уровня...): оценка

(1, 1, 1): 3

(1, 2, 1): 1

(1, 2, 2): 6

(1, 2, 3): 2

(2, 2, 1): 3

(2, 2, 2): 4

(2, 2, 3): 3

(2, 3, 2): 5

(2, 3, 3): 4

.....

результат должен дать 5 путей, и эти пути должны дать общую минимальную стоимость.

Какой алгоритм следует использовать для этой проблемы?

Answer 1

Эта проблема может быть смоделирована как проблема сети с минимальными затратами. Позволять m быть количеством узлов в каждом слое. Искусственный источник s располагается над первым слоем; s подключен к каждому узлу первого слоя, и каждый из них m края имеет пропускную способность сети ограничена 1 и стоимость 0, Кроме того, есть искусственный терминал t ниже последнего слоя; t подключен к каждому узлу последнего слоя, и каждый из них m края имеет пропускную способность сети ограничена 1 и стоимость 0, Проблема может быть решена путем определения минимального потока затрат с суммой m, что возможно через сетевой симплексный алгоритм.