[转载] 请教网络(图论)问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Computation - 科学计算

[转载] 请教网络(图论)问题

[转载] 请教网络(图论)问题# Computation - 科学计算

b*t2003-10-01 07:10

1 楼

【以下文字转载自 Singapore 讨论区】
【原文由 babyscut 所发表】
一个undirected graph, 两个属于这个图的disjoint的point set, V, V'
两个point set的点数是一样的, 能找出这样一种联结两个点集的方法,(一对一的连接)
使得所有的路径的长度和最小. 这个问题计算复杂度是多少?
是NP-Hard的吗? O(N!)吗? 帮帮忙, 谢谢

d*e2003-10-01 07:10

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*t2003-10-01 07:10

3 楼

谢谢, 呵呵, 我不是研究算法的, 老板一定要俺告诉他计算复杂度, 俺实在是痛苦之际

【在 d******e 的大作中提到】

: 你在说matching嘛?
: 描述的好费劲哦.
: 用hungarian method应该是O(V^3).
: 当年俺们作tsp的作业写过这个算法.