b******t
发帖数: 9 | 1 【 以下文字转载自 Singapore 讨论区 】
【 原文由 babyscut 所发表 】
一个undirected graph, 两个属于这个图的disjoint的point set, V, V'
两个point set的点数是一样的, 能找出这样一种联结两个点集的方法,(一对一的连接)
使得所有的路径的长度和最小. 这个问题计算复杂度是多少?
是NP-Hard的吗? O(N!)吗? 帮帮忙, 谢谢 | d******e
发帖数: 2265 | 2 你在说matching嘛?
描述的好费劲哦.
用hungarian method应该是O(V^3).
当年俺们作tsp的作业写过这个算法.
【在 b******t 的大作中提到】
: 【 以下文字转载自 Singapore 讨论区 】
: 【 原文由 babyscut 所发表 】
: 一个undirected graph, 两个属于这个图的disjoint的point set, V, V'
: 两个point set的点数是一样的, 能找出这样一种联结两个点集的方法,(一对一的连接)
: 使得所有的路径的长度和最小. 这个问题计算复杂度是多少?
: 是NP-Hard的吗? O(N!)吗? 帮帮忙, 谢谢
| b******t
发帖数: 9 | 3 谢谢, 呵呵, 我不是研究算法的, 老板一定要俺告诉他计算复杂度, 俺实在是痛苦之际
【在 d******e 的大作中提到】
: 你在说matching嘛?
: 描述的好费劲哦.
: 用hungarian method应该是O(V^3).
: 当年俺们作tsp的作业写过这个算法.
|
|
