将图形“线性化”的示例算法

Question

简化一个业务案例，我有以下情况：

对于给定的“温度计”，应以最“线性”的方式在图形中分配某些对象。

比如，旅行者访问了一些城市。多次访问了几个城市。

因此，我们有纵坐标轴上的城市列表（可能重复），横坐标为时间。

现在，对于给定的路径，例如(A => X => A => B => C)，我们应该显示一条线，在“最线性的方式”下。

但是可能会有多种可能的输出。

是否有一些算法可以帮助这种情况？

- serhio

---

为什么1>2>3>4>5不是一个好的解决方案？这对我来说甚至完全是线性的。你能控制行的顺序吗？如果可以，你只需选择与路径相同的顺序，就可以始终得到一个线性图形。 - Patrick

@Patrick：你说得对，12345是理想的解决方案。这个例子只是为了演示目的..从3开始 :) - serhio

我认为这个问题仍然有点太抽象了。我们需要一个定量的函数来确定你的上下文中的“线性”。例如，显然在你的新例子中，绿色线更加线性。但是，你如何确定橙色和蓝色路径哪个更加线性呢？ - Mark Peters

Answer 1

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

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

示例图（边以度数给出，仅为估计值）：

                                            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

- Mark Peters

---

谢谢。我没有定义角度......我只有一个在Y轴上的城市数组和一个在X轴上的城市数组。我们可以抽象出时间，将其设置为每一步的1。那么现在，我应该“估计”一个角度吗？...这有点尴尬，但如果这是唯一的方法... - serhio

@serhio：我认为你应该从定义“线性”开始。我故意抽象，因为我没有明确的指令来确定A是否比B“更线性”。我选择将其定义为“需要最少转弯的路线”。定义一个函数，其最小值表达了你认为是“最”线性的东西。优化问题需要一个要优化的值，而不是某些模糊描述的特征。 - Mark Peters