Skip to main content
 首页 » 编程设计

python之通过将变量传递给具有 yield 的递归函数来查找最小值

2025年05月04日15txw1958

让我们说 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中

请您参考如下方法:

恐怕我对你现有的代码理解得不够好,无法准确地看出你哪里出了问题(不清楚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 。如果您的片段已经排序(通过它们的开始元素)并且它们的数据结构可以被切片,您可以去掉这一步。