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

Question

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

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

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

Любые мысли по этому поводу?

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

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

Answer 1

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

Отъезд: http://en.wikipedia.org/wiki/A * _search_algorithm

Некоторые псевдо-код там, чтобы помочь вам тоже :)

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

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

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