топология сортировка

Question

При наличии DAG с N узлами каждый узел имеет значение (например, 0,2, 0,5, 1,3, 0,1 ...). Я хочу сортировать вершины в цепочку. Трудность состоит в том, что при сортировке узлов существует объективная функция.

Например, цепочка x ---> y ---> z ---> w. Каждая ссылка имеет вес, для (x, y) weight = x, link (y, z) weight = xy, link (z, w) weight = xyz и т. Д.

Целевая функция состоит в том, чтобы свести к минимуму сумму (здесь для цепочки: x + xy + xyz) всего веса ссылок.

Я думал об этом. Но я понятия не имею. Кто-нибудь может дать некоторые идеи по дизайну алгоритма или сложному доказательству проблемы? Благодарю.

Answer 1

Это алгоритм, на который ссылается 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}))