Ç遞歸函數來找到最小

我正在寫的程序：Ç遞歸函數來找到最小

例如輸入是5（它可以是不僅5）號碼和我在陣列讀取的數據：1, 2, 3, 4, 5。我可以從這個數組中選擇一些元素（不是第一個或最後一個），例如3，然後我將這個數字刪除，然後到sum（最初爲0），將第一個到最右邊的元素（在這種情況下意味着2*4）相乘。結果數組是1, 2, 4, 5，然後我再做一遍，直到元素數等於2（正好是1 and 5，因爲我們不能刪除這些數字）。

例如：（其中，A，B，C，d是對數字1和2，2和3以及等）

A B C D 
1 2 3 4 5

有順序刪除元素的6個可能的組合（並加上左右乘積）：

A (B (C D)) 
A ((B C) D) 
(A B) (C D) 
(A (B C)) D 
((A B) C) D 
A (B (C D))

目標是找到最小的總和！有兩種解決方法，一種是巧妙的算法，或者對每個組合使用遞歸，然後選擇最小的一種。任何人都可以給我一個提示如何寫這種遞歸，從哪裏開始寫作（或者一些聰明的算法）。 TNX

來源

2012-11-27 NGix

我不明白爲什麼有五種組合。您可以刪除除最終元素以外的所有元素，並且可以按任意順序完成刪除操作。對於包含5個元素的列表，這會使（5-2）！ = 6個組合。（他們是：（2,3,4），（2,4,3），（3,2,4），（3,4,2），（4,2,3），（4,3,2））。在你的例子中，你永遠不會配對1和2，因爲它們之間沒有任何東西可以刪除！ –

可否請你把你的例子中的操作'A（B（CD））' – MOHAMED

按遞增順序對列表進行排序，並繼續刪除位於第2位的元素 - 從左邊開始 - 2,3,4，按照你的順序。總和不會比這低。 – ashley

的遞歸回溯的解決方案是相當簡單的（僞）：

def solve (list): 
    if list.length == 2: 
     return 0 
    ans = INFINITY 
    for each interior element: 
     remove element from list 
     ans = min(ans, leftelement * rightelement + solve(list)) 
     place element back in original position in list 
    return ans

然而，這種算法不夠快上不平凡的數據集工作，因爲它的運行時間是階乘(O(n!))。優化遞歸解決方案的常用方法是dynamic programming。讓我們拿出子狀態：

dp[a][b]: minimum cost to reduce array[a .. b] to two elements on the edge 
      (array[a] and array[b])

基礎案件是dp[i][i + 1], i = {0 .. size - 1)（兩個相鄰的元素）。由於沒有內部元素進行刪除，該子被設置爲0

對於所有其他情況dp[a][b]其中b - a >= 2，我們可以通過刪除[a + 1, b - 1]之間索引的任何內部元素劃分array[a .. b]。如果我們在元素i上劃分子陣列，則成本爲dp[a][i] + dp[i][b] + array[a] * array[b]。我們希望最小化每個子狀態的成本，因此我們將爲所有可能的分化元素取最小值。最終答案僅僅是dp[0][size - 1]。

由於有O(n^2)子狀態，每個子狀態要考慮的分隔元素的平均值，總運行時間爲立方體(O(n^3))，它應該在合理的時間內運行於中小型數據集。

來源

2012-11-27 18:13:52 jma127

該算法的運行時間低於O（n！）。我想你誤解了這個問題。 – gbtimmon

是的，由於遞歸性質，第一個算法是O（n！）。但是，第二種算法將其減少到立方時間。底部的運行時分析適用於改進的動態編程解決方案。 – jma127

你是對的，我編輯我的評論：P – gbtimmon

Ç遞歸函數來找到最小

回答

相關問題