c******n
发帖数: 4965 | 1 for google maps, if I try to get directions using public transportation (bus
), they can utilize the starting and ending time of bus schedules, and find
the fastest paths.
but if I want to minimize bus ticket cost (fare), and mandate that the total
trip must be finished within a given time deadline, is there an algorithm
to do this?
thanks |
S**I
发帖数: 15689 | 2 linear programming can do this, but the complexity could be very high.
bus
find
total
【在 c******n 的大作中提到】
: for google maps, if I try to get directions using public transportation (bus
: ), they can utilize the starting and ending time of bus schedules, and find
: the fastest paths.
: but if I want to minimize bus ticket cost (fare), and mandate that the total
: trip must be finished within a given time deadline, is there an algorithm
: to do this?
: thanks
|
s***e
发帖数: 1490 | 3 constrained shortest path
bus
find
total
【在 c******n 的大作中提到】
: for google maps, if I try to get directions using public transportation (bus
: ), they can utilize the starting and ending time of bus schedules, and find
: the fastest paths.
: but if I want to minimize bus ticket cost (fare), and mandate that the total
: trip must be finished within a given time deadline, is there an algorithm
: to do this?
: thanks
|
c******n
发帖数: 4965 | 4 it's a bit unclear how you could cast this into LP:
let's say we remove the constraints, just look at plain Djikstra: how would
you cast Djikstra algo into LP?
【在 S**I 的大作中提到】
: linear programming can do this, but the complexity could be very high.
:
: bus
: find
: total
|
D*******a
发帖数: 3688 | 5 shortest path problem is equivalent to min-cost flow which can be formulated
as LP.
would
【在 c******n 的大作中提到】
: it's a bit unclear how you could cast this into LP:
: let's say we remove the constraints, just look at plain Djikstra: how would
: you cast Djikstra algo into LP?
|
c******n
发帖数: 4965 | 6 I did a few searches, looks min-cost flow reduces to "successive shortest
paths"
but there is nothing that shows the reduction the other way,
if that's the case, they are not equivalent???
formulated
【在 D*******a 的大作中提到】
: shortest path problem is equivalent to min-cost flow which can be formulated
: as LP.
:
: would
|
c*********e
发帖数: 16335 | 7 这个不就是那著名的Dijkstra’s least-cost algorithm吗？
bus
find
total
【在 c******n 的大作中提到】
: for google maps, if I try to get directions using public transportation (bus
: ), they can utilize the starting and ending time of bus schedules, and find
: the fastest paths.
: but if I want to minimize bus ticket cost (fare), and mandate that the total
: trip must be finished within a given time deadline, is there an algorithm
: to do this?
: thanks
|
S**I
发帖数: 15689 | 8 He has an extra constraint
【在 c*********e 的大作中提到】
: 这个不就是那著名的Dijkstra’s least-cost algorithm吗？
:
: bus
: find
: total
|
