Redian新闻
>
[转载] 请教网络(图论)问题
avatar
[转载] 请教网络(图论)问题# Computation - 科学计算
b*t
1
【 以下文字转载自 Singapore 讨论区 】
【 原文由 babyscut 所发表 】
一个undirected graph, 两个属于这个图的disjoint的point set, V, V'
两个point set的点数是一样的, 能找出这样一种联结两个点集的方法,(一对一的连接)
使得所有的路径的长度和最小. 这个问题计算复杂度是多少?
是NP-Hard的吗? O(N!)吗? 帮帮忙, 谢谢
avatar
d*e
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!)吗? 帮帮忙, 谢谢

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

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

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。