algorithm - 示例算法到 "linearize"一张图

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

构建一个图，其中节点是城市+值(value)和时间的一对(例如 A(3)/1)。路径中相邻的两个节点之间存在一条边(例如 A(3)/1 到 X(2)/2)。

边的权重将是最后一对节点和下一对节点之间的矢量差(相反的角度)(这将使边权重动态取决于它来自哪里)。然后使用 Dijkstra 找到到 (a) 目标的最小距离。

示例图(边以度数给出，只是估计值):

                                            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