使用動態編程來找到最適合一組數據點

的問題表述爲以下多邊形鏈：使用動態編程來找到最適合一組數據點

考慮到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

因爲它是我很難寫一個例子來測試，所以我不知道我的回答是否是corrent與否。

答案是如下所示：

首先，我定義C [I，J] =多邊形鏈端在其中j的邊緣，垂直距離的最小和PI。答案應該是C [n，k]。對於基本情況，當j> = i時，我定義C [i，0] = 0，並且C [i，j] = +無窮遠。

對於遞歸公式，我定義C [I，J] =最小（1個< p <ⅰ）{C [P，J-1] + F（P，I）}

是否有任何我的回答錯了嗎？謝謝。

來源

2014-04-21 user

你忘了定義函數* f * –

另外我在這裏沒有看到真正的問題。你只是想驗證你的再發是正確的嗎？ –

由於無法上傳圖片，我很抱歉沒有函數定義。是的，對於以下問題，我的重複發生是否正確：我們希望找到一個從p1到pn的多邊形鏈，其中k個邊從左到右，最小化點到鏈的垂直距離之和。 – user

例如，在鏈中使用不在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_a和p_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

來源

2014-06-16 16:23:37 Ante

+1對於你的反例:)我不認爲你的遞歸有幫助，雖然 - 我認爲它計算原始遞歸相同的東西，但速度較慢，因爲它使用了更多的參數。 –

@j_random_hacker你說得對，這和原來的遞歸完全一樣。只有兩種類型的C（）出現：C（1，i，k）（在原始C [i，k]）和C（i，b，1）（f（i，b））中。 C（a，b，e）的定義提供了不同類型的遞歸：從開始（如原來的），從結束（相反），...最後沒有太多的幫助： - / – Ante

使用動態編程來找到最適合一組數據點

回答

相關問題