gpt4 book ai didi

最小化凸多边形三角剖分对角线总和的算法?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:20:41 45 4
gpt4 key购买 nike

将三角剖分的成本定义为已添加的对角线长度之和。给定一个凸多边形,其最便宜的三角剖分的成本是多少?如果我们将多边形视为一组 n 个坐标:v_1=x_1,y_1,...,v_n=x_n,y_n 并且解必须有 n-3 条对角线(不重叠,因为它是三角剖分)

我一直在尝试重现这个动态规划问题,但我似乎找不到一个好的问题。我真的不承认找到复发的次优结构。任何人都可以帮我解决这个问题吗?

最佳答案

最简单的方法 是遍历每个点,获取前一个点和下一个点之间的距离,并在没有当前点的情况下递归多边形;例如对于五边形 abcde 那将是:

  • 距离 eb + 四边形递归 bcde
  • 距离 ac + 四边形递归 cdea
  • 距离 bd + 四边形递归 deab
  • 距离 ce + 四边形递归 eabc
  • 距离 da + 四边形递归 abcd

recursive triangulation of pentagon

为了不多次计算相同的解决方案,您应该丢弃已经检查过的点没有到达对角线的任何解决方案;例如当在步骤 3 中使用四边形 deab 进行递归时,具有对角线 eb 的解是重复的,因为使用三角形 abe 的解已经被 checkin 第一步。使用此方法完全不进行重复计算可能会很复杂。

另一种方法是选择一个点(在下图中以红色表示),然后将每个解枚举为数字的总和为n - 2,其中 n 是点数。每条对角线都通过所选点的解决方案将是解决方案 11111。然后,您遍历所有总和为 n - 2 的组合:11111、1112、1121、113、1211、122、131, 14、2111、212、221、23、311、32、41 和 5。大于 1 的数字表示您组合了 2 个或更多线段,并从其第一个点到最后一个点添加对角线。当数字大于 2 时,此对角线将与一个剩余的多边形接壤(以粉红色表示),您将使用它进行递归。

动画显示算法对 7 点多边形进行的迭代和递归,直到它对 6 点多边形进行递归。

recursive triangulation of septagon

这两种方法都提供了内存和制表的可能性,但并不简单。一旦开始递归,从 b 点开始的五边形不一定是 bcdef;它很可能是 bdfhj。因此检索存储的中间结果可能会有点复杂。

关于最小化凸多边形三角剖分对角线总和的算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33988478/

45 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com