有个算法题，想和大家交流一下。。。

zxc · 发表于 2016-3-14 12:24:10

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

问题定义
给定一个带权重的有向图 G=(V,E)， V 为顶点集， E 为有向边集，每一条有向边均有一个权
重。对于给定的顶点 s、 t，以及 V 的子集 V'，寻找从 s 到 t 的不成环有向路径 P，使得 P
经过 V'中所有的顶点(对经过 V'中节点的顺序不做要求)。
若不存在这样的有向路径 P，则输出无解，程序运行时间越短，则视为结果越优；若存在这
样的有向路径 P，则输出所得到的路径，路径的权重越小，则视为结果越优，在输出路径权
重一样的前提下，程序运行时间越短，则视为结果越优。

说明：
1 ）图中所有权重均为[1 ， 20]内的整数；
2）任一有向边的起点不等于终点；
3）连接顶点 A 至顶点 B 的有向边可能超过一条，其权重可能一样，也可能不一样；
4）该有向图的顶点不会超过 600 个，每个顶点出度(以该点为起点的有向边的数量)不超过
8；
5） V'中元素个数不超过 50；
6）从 s 到 t 的不成环有向路径 P 是指， P 为由一系列有向边组成的从 s 至 t 的有向连通路
径，且不允许重复经过任一节点；
7）路径的权重是指所有组成该路径的所有有向边的权重之和。

不知道各位鱼油有什么想法吗？也想请问一下小甲鱼老师。。。请老师百忙之中帮忙看看

zxc · 发表于 2016-3-14 12:24:45

呼叫小甲鱼老师~

zxc · 发表于 2016-3-14 12:25:50

呼叫各位鱼友

ligen超越 · 发表于 2016-3-16 14:04:52

这个不是求最短路径吗？A星算法很好的哦

ligen超越 · 发表于 2016-3-16 14:15:15

弄错了，这个从起点一圈一圈的遍历，选择最优的路径，直到遍历到了终点，一般就是最优路径之一吧

zxc · 发表于 2016-3-16 22:07:04

ligen超越发表于 2016-3-16 14:15
弄错了，这个从起点一圈一圈的遍历，选择最优的路径，直到遍历到了终点，一般就是最优路径之一吧

这个图规模太大，这样时间上可能太久了

ligen超越 · 发表于 2016-3-17 14:48:12

zxc 发表于 2016-3-16 22:07
这个图规模太大，这样时间上可能太久了

不大吧！就600个点，就和A星算法差不吧，改进下就好了！没有写过，所以不知道时间复杂度！

mianht · 发表于 2016-4-4 16:45:49

呃，这不就是华为竞赛的题目嘛，题主做得咋样了

账号		自动登录	找回密码
密码			立即注册

[技术交流] 有个算法题，想和大家交流一下。。。

马上注册，结交更多好友，享用更多功能^_^