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

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

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

说明：
1 ） 图中所有权重均为内的整数；
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

呼叫 小甲鱼老师~ {:9_241:}

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

呼叫 各位鱼友 {:9_241:}

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

这个不是求最短路径吗？A星算法很好的哦{:10_256:}

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

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

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

呃，这不就是华为竞赛的题目嘛，题主做得咋样了
页: [1]
查看完整版本: 有个算法题，想和大家交流一下。。。