Алгоритм кратчайшего пути с минимальным количеством пройденных узлов

Question

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

То, что я имею в виду, это типичный алгоритм Дейкстры, учитывающий вес ребер, соединяющих узлы, при расчете кратчайшего маршрута от узла A к узлу B. Я хочу вставить в него другой параметр. Я хочу, чтобы алгоритм также определил вес пройденного узла.

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

Есть мысли по этому поводу?

Приветствия
RD

Редактировать:
Мои извенения. Я должен был объяснить лучше. Итак, допустим, самый короткий маршрут от
(A, B) представляет собой A -> C -> D -> E -> F -> B, охватывающий в общей сложности 10 единиц
Но я хочу, чтобы алгоритм придумал маршрут A -> M -> N -> B, охватывающий всего 12 единиц.
Итак, что я хочу, так это уметь рассчитывать количество узлов, а не только расстояние между связанными узлами.

Answer 1

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

Вот исходный график (треугольник):

A-------B
 \  5  /
2 \   / 2
   \ /
    C

Кратчайший путь от A до B через C. Теперь добавьте константу 2 ко всем ребрам.Вместо этого кратчайший путь становится единственным шагом от A непосредственно к B (из-за «штрафа», который мы ввели за использование дополнительных ребер).

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

Answer 2

Способ, которым вы можете сделать это - адаптировать веса ребер, чтобы они всегда были равны 1, так что вы пересекаете 5 узлов, и вы прошли расстояние «5».Алгоритм был бы таким же в этой точке, оптимизируя количество пройденных узлов, а не пройденное расстояние.

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

weight = node_importance * 1 + (1 - node_importance) * distance

Где node_importance - это процент, который измеряет, насколько расстояние является фактором и насколько важен минимальный обход узла.Хотя вам, возможно, придется нормализовать расстояния, чтобы они составляли в среднем 1.

Answer 3

Если я правильно понял вопрос, то его лучшая аналогия была бы той, что использовалась для поиска лучшего сетевого пути.

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

Таким образом, лучший расчет пути содержит минимизацию функции переменных, как в вашем случае Distance и Hop Count (узлов).

Вы должны получить функциональное уравнение, которое могло бы связать расстояние и количество узлов с качеством.

так что-то как предположим
1 hop count change = 5 unit distance (что означает, что воздействие одинаково для 5-ю единицей или изменения 1 узла)

, чтобы минимизировать потери, вы можете использовать его в линейном уравнении.
minimize(distance + hopcount);
где hopcount может быть выражен как расстояние.

Answer 4

Я собираюсь выйти на конечности здесь, но вы пробовали алгоритм A *? Возможно, я неправильно понял ваш вопрос, но кажется, что A * будет хорошей отправной точкой для того, что вы хотите сделать.

Выезд: http://en.wikipedia.org/wiki/A*_search_algorithm

Какой-то псевдокод вам тоже поможет:)