用于有效绘制一组线的算法

Question

我发现以下算法在线提问,但找不到任何有效的解决方案.
谷歌访谈时询问了这个问题.问题是这样的:

给定要绘制的一系列线条(每条线具有起点和终点),
给出一种算法,帮助您在最短的时间内绘制线条.
没有必要仅从起点绘制线.

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

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

任何人都可以提供关于如何解决这类问题的提示吗？

Answer 1

假设Steve314在评论中对笔式绘图仪的解释是正确的(如OP所述),那么问题就在于旅行商问题的某种推广,这已知是NP完全问题.

证明:如果所有线都具有长度0,即减少到点,则问题在于:笔必须触摸每个点,并且必须最小化笔行进的总距离.这正是欧几里德旅行商问题.

因此,您应该寻找一种近似算法(您无法有效地找到最佳解决方案).欧几里德TSP的一些近似算法基于miminum生成树,可以进行修改以解决您的问题.也可以证明生成的算法会给出一条不超过最佳路径长度X(= 2？)倍的路径.

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

1. 将要绘制的线条解释为无向(可能是断开连接)图形的边,其顶点是指定的端点
2. 完成包含所需边的最小连通(跨越)图(使用Prim算法)
3. 转换为有向图并找到欧拉电路

这应该给你一个解决方案(按照适当的路径绘制边缘),最多只有最佳路径的两倍.它可以通过多种方式进一步优化,例如,通过获取快捷方式并在不需要绘制下一个边缘时(再次或根本)跳过路径中的顶点.

Answer 2

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