在给定的 DAG 中,假设每个节点都有一个成本参数,并且每条边都有一个距离。 我们需要编写最小化函数是 MAX(所有选定节点的总成本,max(每个选定节点与其后代选定节点之间的距离之和)。
解决方案可以是任何语言。
写了这段代码。不确定这是否是最优化的解决方案
def minimize_max_cost(dag):
# find the lower and upper bounds of the binary search
lower_bound = float('inf')
upper_bound = 0
for node in dag:
lower_bound = min(lower_bound, node.cost)
upper_bound += node.cost
# binary search for the minimum value of the function
answer = float('inf')
while lower_bound <= upper_bound:
mid = (lower_bound + upper_bound) // 2
total_cost = 0
max_distance = 0
for node in dag:
if node.cost <= mid:
total_cost += node.cost
for child in node.children:
if child.cost <= mid:
max_distance = max(max_distance, node.distance_to(child))
if max_distance <= mid:
answer = min(answer, total_cost)
upper_bound = mid - 1
else:
lower_bound = mid + 1
return answer