| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Оптимальный план перевозок |
| Автор: mFeel 14.12.2009, 22:16 |
| Задана карта, на которой показана транспортная сеть, точки расположения складов с товаром и гаражи с транспортом. Алгоритм принимает от пользователя точку положения заказчика и заказ на доставку груза в некотором объеме(количестве). Построить оптимальный путь для автомобиля, который заедет на склад, возьмёт товар и привезёт в точку заказа. Мое решение задачи. -Задан взвешенный неор граф(множеством вершин и множеством ребер), т е транспортная сеть. -Вес ребра графа = стоимость/километраж проезда по этому ребру(дороге) -Некоторые вершины помечены как склады с определенным количеством товара. (n) -Некоторые вершины помечены как гаражи с машинами(машина имеет неограниченную грузоподъемность, т к перевозка за 1 поездку 100 единиц товара равноценна 10 поездкам по 10 ед товара) (m) Задача: Дается вершина графа куда надо привезти заданное количество товара(заказчик), найти путь для этого. жадное решение: 1) Находим ближайший гараж к заказчику(путем перебора всех гаражей) 2) Находим ближайший склад к найденному гаражу(тоже перебором), едем туда и закружаем минимум из (требуемый товар, товар на складе) 3)Если заказ выполнен, то возвращаемся назад по известному пути Иначе ищем ближайший склад к текущему складу и едем туда...... Ездим по ближайшим складам, пока не выполним заказ. Общий алгоритм: 1)найти кратчайшие пути до всех гаражей от заказчика.(всего m путей) 2)найти кратчайшие пути от каждого склада до каждого гаража( уже m*n путей) 3)найти кратчайшие пути от текущего склада до другого( всего m*m*n - те, где заказ выполнен) .... до тех пор, пока все пути не будут с выполненными заказами или текущая стоимость проезда > текущей минимальной. Вопросы: 1)можно ли в п1, 2 жадного решения обойтись без перебора? 2)Существует ли более оптимальный метод поиска точного решения? 3)Каким образом можно оптимизировать этот алгоритм, т к дисциплина называется "методы оптимизации" PS: я понимаю, что жадный алгоритм не найдет оптимального решения |
| Автор: VictorTsaregorodtsev 15.12.2009, 16:09 |
| Методы оптимизации оптимизируют в первую очередь не алгоритм, а качество решения задачи (понимаемое как достижение именно наилучшего при тех или иных ограничениях решения по сравнению с альтернативными вариантами). Хочу заметить, что чаще всего решение транспортных задач описывается в учебниках по исследованию операций, а не по методам оптимизации - в мет.опт. обычно мало времени уделяется симплекс-методам и оптимизации на графах в пользу методов градиентной оптимизации и оптимизации с ограничениями. Поэтому советую поискать учебники по исследованию операций: переводной трехтомник Вагнера начала 1970х как чуть ли не самый лучший вплоть до настоящего времени учебник, несколько изданий учебника Вентцель, учебник Косорукова и Мищенко (он лучше первых двух только изложением задач оптимизации потоков в сети), талмуд от Тахо (если фамилию правильно помню),... |
| Автор: LPPL 24.1.2010, 21:19 |
Модератор: Сообщение скрыто. |