Есть граф дорог. У каждого ребра и вершины есть коэффициент, который показывает как трудно проехать через эту вершину или ребро. Существует ли алгоритм нахождения минимального пути между двумя вершинами в этом графе?

Здравствуйте, na1s, Вы писали:

N>Есть граф дорог. У каждого ребра и вершины есть коэффициент, который показывает как трудно проехать через эту вершину или ребро. Существует ли алгоритм нахождения минимального пути между двумя вершинами в этом графе?

Ну обычный алгоритм Дейкстры, например. Только непонятно при чем тут поток.

Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, na1s, Вы писали:

N>>Есть граф дорог. У каждого ребра и вершины есть коэффициент, который показывает как трудно проехать через эту вершину или ребро. Существует ли алгоритм нахождения минимального пути между двумя вершинами в этом графе?

V_>Ну обычный алгоритм Дейкстры, например. Только непонятно при чем тут поток.
Граф дорог. У дорог есть коэффициент, показывающий максимальный поток, который можно провести через данное ребро.

Для улучшения понимания:
Есть граф дорог, дорога может быть авфальтовой. грунтовой и прочее. Перекрестки тоже могут обладать своими свойствами, влияющими на скорость. Но дорога бывают разными двухполосными, четырезполосными. Нужно найти кратчайщий маршрут из одной точки в другую.

Здравствуйте, na1s, Вы писали:

N>Для улучшения понимания:
N>Есть граф дорог, дорога может быть авфальтовой. грунтовой и прочее. Перекрестки тоже могут обладать своими свойствами, влияющими на скорость. Но дорога бывают разными двухполосными, четырезполосными. Нужно найти кратчайщий маршрут из одной точки в другую.

Стандартная задача о поиске кратчайшего пути в графе. Обычный алгоритм Дейкстры Вам действительно подойдет.

Здравствуйте, na1s, Вы писали:

N>Граф дорог. У дорог есть коэффициент, показывающий максимальный поток, который можно провести через данное ребро.

Выражайтесь яснее. Вам поток нужен, или маршрут? Или что-то еще?

Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, na1s, Вы писали:

N>>Граф дорог. У дорог есть коэффициент, показывающий максимальный поток, который можно провести через данное ребро.

V_>Выражайтесь яснее. Вам поток нужен, или маршрут? Или что-то еще?
Ну представьте себе город. В городе есть дороги разные. Я их уже описал. Есть множество машин в городе. Каждой надо куда-либо приехать, причем чем скорее тем лучшее. Причем проблема и в распределении машин по дорогам, чтоб они не переполнили какое-нибудь ребро. Как оптимально найти маршрут следования автомобилей?

Здравствуйте, na1s, Вы писали:

N>Здравствуйте, Vintik_69, Вы писали:

V_>>Здравствуйте, na1s, Вы писали:

N>>>Граф дорог. У дорог есть коэффициент, показывающий максимальный поток, который можно провести через данное ребро.

V_>>Выражайтесь яснее. Вам поток нужен, или маршрут? Или что-то еще?
N>Ну представьте себе город. В городе есть дороги разные. Я их уже описал. Есть множество машин в городе. Каждой надо куда-либо приехать, причем чем скорее тем лучшее. Причем проблема и в распределении машин по дорогам, чтоб они не переполнили какое-нибудь ребро. Как оптимально найти маршрут следования автомобилей?

Тогда я поясняю для Вас.

1) Есть задача о поиске минимального пути в графе. Одна машина едет из А в Б.
2) Есть задача о максимальном потоке. Много машин из А в Б.

Заметьте, что в обоих случаях ЦЕЛЕВАЯ ФУНКЦИЯ вполне определена. Она одна и ее нужно максимизировать/минимизировать.

Теперь Ваш случай. Много машин, которые ездят по всему городу, каждой хочется побыстрее. Что Вы пытаетесь добиться? Чтобы они все сразу побыстрее? Сколько машин, столько и целевых функций? Надо аггрегировать в каком-то смысле. Или не побыстрее, а побольше машин напропустить через город? Тогда задача вообще неопределена, т.к. непонятно, за какое время их пропускать ну и т.д.

Ставьте задачу четко.

Здравствуйте, vadimcher, Вы писали:

Ставьте задачу четко.

Чтоб они все сразу побыстрее, и чтоб не переполнили канал.

Здравствуйте, na1s, Вы писали:

N>Здравствуйте, vadimcher, Вы писали:
N>

N>Ставьте задачу четко.

N>Чтоб они все сразу побыстрее, и чтоб не переполнили канал.

Научитесь для начала ставить задачу. Убедитесь, что Вы сами четко понимаете, чего хотите. Вы должны ставить задачу таким образом, чтобы единственная трудность была решить ее, но не понять, что же Вы имеете в виду.

В Вашем случае "чтобы не переполнили канал" вполне понятное ограничение.
Целевая же функция не ясна никому, в том числе и Вам.

"Все сразу побыстрее" не имеет ни малейшего смысла, ибо одно решение будет минимизировать время одних в пути, а другое -- других. Например, с Можайского шоссе утром 10000 человек едет в центр на работу. Для них всех оптимально использовать Кутузовский проспект. 10-15 минут -- и ты на работе. Пропускная способность Кутузрвского, допустим 100 машин в минуту. Выходит, что за час Вы не пропустите более 6000 машин. Кого из них "минимизировать"? Этот пример всего лишь иллюстрация того, что Вы пытаетесь словами решить многоцелевую оптимизацию. Он не очень хорош тем, что он симметричный. В несимметричном случае еще хуже. У каждого из ста водителей есть точка Ai, точка Bi, время в пути ti, которое Вы хотите минимизировать сразу и для всех. Как это?

Здравствуйте, vadimcher, Вы писали:

Я как бог, для меня нет любимчиков, выберу нескольких которые поедут по кутузовскому, другие поедут другим способом. Надо найти оптимальный вариант, когда все было бы не так хреново. Как то ведь пакеты маршруизуются? Там ведь тоже такая же задача.

Здравствуйте, na1s, Вы писали:

N>Здравствуйте, vadimcher, Вы писали:

N>Я как бог, для меня нет любимчиков, выберу нескольких которые поедут по кутузовскому, другие поедут другим способом. Надо найти оптимальный вариант, когда все было бы не так хреново. Как то ведь пакеты маршруизуются? Там ведь тоже такая же задача.

Назовите одно конкретное число, которое Вы хотите максимизировать/минимизировать.

Здравствуйте, na1s, Вы писали:
N>Как то ведь пакеты маршруизуются? Там ведь тоже такая же задача.

На эту тему можно почитать "Компьютерные Сети" Танненбаума.

Здравствуйте, na1s, Вы писали:

N>>>Граф дорог. У дорог есть коэффициент, показывающий максимальный поток, который можно провести через данное ребро.

V_>>Выражайтесь яснее. Вам поток нужен, или маршрут? Или что-то еще?
N>Ну представьте себе город. В городе есть дороги разные. Я их уже описал. Есть множество машин в городе. Каждой надо куда-либо приехать, причем чем скорее тем лучшее. Причем проблема и в распределении машин по дорогам, чтоб они не переполнили какое-нибудь ребро. Как оптимально найти маршрут следования автомобилей?

Если я правильно понял задачу. Есть граф дорог. Каждое ребро характеризуется пропускной способностью (количество машин) и временем движения (или расстоянием) по нему. Необходимо распределить поток машин из А в Б не превышая пропускную способность дорог минимизируя время в пути.

1. Находим кратчайший маршрут из А в Б.
2. Определяем пропускную способность этого маршрута = p. Т.е. пропускную способность "наименее пропускаемого" ребра входящего в этот маршрут.
3. "Пускаем" по этому маршруту p машин.
4. Корректируем граф: уменьшаем пропускную способность всех ребер маршрута из п.1 на p (как следствие ребра с исчерпавшейся пропускной способностью будут исключены из графа)
5. Повторяем начиная с п.1 пока не "разрулим" все машины.

Если машины одновременно едут из различных пунктов А в различные пункты Б, то надо определяться в приоритетах — какие машины необходимо пропускать первыми (из конкретных пунктов, равномерно из всех и т.п.).

Вроде так, IMHO

Здравствуйте, na1s, Вы писали:

Ищи "многопродуктовый поток в сети". Допустим есть граф(транспортная сеть) с заданными пропускными способностями и ценами прохождения единицы продукта через ребро. В сети движутся N разных продуктов, для каждого из которых определен источник, пункт назначения и минимальное количество продукта, которое необходимо доставить. Необходимо сказать, по какому маршруту должен двигаться каждый продукт, чтобы доставить количество, равное минимальному необходимому, при том затратив минимум денег. Насколько я знаю(пол года назад писал курсовую на подобную тему), не существует алгоритма, во всех случаях способного дать ответ на такую задачу за полиномиальное время. Я решал задачу о допустимости(дает ответ на вопрос, могут ли продукты пройти через заданную сеть, не учитывая цены). Решал как задачу ЛП. Вроде бы можно и первую задачу привести к задаче линейного программирования и решить симплекс-методом. Впрочем, я не завидую человеку, который решится реализовывать такую вещь.

Здравствуйте, Mace, Вы писали:

M>Здравствуйте, na1s, Вы писали:

M>Ищи "многопродуктовый поток в сети". Допустим есть граф(транспортная сеть) с заданными пропускными способностями и ценами прохождения единицы продукта через ребро. В сети движутся N разных продуктов, для каждого из которых определен источник, пункт назначения и минимальное количество продукта, которое необходимо доставить. Необходимо сказать, по какому маршруту должен двигаться каждый продукт, чтобы доставить количество, равное минимальному необходимому, при том затратив минимум денег. Насколько я знаю(пол года назад писал курсовую на подобную тему), не существует алгоритма, во всех случаях способного дать ответ на такую задачу за полиномиальное время. Я решал задачу о допустимости(дает ответ на вопрос, могут ли продукты пройти через заданную сеть, не учитывая цены). Решал как задачу ЛП. Вроде бы можно и первую задачу привести к задаче линейного программирования и решить симплекс-методом. Впрочем, я не завидую человеку, который решится реализовывать такую вещь.

Теперь я что-то начинаю понимать. По видимому требуется минимизировать максимальное время в пути.

Т.е., грубо говоря, есть граф, набор авто, у каждого пункты отправления и назначения. Предположим, что мы запускаем всех по определенным маршрутам. Этого НЕ достаточно. Надо определить очередность проезда автомобилей. Допустим, что они все едут по тому же Кутузовскому, а потом разъезжаются по разным улицам. В начале Кутузовского "столпилась" куча народу. Порядок их проезда по нему будет влиять на загруженность улиц в конце Кутузовского, так как там каждый едет уже по своей улице. Таким образом, на любой улице в конце Кутузовского загруженность может быть большой, но растянутой во времени, т.е. авто едут без задержки, либо большой за короткий период (если мы всех таких, кто собирается ехать по этой улице, запустим по Кутузовскому одновременно).

Задача с продуктами видится мне вполне подъемной, с машинами -- Какой хоть порядок задачи (количество улиц, машин).

Здравствуйте, vadimcher, Вы писали:

V>Задача с продуктами видится мне вполне подъемной, с машинами -- Какой хоть порядок задачи (количество улиц, машин).

Собственно, термин "продукты" в данном случае не очень удачен, я себе слабо представляю, как, например, сгущенка и нефть будут паралельно двигатся по одной трубе, а потом расходится по разным пунктам назначения да еще и без последствий То есть продукт знает, откуда и куда он движется — чем не автомобиль?)) Я думаю в масштабах той же Москвы можно абстрагироватся от индивидуальных особенностей автомобиля и считать его просто единицей "продукта". Другое дело, что в таких масштабах эту задачу решить практически не возможно...

Здравствуйте, Mace, Вы писали:

M>Здравствуйте, vadimcher, Вы писали:

V>>Задача с продуктами видится мне вполне подъемной, с машинами -- Какой хоть порядок задачи (количество улиц, машин).

M>Собственно, термин "продукты" в данном случае не очень удачен, я себе слабо представляю, как, например, сгущенка и нефть будут паралельно двигатся по одной трубе, а потом расходится по разным пунктам назначения да еще и без последствий То есть продукт знает, откуда и куда он движется — чем не автомобиль?)) Я думаю в масштабах той же Москвы можно абстрагироватся от индивидуальных особенностей автомобиля и считать его просто единицей "продукта". Другое дело, что в таких масштабах эту задачу решить практически не возможно...

Ну так вопрос именно об масштабе решаемой задачи (вопрос к автору исходного топика, если он нас еще читает ).

Что же касается продуктов, то, грубо говоря, я представил себе такую ситуацию: 5-10 складов, 20-30 магазинов, надо определенные товары в определенные магазины. Ну в общем, решаемо. А если у Вас 2000000 автомобилей, едущих только в центр с утра, 3500 улиц, для каждой есть какие-то цифры пропускной способности, для каждой нужно установить приоритет и т.п.