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要求的路径
|
|