algorithm - 什么类型的算法用于多路径但一个起点的寻路？

Question

我有一张包含一个起点和多个终点的图表。我正在尝试找到一种方法来表达问题以找到要解决的正确算法类型。目标是使用尽可能少的路径到达所有点，但路径必须始终遵循网格点(即直角)。

例如:

Origin:  (0, 0)
Point A: (3, 3)
Point B: (3, 0)
Point C: (1, 3)

从原点 -> C -> A 的路径很棒，因为到达点 A 只需要 2 个额外的线段，因为它能够共享从原点 -> C 的路径。

我想通的一些事情:

• 穷尽所有点的所有路径选项，然后穷尽所有组合。这显然是蛮力和最慢的方法。不能很好地扩展。
• 创建从起点到点 _ 的全 1 矩阵，然后执行矩阵加法以找到最高流量 点。然后重新执行某种类型的详尽搜索，优先选择那些遵循高流量路段的路径。

我想做的是绘制从原点到达每个点的“顶部”路径，然后将每条路径与其他路径进行比较，以查看它们可以共享路径的位置。这感觉递归很棘手。

因此，我的问题不是寻找特定问题的答案，而是更多地试图找出解决问题的方法，即在尝试解决问题时应该走哪条路(双关语意)。

总体而言，希望根据(尚无特定顺序)对路径进行评分:

• 共享的分割数与独特的分割数
• 转弯次数(首选直线)
• 最短距离

Answer 1

这看起来不像最小生成树，而是Steiner树，https://en.wikipedia.org/wiki/Steiner_tree_problem特别是直线斯坦纳树。

https://en.wikipedia.org/wiki/Rectilinear_Steiner_tree

不幸的是，这是 NP-hard。