Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Вопрос-Ответ Новый топик    Ответить
 Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
iv_an_ru
Member

Откуда: Новосибирск
Сообщений: 20366
Есть старая оптимизационная задача: Из A в B есть железная дорога, на ней N станций, есть таблица цен проезда от любой станции до любой другой. Надо выбрать 0 или больше "промежуточных станций" так, чтобы сумма билетов с пересадками на этих станциях была минимальной, т.е. проехать в итоге от A до B дешевле всего.

Приспичило узнать, как эта задача называется в английской литературе, и очень желательно --- где она сначала появилась.
3 фев 18, 08:42    [21162429]     Ответить | Цитировать Сообщить модератору
 Re: Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
miksoft
Member

Откуда:
Сообщений: 38545
https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
3 фев 18, 13:08    [21162668]     Ответить | Цитировать Сообщить модератору
 Re: Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
iv_an_ru
Member

Откуда: Новосибирск
Сообщений: 20366
miksoft,

Дейкстру я бы и сам назвал, вот только эта задача --- ещё более частный случай Дейкстры: граф полон и полностью упорядочен, а путь именно от наименьшей до наибольшей вершины в этом порядке.
3 фев 18, 17:59    [21163123]     Ответить | Цитировать Сообщить модератору
 Re: Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
miksoft
Member

Откуда:
Сообщений: 38545
iv_an_ru
полностью упорядочен
упорядочен или ориентирован?

А вообще - не вижу, как добавленные уточнения мешают применить алгоритм Дейкстры. Ну или какой-то из его подходящих аналогов.
3 фев 18, 22:14    [21163464]     Ответить | Цитировать Сообщить модератору
 Re: Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
iv_an_ru
Member

Откуда: Новосибирск
Сообщений: 20366
miksoft
iv_an_ru
полностью упорядочен
упорядочен или ориентирован?
И упорядочен и ориентирован.
miksoft
А вообще - не вижу, как добавленные уточнения мешают применить алгоритм Дейкстры. Ну или какой-то из его подходящих аналогов.
Никак не мешают. Вопрос вообще в другом --- не как решать, а как эта конкретная задача называется в английской литературе.
4 фев 18, 00:38    [21163744]     Ответить | Цитировать Сообщить модератору
 Re: Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 54383
iv_an_ru
Есть старая оптимизационная задача: Из A в B есть железная дорога, на ней N станций, есть таблица цен проезда от любой станции до любой другой. Надо выбрать 0 или больше "промежуточных станций" так, чтобы сумма билетов с пересадками на этих станциях была минимальной, т.е. проехать в итоге от A до B дешевле всего.

Приспичило узнать, как эта задача называется в английской литературе, и очень желательно --- где она сначала появилась.
это фигня
вы к оптимальной стоимости добавьте оптимальное время
4 фев 18, 08:36    [21163895]     Ответить | Цитировать Сообщить модератору
 Re: Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
exp98
Member

Откуда:
Сообщений: 2699
iv_an_ru, что-нить вида "транспортная задача", "задача транспортного типа".
В пристойном тексте находим список литературы, дальше копаем.
6 фев 18, 10:27    [21169071]     Ответить | Цитировать Сообщить модератору
 Re: Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
exp98
Member

Откуда:
Сообщений: 2699
iv_an_ru,
скорее даже "задача комивояжера".
6 фев 18, 11:22    [21169239]     Ответить | Цитировать Сообщить модератору
 Re: Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
iv_an_ru
Member

Откуда: Новосибирск
Сообщений: 20366
exp98
iv_an_ru, что-нить вида "транспортная задача", "задача транспортного типа".
В пристойном тексте находим список литературы, дальше копаем.
Беда в том, что этой задачей первым занимался как бы не Беллман. Ричард Эрнст который. А Беллман мало того, что понарешал чортову прорву задач, так у него ещё и фамилия ходовая. Загуглиться можно вусмерть. И сроки жмут --- с ответом хорошо бы помочь одной красивой женщине до 9-го февраля, и это при том, что 8-го как на грех приезжает Путин, поэтому рядом с её работой будет транспортный карачун.
6 фев 18, 13:24    [21169741]     Ответить | Цитировать Сообщить модератору
 Re: Как в английской литературе называется задача о самом дешёвом проезде на поезде?  [new]
exp98
Member

Откуда:
Сообщений: 2699
iv_an_ru, сочувствую), но завтра (т.т.т.) надеюсь, что уже пересеку государственную границу.

Но во-1х тындекс делает более короткую выдачу, и он вроде до сих пор опирается на принцип "на что все ссылаются" (а не "что все ищут" и т.п.), причём слово "ссылка" отнюдь не в смысле УРЛа.
Ну и может кафедра Истории математики MSU успеет помочь), хоть это и достаточно далеко от предмета.
6 фев 18, 16:22    [21170463]     Ответить | Цитировать Сообщить модератору
Все форумы / Вопрос-Ответ Ответить