Как найти кратчайший путь в графе, добавив наименьшее количество новых узлов?

Question

Мне нужно найти кратчайший путь на графике с наименьшим количеством добавленных узлов. Начальный и конечный узлы не важны. Если в графе нет пути только между указанными n-узлами, я могу добавить несколько узлов для завершения кратчайшего дерева, но я хочу добавить как можно меньше новых узлов.

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

Answer 1

Начните с начального узла.

если это целевой узел, все готово.

Проверьте каждый подключенный узел, если это целевой узел. Если это правда, вы сделали

Проверьте, подключен ли какой-либо из подключенных узлов к целевому узлу. Если это правда, вы сделали.

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

Answer 2

Вы хотите минимизировать количество узлов в пути (вместо суммы веса, как в общих алгоритмах).

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

А если пути нет, просто добавьте это ребро на график.

Sands.

PS: если вы зададите значение 1 для каждого ребра, число узлов в пути будет равно весу 1 (исключая узлы источника и назначения)

Answer 3

Рекомендую использовать генетический алгоритм. Больше информации здесь и здесь . Быстро объясняя это, GA - это алгоритм для нахождения точных или приближенных решений задач оптимизации и поиска.

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

Через несколько поколений вы найдете наиболее подходящее (читай самое короткое) решение проблемы.