请教一个算法 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一个算法

请教一个算法# JobHunting - 待字闺中

e*r2013-06-29 07:06

1 楼

一个Graph,求最短路径，一个路径如果经过几个特定点会有一个extra weight，比如说
，单独经过A点，单独经过B点都是用正常的weight，但是如果这个路径同时经过A,B，
那就给这个路径设定一个extra weight，这样一个Graph，请问有什么好的算法吗.

J*32013-06-29 07:06

2 楼

求最后权重最值？

p*32013-06-29 07:06

3 楼

Single point shortest path??看看这个行不行
原始最短路径算法有一个是：
res[N]放结果
for i = 0; i < N-1; i++
for each edge "e"
relaxation(e, res)
一般的relaxation只考虑
res[e.beg] + cost(e) < res[e.end]的情况
这里修改relaxation
res[e.beg] + cost(e) + extra_cost_introduced_by_passing_e.end < res[e.end]

t*t2013-06-29 07:06

4 楼

这把蒂结私忒拉的最短路径改动一下就行了吧？

r*e2013-06-29 07:06

5 楼

按原题的意思
extra cost不是针对某一个点或者某一条边，而是一条路径上的某几个点
相当于 set_extra_cost -through A -through B ... extra_cost
单纯检查某一个点是不能知道加或者不加extra cost的
必须要track整个路径

【在 p*****3 的大作中提到】

: Single point shortest path??看看这个行不行
: 原始最短路径算法有一个是：
: res[N]放结果
: for i = 0; i < N-1; i++
: for each edge "e"
: relaxation(e, res)
: 一般的relaxation只考虑
: res[e.beg] + cost(e) < res[e.end]的情况
: 这里修改relaxation
: res[e.beg] + cost(e) + extra_cost_introduced_by_passing_e.end < res[e.end]

p*32013-06-29 07:06

6 楼

是啊，不能用DP,好像没有什么更好的办法了

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

: 按原题的意思
: extra cost不是针对某一个点或者某一条边，而是一条路径上的某几个点
: 相当于 set_extra_cost -through A -through B ... extra_cost
: 单纯检查某一个点是不能知道加或者不加extra cost的
: 必须要track整个路径

J*32013-06-29 07:06

7 楼

觉得就是dijkstra 把新节点加入集合时候对权值进行判断的时候加上条件？

p*32013-06-29 07:06

8 楼

dijikastra这里不成立啊，最优子结构被破坏了
1 1 1 extra_cost(b,d) == 100000000
a ---> b --->c--->d
| ^
| |100
-------------e
100
dijkstra 不work啊

【在 J****3 的大作中提到】

: 觉得就是dijkstra 把新节点加入集合时候对权值进行判断的时候加上条件？

v*k2013-06-29 07:06

9 楼

每走一步都需要backtrack重新算到当前为止的总weight和最优路径吧，除非这个
weight有什么规律可以压缩判断时间

p*32013-06-29 07:06

10 楼

是不是NP complex？

【在 v*****k 的大作中提到】

: 每走一步都需要backtrack重新算到当前为止的总weight和最优路径吧，除非这个
: weight有什么规律可以压缩判断时间

v*k2013-06-29 07:06

11 楼

不清楚。这个算法有典型的语音识别或者手写识别的应用，假如状态量不是太多的话。

【在 p*****3 的大作中提到】

:
: 是不是NP complex？

e*r2013-06-29 07:06

12 楼

谢谢各位回帖，现在的问题可以被看作一个寻路问题，从城市A到城市B，找最短路径，
但是如果途中同时经过城市C和城市D，那对路径会有一个Bonus，这样一个问题在实际
中应该会有不少，各位再费心帮俺想一下，俺去查一个有没有类似的文献.

e*r2013-06-29 07:06

13 楼

应该是的.

【在 p*****3 的大作中提到】

:
: 是不是NP complex？

I*c2013-06-29 07:06

14 楼

如果我没有记错的话，这种点对点求最短路径问题就时间效率而言等同于single-
source最短路径。后者可以用Dijkstra或者bellmen-ford来求解。不过我感觉直接修改
这两个算法来解题不容易。
我觉得可以不考虑extra weight的情况下先求最短路径。如果得到的最短路径没有
extra weight，那么这就是答案。不然的话，可以把原图里能够引起extra weight的点
去掉，来求最短路径(要分不同情况分别求。如点A，点B同时出现的话会造成extra
weight，那么就把点A去掉求一次，把点B去掉再求一次）.并和最开始求的带有extra
weight的最短路径比较来决定最后的最短路径。
如果造成extra weight的条件很复杂，可能需要别的算法。