加权有向无环图：查找边权重以定义距离函数的算法？
我有一个可以用有向无环图（DAG）来表达的技术问题。 节点代表事件（时间未知），有向边编码关系：“我比你年轻/我发生在你之前”。
我需要估计边权重（即“动态权重”），以便加权 DAG (WDAG) 暗示 DAG 上的距离函数。换句话说，节点 A 和 B 之间的路径权重之和对于所有路径应该相等。
这是一个未确定的问题，即使权重是整数（我想这与拓扑排序不唯一的根本原因相同）。一般来说，表示节点/事件之间的时间间隔的边权重是实数。因此，我在加权 DAG 上引入一些预设的目标函数 C=J(WDAG)，这里未指定。
我的问题是：是否有一种算法可以在 WDAG 上分配正定权重，并受到以下约束：1）权重形成 DAG 的距离函数，2）最小化目标函数成本 C。
这似乎与最短-通常与 WDAG 相关的路径或最小生成树问题。对于上述问题的正式或启发式解决方案有什么想法吗？
问候，
斯蒂芬
I have this technical problem that can be formuated with a Directed Acyclic Graph (DAG).
Nodes represent events (with unknown timing), with directed edges encoding the relation ship: "I'm younger than you/I happened before you".
I need to estimate edge weights (i.e. "dynamic weights") such that the Weighted DAG (WDAG) implies a distance function on the DAG. In other words the sum of weights for paths between nodes A and B should be equal for all paths.
This is an undetermined problem, even if the weights are integers (same underlying reason that topological sorting is not unique, I suppose). In all generality, the edge weights, which represent timeintervals between nodes/events, are real numbers. Therefore I'm introducing some preset objective function C=J(WDAG) on the weighted DAG, here unspecified.
My question is: is there an algorithm that distributes positive definite weights on the WDAG, subject to the constraint 1) that the weights form a distance function of the DAG and 2) minimizing the objective function cost C.
This seems unrelated to the shortest-path or minimum-spanning-tree problems classically associated to WDAG's. Any ideas to a formal or heuristic solution to the above problem?
Regards,
Stephane
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为您所需要的只是拓扑排序。
这是一种可能的解决方案。如果您对权重的限制比问题中描述的更多，则问题可能会更困难。
I think all you need is topological sorting.
This is one possible solution. If you have more constraints on the weights than what you describe in the question, the problem might be more difficult.