gpt4 book ai didi

algorithm - 拓扑排序

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:48:31 25 4
gpt4 key购买 nike

给定一个有 N 个节点的 DAG,每个节点都有一个值(例如 0.2、0.5、1.3、0.1...)。我想将顶点排序成一个链。难点在于节点排序时有一个目标函数。

例如,链是x---> y --->z ---> w。每个链接都有一个权重,对于 (x,y) 权重 = x,链接 (y,z) 权重 = xy,链接 (z,w) 权重 = xyz 等等。

目标函数是最小化所有链接权重的总和(此处为链:x+xy+xyz)。

我一直在想。但我现在不知道。有没有人可以就算法设计或问题的复杂性证明提供一些想法?谢谢。

最佳答案

这是 kevmo314 提到的算法,用 Python 实现。可能应该用 C 语言重新实现,用按位操作代替集合操作。

我们可以重写目标

x + x*y + x*y*z = x*(1 + y*(1 + z)),

所以假设所有的权重都是正的,总体目标在子问题目标中是单调的,这允许动态规划。

def optimal_order(predecessors_map, weight_map):
vertices = frozenset(predecessors_map.keys())
memo_map = {frozenset(): (0, [])}
return optimal_order_helper(predecessors_map, weight_map, vertices, memo_map)


def optimal_order_helper(predecessors_map, weight_map, vertices, memo_map):
if vertices in memo_map:
return memo_map[vertices]
possibilities = []
for v in vertices:
if any(u in vertices for u in predecessors_map[v]):
continue
sub_obj, sub_order = optimal_order_helper(predecessors_map, weight_map, vertices - frozenset({v}), memo_map)
possibilities.append((weight_map[v] * (1.0 + sub_obj), [v] + sub_order))
best = min(possibilities)
memo_map[vertices] = best
return best


print(optimal_order({'u': [], 'v': ['u'], 'w': [], 'x': ['w']}, {'u': 1.2, 'v': 0.5, 'w': 1.1, 'x': 1.001}))

关于algorithm - 拓扑排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37394331/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com