让我们说 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 。如果您的片段已经排序(通过它们的开始元素)并且它们的数据结构可以被切片,您可以去掉这一步。
