通過將變量傳遞給具有收益率的遞歸函數來尋找最小值

Question

讓我們說space = [0, 100]。

我給出了空間的碎片，並可能重疊。

例如，

[0, 30], [0, 20], [10, 40], [30, 50], [50, 90], [70, 100] 

是一組片段。

一組跨越從上述組選擇的整個空間片段的一個例子是：

[0, 30], [10, 40], [30, 50], [50, 90], [70, 100] 

這組片段跨越整個空間，因爲它具有在[0，100]

所有元素

又如

[0, 30], [30, 50], [50, 90], [70, 100] 

其是沒有[10, 40]在前面的例子中的集。

對於每組碎片，可以計算成本。

集合的成本是添加片段的邊際成本的總和。

def get_marginal_cost(fragment): 
    return RTT + (fragment[1] - fragment[0])/bandwidth 

其中RTT和bandwidth是常數：

用於添加到該組的片段的邊際成本函數由下式給出。

我正在嘗試從具有最低成本的片段集合中找到子集。

由於這不能用貪心算法解決，所以我想考慮所有可能的片段集合。

我用Depth First Search算法來考慮所有可能的情況下，通過考慮每個片段作爲node，並且限定爲存在edge片段u和v如果u[0] < v[0] <= u[1] <= v[1]之間。

葉節點，與100

我能得到代表（可能）集片段組成一個整體space，通過下面的函數的所有可能的情況下，發電機對象結束片段。

def dfs(a, start, path=None): 
    if path is None: 
     path = [start, ] 
    if start[1] == space: 
     yield path 
    for frgmt in a - set(path): 
     l = frgmt[0] 
     r = frgmt[1] 
     if start[0] < l <= start[1] <= r: 
      yield dfs(a, frgmt, path + [frgmt, ]) 

但是，我不知道我怎麼能使用get_marginal_cost功能上面我提到我dfs功能裏面，我怎麼可以傳遞和更新minimum變量dfs函數，這樣我能找到的最小成本程序終止。

它應該不斷增加最小值的邊際成本，並檢查並更新if start[1] == space:（空間爲100）中的最小值。

測試用例和代碼是http://ideone.com/oN4jWa

Answer 1

恐怕我不明白你的現有代碼不夠好，看看究竟你要去哪裏錯了（目前還不清楚是什麼a，或start是例如在dfs中）。但是，我認爲我掌握了你正在努力解決的問題。以下是我想解決它自己，使用您所描述的基本算法：

from operator import itemgetter 

def dfs(space, fragments, path=None, cost=0): 
    if path == None: 
     path = [] 
     path_end = space[0] 
    else: 
     path_end = path[-1][1] 

    for i, fragment in enumerate(fragments): 
     if fragment[0] > path_end: # this fragment would leave a gap (as 
      break     # will all the rest) so we can stop 
     elif path_end < fragment[1]: # useless fragments are skipped 
      new_path = path + [fragment] 
      new_cost = cost + get_marginal_cost(fragment) 
      if fragment[1] == space[1]: # this fragment reaches the end, 
       yield new_path, new_cost # so this is a base case 
      else:  # recursive case 
       for result in dfs(space, fragments[i+1:], # slice frag list 
            new_path, new_cost): 
        yield result # in Python 3.3 and later, you can skip the 
           # loop and just use "yield from dfs(...)" 

def find_minimum_cost_path(space, fragments): 
    fragments.sort(key=itemgetter(0)) # sort by start of the fragments 
    path, cost = min(dfs(space, fragments), key=itemgetter(1)) 
    return path 

我解決了通過拆分發現所有有效路徑之間的工作（使用遞歸深度優先遍歷尋找最低成本路徑的問題），並選擇最低成本路徑（撥打min）。您可能可以將dfs更改爲僅返回找到的路徑的最低成本，但這會更復雜一些。爲了簡單起見，我將這些部件分開。

它們對我的dfs函數的關鍵在於它只對分段的片段序列有效。目前尚不清楚您使用的是何種數據結構，因此我在find_minimum_cost_path函數中調用了sorted。如果你的片段已經被排序（通過它們的開始元素）並且它們的數據結構可以被分割，你可以擺脫那個步驟。