n****y
发帖数: 106 | 1 最近碰到一个问题，关于dijkstra的，呵呵
dijkstra是用来解决最短路径的，graph上面只有一种weight,比如distance,找到一个
从source到destination的最短路径
现在有个问题就是，假设graph上每条edge都有两种weight,say distance and time,
现在要
用一种算法也是minimize 的distance, 但是subject to total time < T
也就是说，原来的dijkstra找出的路径可能不行了，因为总时间可能>T
我看了点文献，这个问题是NP-Hard, 有一些用heuristic来减少complexity的
谁能推荐个比较经典的算法，不需要性能最好，保证对的就可以了。刚看了一个“专利
”，研究到最后发现根本就是错的，sigh.
多谢。 | w*****e
发帖数: 197 | 2 最简单的办法 就是用integer programming
但是需要比较好的solver
其实这个问题的标准解法也是用OR的思路
单纯的图论算法没有特别有效的
如果非要手工写一个不在乎性能的
如果可以假定distance都是整数
那么可以有一些比较简单的hack
否则可能只能用heuristic实际些 | j*******2
发帖数: 18 | 3 深度或者广度遍历
获得各个有效路径
取distance最小并且符合time要求的路径 | w*****e
发帖数: 197 | 4 恐怕不行吧
【在 j*******2 的大作中提到】
: 深度或者广度遍历
: 获得各个有效路径
: 取distance最小并且符合time要求的路径
|
|
