6

我在网上找到了以下算法问题，但找不到任何有效的解决方案。
这是在谷歌面试中被问到的。问题是这样的：

给定一系列要绘制的线（每条线都有起点和终点），
请给出一个算法来帮助您在最短的时间内绘制线。
不必仅从起点绘制一条线。

有一种方法将每条线视为图中的一个节点。
两个节点之间的边是第一行的结束节点
和第二行的起始节点之间的距离。在此之后，如果我们计算最小生成树，
它将给出最佳答案。

但我不确定这是否始终提供最佳解决方案，因为它假设这
条线仅在一个方向上绘制。

谁能提供有关如何解决此类问题的提示？

4

5 回答 5

5

假设 Steve314 在评论中对笔式绘图仪的解释是正确的（如 OP 所述），那么问题是旅行商问题的某种概括，已知它是 NP 完全的。

证明：如果所有线的长度都为0，即缩减为点，那么问题是：每个点都必须被笔触碰，笔的总距离必须最小化。这正是欧几里得旅行商问题。

所以你应该寻找一个近似算法（你不能有效地找到最优解）。欧几里得 TSP 的一些近似算法基于最小生成树，可以修改以解决您的问题。也有可能证明生成的算法将为您提供一条不超过 X（= 二？）乘以最佳路径长度的路径。

编辑：这是一个完整的例子，改编自维基百科中的“最简单”度量 TSP 近似解算法

  1. 将您要绘制的线解释为无向（可能不连贯）图的边，其顶点是指定的端点
  2. 完成包含所需边的最小连接（生成）图（使用 Prim 算法）
  3. 转换为有向图并找到欧拉回路

这应该为您提供一个解决方案（根据需要遵循绘制边缘的路径），该解决方案最多是最佳路径的两倍。可以通过多种方式对其进行进一步优化，例如，只要不需要（再次或根本）绘制下一条边，就可以采取捷径并跳过路径中的顶点。

于 2013-08-30T16:24:06.973 回答
1

这是一个非常讨厌的问题。这是一条最短哈密顿路径，但是您有很多边（所有边 (u, v)，其中 u 是某条线的端点，v 是另一条线的起点），并且距离不对称。我认为 TAOCP 4A 中描述的基于 ZDD 的优雅方式并不适用——它会淹没在所有这些边缘。

这是一个从 TSP 借来的想法（不是最优的，但无论如何这似乎是一个相当不错的想法）：

For every line s
    Schedule = empty sequence
    For every line n
        insert n in the optimal position in Schedule
    Apply 2-opt (see TSP) to the Schedule
Take the best Schedule.

小心那个 2-opt。它经常被描述为对称距离的情况，它可以让您优化“距离变化”计算。你不能在这里做。

这是另一个想法，大量借鉴了 TSP：

解决大量 ILP 问题。对于每个节点s和t（不等于）：

  • 每个边的布尔变量。
  • 权重是这些边的长度。
  • 每个节点n不是s或给出“与== 2t相邻的所有边的总和”形式的约束n
  • 对于节点s和t，该和等于 1
  • 懒惰地添加整个事物必须是单个连接组件的约束，即：
    • 检测连接的组件。如果有1，这是一个解决方案。
    • 如果有超过 1 个，对于每个连接的组件：
    • 如果它包含sor t，则添加与该连通分量相邻的所有边的总和必须为 1 的约束。
    • 否则，该总和必须为 2。

充分利用所有这些解决方案。这可能需要一段时间。

于 2013-08-30T18:10:32.257 回答
1

对于最小生成树，您将不得不使用 Djikstra 算法，该算法将选择一条最短路径并将其与连接到同一节点的所有其他路径递归地进行比较，直到所有节点都被处理。实际上，我只是重读了您的问题，并且由于您的路径不必从某个点开始，您可以使用 Prim's，它具有与上述相同的想法，但从任何节点开始。两者都使用允许广度优先搜索的优先级队列。

于 2013-08-30T01:57:03.340 回答
0

不确定我是否完全理解你的问题。一种方法是从您的绘图区域开始，例如 640X480 图像。然后对于图像中的每个位置，您检查像素 (x,y) 是否位于至少一条线上（您只需要使用线方程和一些合适的 epsilon 值满足一条线），如果是，则输出a 1 else a 0. 绘制所有线。

于 2013-08-30T14:17:39.087 回答
0

使用不相交集数据结构。只要您对集合进行并集，它就会求解最小生成树。https://en.m.wikipedia.org/wiki/Disjoint-set_data_structure

于 2019-03-31T10:05:36.280 回答