algorithm - 两条折线之间面积最小的网格

Question

我在 3D 中有两条折线 v 和 u 分别带有 n 和 m 顶点。我想将 v[0] 连接到 u[0]，将 v[n-1] 连接到 u[m-1 ] 以及内部顶点以某种方式获得具有最小表面积的三角形网格带。

我天真的解决方案是通过随后添加最小对角线来获得接近最优的初始网格，然后在每个四边形中切换对角线(如果它产生的面积较小)，直到这不再可能为止。

但恐怕我可以以局部最小而不是全局结束。实现最小网格的更好选择是什么？

Answer 1

这可以通过动态程序来解决。

让我们将问题想象成一个表格，其中列代表第一条折线的顶点，行代表第二条折线的顶点:

    0  1  2  3  ... n-1   -> v
 0 
 1
 2
...
m-1

每个单元格代表折线之间的一条边。你从 (0, 0) 开始，想通过 (+1, 0) 找到一条通往 (n-1, m-1) 的路径 或 (0, +1) 步骤。您执行的每一步都有成本(所得三角形的面积)，您希望找到成本最低的路径。

因此，您可以迭代地(仅采用动态规划的方式)计算到达任何像元所需的成本(通过比较两个可能的传入方向的最终成本)。记住你选择的方向，你最终会得到一条成本最低的完整路径。总运行时间为 O(n * m)。

如果您知道您的顶点或多或少分布得很好，您可以将表格的计算限制在对角线附近的几个条目。这可以将运行时间降低到 O(k * max(n, m))，其中 k 是对角线周围的可变半径。但是，如果良好顶点分布的假设不成立，您可能会错过最佳解决方案。

您还可以采用类似 A* 的策略，仅当您认为它可能属于最小路径时才计算单元格(在一些启发式的帮助下)。