Пример алгоритма «линеаризации» графа

Question

Упрощая бизнес-пример, я имею следующую ситуацию:

Некоторые объекты должны быть распределены на графике наиболее "линейным" способом, возможным для данного "термометра".

Скажите,Вояджер посещает некоторые города.Несколько городов посещаются несколько раз.

Итак, у нас есть список городов по оси ординат (которые могут быть дублированы), и время по абсциссе один.

Теперь для заданного пути, скажем, (A => X => A => B => C) мы должны отобразить строку «наиболее линейным способом».

Напримерна изображении выше линия зеленая является оптимальной
(1> 2> 3> 4> 5)

, но может быть несколько возможных выходов

(1> 2> 1> 4> 5)
(1> 2> 3> 4> 5)
(1> 2> 6> 4> 5)

(3> 2> 1> 4> 5)
(3> 2> 3> 4> 5)
(3> 2> 6> 4> 5)

(6> 2> 1> 4> 5)
(6> 2> 3> 4> 5)
(6> 2> 6> 4> 5)

Какие алгоритмы помогают в таких ситуациях?

Answer 1

Построить график, на котором узел представляет собой пару город + значение и время (например, A (3) / 1).Ребро существует между двумя узлами, которые находятся рядом на пути (например, от A (3) / 1 до X (2) / 2).

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

Пример графа (ребра даны в градусах и являются просто оценками):

                                            Total cost
      0        0      105       15
A31  ->  X22  ->  A13  ->  B44  ->  C55     120

              90       0        0
              ->  A33  ->  B44  ->  C55     90

              115      110      105
              ->  A63  ->  B44  ->  C55     330