e********r
发帖数: 2352 | 1 一个Graph,求最短路径，一个路径如果经过几个特定点会有一个extra weight，比如说
，单独经过A点，单独经过B点都是用正常的weight，但是如果这个路径同时经过A,B，
那就给这个路径设定一个extra weight，这样一个Graph，请问有什么好的算法吗. |
J****3
发帖数: 427 | |
p*****3
发帖数: 488 | 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***t
发帖数: 6066 | |
r*******e
发帖数: 7583 | 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*****3
发帖数: 488 | 6
是啊，不能用DP,好像没有什么更好的办法了
【在 r*******e 的大作中提到】
: 按原题的意思
: extra cost不是针对某一个点或者某一条边，而是一条路径上的某几个点
: 相当于 set_extra_cost -through A -through B ... extra_cost
: 单纯检查某一个点是不能知道加或者不加extra cost的
: 必须要track整个路径
|
J****3
发帖数: 427 | 7 觉得就是dijkstra 把新节点加入集合时候对权值进行判断的时候加上条件？ |
p*****3
发帖数: 488 | 8
dijikastra这里不成立啊，最优子结构被破坏了
1 1 1 extra_cost(b,d) == 100000000
a ---> b --->c--->d
| ^
| |100
-------------e
100
dijkstra 不work啊
【在 J****3 的大作中提到】
: 觉得就是dijkstra 把新节点加入集合时候对权值进行判断的时候加上条件？
|
v*****k
发帖数: 7798 | 9 每走一步都需要backtrack重新算到当前为止的总weight和最优路径吧，除非这个
weight有什么规律可以压缩判断时间 |
p*****3
发帖数: 488 | 10
是不是NP complex？
【在 v*****k 的大作中提到】
: 每走一步都需要backtrack重新算到当前为止的总weight和最优路径吧，除非这个
: weight有什么规律可以压缩判断时间
|
v*****k
发帖数: 7798 | 11 不清楚。这个算法有典型的语音识别或者手写识别的应用，假如状态量不是太多的话。
【在 p*****3 的大作中提到】
:
: 是不是NP complex？
|
e********r
发帖数: 2352 | 12 谢谢各位回帖，现在的问题可以被看作一个寻路问题，从城市A到城市B，找最短路径，
但是如果途中同时经过城市C和城市D，那对路径会有一个Bonus，这样一个问题在实际
中应该会有不少，各位再费心帮俺想一下，俺去查一个有没有类似的文献. |
e********r
发帖数: 2352 | 13 应该是的.
【在 p*****3 的大作中提到】
:
: 是不是NP complex？
|
I******c
发帖数: 163 | 14 如果我没有记错的话，这种点对点求最短路径问题就时间效率而言等同于single-
source最短路径。后者可以用Dijkstra或者bellmen-ford来求解。不过我感觉直接修改
这两个算法来解题不容易。
我觉得可以不考虑extra weight的情况下先求最短路径。如果得到的最短路径没有
extra weight，那么这就是答案。不然的话，可以把原图里能够引起extra weight的点
去掉，来求最短路径(要分不同情况分别求。如点A，点B同时出现的话会造成extra
weight，那么就把点A去掉求一次，把点B去掉再求一次）.并和最开始求的带有extra
weight的最短路径比较来决定最后的最短路径。
如果造成extra weight的条件很复杂，可能需要别的算法。 |
