拓扑排序

Question

给定一个具有 N 个节点的 DAG，每个节点都有一个值（例如，0.2、0.5、1.3、0.1...）。我想将顶点排序成一个链。难点在于排序节点时有一个objective函数

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

objective函数是最小化所有links权重的总和（此处为链：x+xy+xyz）。

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

Answer 1

这是 kevmo314 提到的算法，在 Python 中实现。可能应该用 C 重新实现，用位操作代替集合操作。

我们可以重写 objective

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

所以假设所有的权重都是正的，整体objective在子问题objectives中是单调的，这允许动态规划。

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}))

拓扑排序

topology sorting

sorting

algorithm

graph-algorithm