Express & Simplenaut
Express
Привет, задувался о том, как более эффективный алгоритм маршрутов мог бы сэкономить кучу времени на доставке? Я думаю, как ускорить процесс, и думаю, у тебя может быть отличная идея.
Simplenaut
Конечно, попробуй динамическое программирование: заранее рассчитай кратчайшие пути между хабами, а потом используй жадный алгоритм для оставшихся точек. Это уменьшит вычисления за счёт кэширования стоимости сегментов, пересчитывать придётся только когда данные о трафике обновятся. Так ты точно выиграешь время.
Express
Звучит неплохо. Давай код, надо вписать его в текущий график. Если время сэкономит – я за.
Simplenaut
Слушай, я тут код немного переделывал, чтобы оптимизировать маршрут доставки. Dijkstra алгоритм прикинул расстояния между всеми хабами, потом построил матрицу затрат, а потом уже жадный алгоритм вставил каждую точку доставки в оптимальное место. Вроде получилось неплохо.
Express
Отличный, аккуратный алгоритм Дейкстры, но жадная вставка всё равно будет O(n²) если остановок много. Просто поддерживай очередь с приоритетом для наилучшей стоимости вставки и обновляй её не сразу; это сильно сэкономит время, когда спешишь. И проверь, как ты обрабатываешь длину маршрута, пока он пустой – иначе получишь нулевой индекс для пустого списка. Небольшая доработка там – и всё готово.
Simplenaut
Спасибо за подсказки. Переключусь на приоритетную очередь, основанную на куче, для вставок и добавлю проверку, чтобы пропускать вычисление остатка, когда маршрут состоит только из начального узла. Это должно сохранить алгоритм близким к линейному и избавит от ошибки с нулевым индексом.
Express
Отлично придумал, только держи очередь небольшой, и доставку вовремя уложите. Скажи, как заработает после изменений.