gpt4 book ai didi

algorithm - 使用动态规划找到最适合一组数据点的多边形链

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:00:38 24 4
gpt4 key购买 nike

题目表述如下:

给定一个包含 n 个点的序列 p_1= (x_1,y_1),...,p_n=(x_n,y_n) 并按它的 x 坐标从左到右排序(即 x_1 < x_2 < ... < x_n ) 和一个介于 1 和 n 之间的数字 k。我们想要找到一条从 p1 到 pn 的多边形链,有 k 条边从左到右,最小化点到链的垂直距离之和。设计一个动态规划算法在 O(n^3) 时间内解决问题。计算点p_a+1, .的垂直距离之和的方法。 . . ,p_b-1到线通过p_ap_b。由 f(a,b) 给出。

enter image description here

由于我很难写一个例子来测试,所以我不知道我的答案是否正确。

答案如下:

首先,我定义 C[i,j] = pi 处有 j 条边的多边形链末端,垂直距离的最小总和。答案应该是 C[n,k]。

对于基本情况,当 j>=i 时,我定义 C[i,0] = 0 和 C[i,j] = +infinity。

对于递归公式,我定义 C[i,j] = minimum (1 < p < i) { C[p , j-1] + f(p,i) }

我的回答有问题吗?谢谢。

最佳答案

对于链,最好使用不在 P 中的点(p_i 的集合)的示例。

P = {(0, 0), (1, 1), (3, 1), (4, 0)}
k = 2

+ (2,2)

* (1,1) * (3,1)

* (0,0) * (4,0)

对于 P 中的点的链有 2 种可能性,两者都有 f(1,4) = 2/3。以 (2, 2) 作为链点给出 f(1,4) = 0

没有限制链点在P中的问题的解决方案,可能很难用DP方式描述。它看起来更像是有很多约束的回归问题。

我想在这个问题中,预计链点来自 P

更新

低递归与原始递归相同,如提到的 j_random_hacker。

我认为最好定义稍微不同的函数。将 C(a, b, e) 定义为点 p_ap_b 之间具有 e 边的链的最小成本.我们问题的答案是 C(1, n, k)

C(a, b, 1) = f(a,b)
C(a, a+i, i) = 0
C(a, b, k) = inf, k > b-a

可以使用不同的递归。这是最后一条边的“长度”:

C(a, b, k+1) = min( C(a, c, k) + C(i, b, 1) ), for i in a+k, b-1

关于algorithm - 使用动态规划找到最适合一组数据点的多边形链,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23200181/

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