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

Question

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

例如：

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

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

我想通的一些事情：

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

我想做的是绘制 "top" 从原点到达每个点的方法，然后将每条路径与其他路径进行比较，看看它们在何处可以共享路径。这感觉递归棘手。

所以，我的问题不是寻找具体问题的答案，而是更多地试图找出解决问题的方法，即在尝试解决时应该走哪条路（双关语）。

总体而言，希望根据（尚无特定顺序）对路径进行评分：

• 共享段数与唯一段数
• 圈数（首选直线）
• 最短距离

Answer 1

因为你实际上可以从 2D-space 上的任何点到达所有点，那么你可以将其表示为具有 N 个节点和 N * (N - 1) / 2 个边的 complete graph - 从每个点到所有其他点。

每条边的权重可以表示两个节点之间的距离，等于两点之间的距离x加上距离y，因为你只用直角:

W[a, b] = = |a.x - b.x| + |a.y - b.y|

现在，您有了一个普通图，由一组节点和边表示，您可以应用任何所需的算法。

目前还不清楚你到底想达到什么分数，但构建最小生成树听起来像是解决最佳路径问题的答案。
比如可以用Kruskal's algorithm来实现。

Answer 2

这似乎与最小生成树不相似，但与 Steiner 树相似，https://en.wikipedia.org/wiki/Steiner_tree_problem 特别是直线 Steiner 树。

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

不幸的是，这是 NP-hard。