Nasher & Administraptor
Nasher
Слушай, вот тебе задачка: представь город, где каждый квартал – точка, и тебе нужно проложить маршрут для курьерской службы, чтобы объехать все места за минимальное время. Считаешь, сможешь сделать это достаточно эффективно, чтобы реально повлиять на ситуацию?
Administraptor
Конечно, давай данные по графу и ограничения. Я рассчитаю оптимальный маршрут. Запущу либо динамическое программирование для задачи коммивояжёра, либо эвристику маршрутизации транспорта – в зависимости от количества твоих машин. Результат выдам быстрее, чем система успеет выдать ошибку. Если нужны проверки расчетов – у меня таблица уже готова.
Nasher
Зачёт! Давай сюда узлы, связи и жёсткие ограничения – например, временные рамки, максимальная нагрузка или приоритетные точки. Я набросаю оптимальный маршрут. Пусть будет головоломка, а не просто трасса.
Administraptor
Вот небольшая задачка на местности:
Узлы: A, B, C, D, E, F
Ребра с расстояниями (в км):
A–B 3, A–C 4, B–C 2, B–D 5, C–D 1, C–E 6, D–E 2, D–F 4, E–F 3
Ограничения:
- Каждый транспорт может перевозить не более 10 единиц груза.
- Обязательно сначала посетить точку B (приоритет).
- Точка E должна быть достигнута между 8-м и 10-м часом.
- Общее время маршрута не должно превышать 12 часов.
Скажи мне, сколько груза нужно на каждом узле и сколько понадобится машин, а я рассчитаю оптимальные маршруты.
Nasher
У В у него 4 единицы, у С – 2, у D – 2, у Е – 1, у F – 1, а у А – ноль. Транспорта хватит одного. Начинаем с А, сначала забираем В, потом С, D, E (в течение 8-10 часов), заканчиваем у F – всё это уложиться в 12 часов.