Взвешенные ориентированные ациклические графы: алгоритм для нахождения весов ребер таким образом, чтобы они определяли функцию расстояния?

Question

У меня есть эта техническая проблема, которая может быть сформулирована с помощью Направленного ациклического графа (DAG).Узлы представляют события (с неизвестным временем), с направленными ребрами, кодирующими корабль отношений: «Я моложе, чем вы / я был до вас».

Мне нужно оценить веса ребер (т.е. «динамические веса»)такой, что Взвешенный DAG (WDAG) подразумевает функцию расстояния на DAG.Другими словами, сумма весов для путей между узлами A и B должна быть одинаковой для всех путей.

Это неопределенная проблема, даже если веса являются целыми числами (та же основная причина, по которой топологическая сортировка не уникальна,Я полагаю).Вообще говоря, веса ребер, которые представляют интервалы времени между узлами / событиями, являются действительными числами.Поэтому я ввожу некоторую заданную целевую функцию C = J (WDAG) для взвешенной DAG, здесь не указано.

Мой вопрос: существует ли алгоритм, который распределяет положительно определенные веса в WDAG при условии ограничения1) что веса образуют функцию расстояния DAG и 2) минимизируют стоимость целевой функции C.

Это, похоже, не связано с проблемами кратчайшего пути или минимального связующего дерева, классически связанными с WDAG.Любые идеи для формального или эвристического решения вышеуказанной проблемы?

С уважением,

Стефан

Answer 1

Я думаю, все, что вам нужно, это топологическая сортировка .

1. Сортировка узлов по топологической сортировке.
2. Распределите их в интервале [0,1] в порядке, который вы получили.
3. Теперь расстояние между парами узлов в линии [0,1] даст вам вес соединяющего их ребра.

Это одно из возможных решений.Если у вас есть больше ограничений на веса, чем то, что вы описываете в вопросе, проблема может быть более сложной.