Re: proper name of a "k-stops bus route" optimization problem?
- From: Robert Israel <israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Fri, 06 Jul 2007 17:23:33 -0500
cerios <spamfree@xxxxxxxxxxx> writes:
Hello,
I have an optimization problem that I think is equivalent to
the problem of choosing stops for a bus:
There are N possible stops, ordered,
and the bus is required to make exactly K (<N) stops.
The cost of travelling from any stop to another is known.
.... and you want to minimize the total cost?
Does this problem have a standard name?
The Floyd/Dijkstra problems come to mind, but I think
they are actually different in that the current
in problem exactly K stops are required.
Floyd's and Dijkstra's are algorithms, not problems AFAIK.
The problems are called shortest-path problems.
In this case you can make it into a shortest-path problem
with N K vertices: vertex (j,k) for 1<=j<=N, 1<=k<=K corresponds
to making your k'th stop at stop number j. Directed edges go
from (i,k) to (j,k+1) with the cost of going from stop i to stop j.
Dynamic programming provides an easy solution. If c(i,j) is the
cost of going from i to j and X(i,j,k) is the minimum cost of
going from i to j in exactly k steps, then X(i,j,1) = c(i,j) and
X(i,j,k+1) = min_{j'} (X(i,j',k) + c(j',j)).
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada V6T 1Z2
.
- Prev by Date: Re: A question for Tommy1729
- Next by Date: Re: all prime factors of f(n) are mutually congruent mod m
- Previous by thread: Series Summing to Different Values
- Next by thread: A GCD question
- Index(es):
Relevant Pages
|
