Задача 2. «Маршрут складского робота» На складе автономный робот должен забрать товары из трёх ячеек (X, Y, Z) и привезти их на базу (0). Робот стартует с базы. Вместимость робота ограничена: он может одновременно перевозить не более двух товаров. Чтобы забрать третий товар, он обязан сначала вернуться на базу, выгрузить собранное и только затем продолжить маршрут. Расстояния между точками симметричны и составляют: • от базы 0 до Х: 10 м; • от базы 0 до Ү: 15 м; • от базы 0 до Z: 20 м; • от Х до Ү: 5 м; • от У до Z: 5 м; • от Х до Z: 12 м. Чему равно минимальное общее расстояние (в метрах), которое пройдёт робот, чтобы доставить все три товара на базу по оптимальному маршруту?

Краткое пояснение:

Пошаговое решение:

Робот стартует с базы (0) и должен доставить три товара из ячеек X, Y, Z.

Вариант 1: Сначала везет два товара, потом один.

1. Шаг 1: Робот забирает два ближайших товара, например, X и Y (расстояние 0 -> X -> Y = 10 + 5 = 15 м).
2. Шаг 2: Возвращается на базу с двумя товарами (Y -> 0 = 15 м). Общее расстояние: 15 + 15 = 30 м.
3. Шаг 3: Робот едет за третьим товаром (Z). Маршрут 0 -> Z = 20 м.
4. Шаг 4: Возвращается на базу с третьим товаром (Z -> 0 = 20 м). Общее расстояние: 30 + 20 + 20 = 70 м.

Давайте рассмотрим другие комбинации для первых двух товаров:

• X и Z: 0 -> X -> Z = 10 + 12 = 22 м. Возврат: Z -> 0 = 20 м. Общее: 22 + 20 = 42 м. Затем за Y: 0 -> Y = 15 м, Y -> 0 = 15 м. Итого: 42 + 15 + 15 = 72 м.
• Y и Z: 0 -> Y -> Z = 15 + 5 = 20 м. Возврат: Z -> 0 = 20 м. Общее: 20 + 20 = 40 м. Затем за X: 0 -> X = 10 м, X -> 0 = 10 м. Итого: 40 + 10 + 10 = 60 м.

Вариант 2: По одному товару за раз (менее оптимален из-за вместимости, но рассмотрим для полноты).

Если бы робот мог брать только один товар:

• 0 -> X -> 0 = 10 + 10 = 20 м.
• 0 -> Y -> 0 = 15 + 15 = 30 м.
• 0 -> Z -> 0 = 20 + 20 = 40 м.
• Итого: 20 + 30 + 40 = 90 м.

Вариант 3: Комбинированный маршрут, где робот сначала везет один, потом два.

Предположим, робот везет сначала товар X:

1. Шаг 1: 0 -> X = 10 м.
2. Шаг 2: X -> 0 = 10 м. Общее: 10 + 10 = 20 м.
3. Шаг 3: Теперь робот должен забрать Y и Z. Наиболее короткий путь для этого — 0 -> Y -> Z = 15 + 5 = 20 м.
4. Шаг 4: Возврат на базу с Y и Z: Z -> 0 = 20 м. Общее: 20 + 20 + 20 = 60 м.

Рассмотрим другие комбинации для второго этапа:

• Сначала X (20 м), потом 0 -> Z -> Y = 20 + 5 = 25 м, Y -> 0 = 15 м. Итого: 20 + 25 + 15 = 60 м.
• Сначала Y (30 м), потом 0 -> X -> Z = 10 + 12 = 22 м, Z -> 0 = 20 м. Итого: 30 + 22 + 20 = 72 м.
• Сначала Y (30 м), потом 0 -> Z -> X = 20 + 12 = 32 м, X -> 0 = 10 м. Итого: 30 + 32 + 10 = 72 м.
• Сначала Z (40 м), потом 0 -> X -> Y = 10 + 5 = 15 м, Y -> 0 = 15 м. Итого: 40 + 15 + 15 = 70 м.
• Сначала Z (40 м), потом 0 -> Y -> X = 15 + 5 = 20 м, X -> 0 = 10 м. Итого: 40 + 20 + 10 = 70 м.

Анализ оптимальных маршрутов:

Маршрут 1: 0 -> X -> Y (10+5=15 м) -> 0 (15 м) -> Z (20 м) -> 0 (20 м). Общее: 15 + 15 + 20 + 20 = 70 м.

Маршрут 2: 0 -> Y -> Z (15+5=20 м) -> 0 (20 м) -> X (10 м) -> 0 (10 м). Общее: 20 + 20 + 10 + 10 = 60 м.

Маршрут 3: 0 -> X -> Z (10+12=22 м) -> 0 (20 м) -> Y (15 м) -> 0 (15 м). Общее: 22 + 20 + 15 + 15 = 72 м.

Маршрут 4: 0 -> X (10 м) -> 0 (10 м) -> Y -> Z (15+5=20 м) -> 0 (20 м). Общее: 10 + 10 + 20 + 20 = 60 м.

Маршрут 5: 0 -> Y (15 м) -> 0 (15 м) -> X -> Z (10+12=22 м) -> 0 (20 м). Общее: 15 + 15 + 22 + 20 = 72 м.

Маршрут 6: 0 -> Z (20 м) -> 0 (20 м) -> X -> Y (10+5=15 м) -> 0 (15 м). Общее: 20 + 20 + 15 + 15 = 70 м.

Сравним расстояния: 70 м, 60 м, 72 м, 60 м, 72 м, 70 м.

Минимальное расстояние составляет 60 метров.

Два оптимальных маршрута, дающие минимальное расстояние 60 м:

1. Маршрут 1: 0 -> Y -> Z (15+5=20 м). Возврат на базу Z -> 0 (20 м). Затем 0 -> X (10 м). Возврат на базу X -> 0 (10 м). Общая длина: 20 + 20 + 10 + 10 = 60 м.
2. Маршрут 2: 0 -> X (10 м). Возврат на базу X -> 0 (10 м). Затем 0 -> Y -> Z (15+5=20 м). Возврат на базу Z -> 0 (20 м). Общая длина: 10 + 10 + 20 + 20 = 60 м.

Важно: В обоих случаях робот сначала забирает один товар, возвращается, а затем забирает оставшиеся два, так как это позволяет минимизировать общее расстояние.

Почему вариант с двумя товарами в начале не оптимален?

Если робот забирает Y и Z сначала (0 -> Y -> Z = 20 м), возвращается (Z -> 0 = 20 м), это уже 40 м. Затем ему нужно ехать за X (0 -> X = 10 м) и возвращаться (X -> 0 = 10 м), итого 40 + 10 + 10 = 60 м. Этот путь тоже равен 60 метрам. Однако, стоит учесть, что самый короткий путь для двух товаров из X, Y, Z, которые можно везти одновременно, это Y и Z (15+5=20 м), или X и Y (10+5=15 м). Наиболее коротким маршрутом для первого этапа, где робот везет два товара, будет 0->X->Y (15 м) + Y->0 (15 м) = 30 м. Затем 0->Z (20 м) + Z->0 (20 м) = 40 м. Итого 30+40=70 м.

Рассмотрим другой вариант, где робот везет два товара, но не с базы:

0 -> X (10м). Забирает X. Робот может взять еще один товар. Ближайший к X - Y (5м). Маршрут: X -> Y (5м). Теперь робот везет X и Y. Возврат на базу: Y -> 0 (15м). Пройденное расстояние: 10 + 5 + 15 = 30м. Теперь надо везти Z. Маршрут: 0 -> Z (20м). Возврат: Z -> 0 (20м). Общее: 30 + 20 + 20 = 70м.

0 -> Y (15м). Забирает Y. Ближайший к Y - X (5м). Маршрут: Y -> X (5м). Робот везет Y и X. Возврат: X -> 0 (10м). Пройденное расстояние: 15 + 5 + 10 = 30м. Теперь надо везти Z. Маршрут: 0 -> Z (20м). Возврат: Z -> 0 (20м). Общее: 30 + 20 + 20 = 70м.

0 -> Y (15м). Забирает Y. Ближайший к Y - Z (5м). Маршрут: Y -> Z (5м). Робот везет Y и Z. Возврат: Z -> 0 (20м). Пройденное расстояние: 15 + 5 + 20 = 40м. Теперь надо везти X. Маршрут: 0 -> X (10м). Возврат: X -> 0 (10м). Общее: 40 + 10 + 10 = 60м.

0 -> Z (20м). Забирает Z. Ближайший к Z - Y (5м). Маршрут: Z -> Y (5м). Робот везет Z и Y. Возврат: Y -> 0 (15м). Пройденное расстояние: 20 + 5 + 15 = 40м. Теперь надо везти X. Маршрут: 0 -> X (10м). Возврат: X -> 0 (10м). Общее: 40 + 10 + 10 = 60м.

0 -> X (10м). Забирает X. Ближайший к X - Z (12м). Маршрут: X -> Z (12м). Робот везет X и Z. Возврат: Z -> 0 (20м). Пройденное расстояние: 10 + 12 + 20 = 42м. Теперь надо везти Y. Маршрут: 0 -> Y (15м). Возврат: Y -> 0 (15м). Общее: 42 + 15 + 15 = 72м.

0 -> Z (20м). Забирает Z. Ближайший к Z - X (12м). Маршрут: Z -> X (12м). Робот везет Z и X. Возврат: X -> 0 (10м). Пройденное расстояние: 20 + 12 + 10 = 42м. Теперь надо везти Y. Маршрут: 0 -> Y (15м). Возврат: Y -> 0 (15м). Общее: 42 + 15 + 15 = 72м.

Наименьшее расстояние получилось 60 метров. Это достигается, когда робот сначала забирает один товар (либо X, либо Y, либо Z), возвращается на базу, а затем забирает два оставшихся товара, возвращаясь на базу.

Пример оптимального маршрута:

1. Робот едет с базы (0) до ячейки Y: 15 м.
2. Забирает товар Y.
3. Едет от Y до ячейки Z: 5 м.
4. Забирает товар Z (теперь везет Y и Z).
5. Возвращается на базу (0) от Z: 20 м.
6. Выгружает товары Y и Z.
7. Едет с базы (0) до ячейки X: 10 м.
8. Забирает товар X.
9. Возвращается на базу (0) от X: 10 м.
10. Выгружает товар X.

Общее пройденное расстояние: 15 + 5 + 20 + 10 + 10 = 60 м.

Другой оптимальный маршрут:

1. Робот едет с базы (0) до ячейки X: 10 м.
2. Забирает товар X.
3. Возвращается на базу (0) от X: 10 м.
4. Выгружает товар X.
5. Едет с базы (0) до ячейки Y: 15 м.
6. Забирает товар Y.
7. Едет от Y до ячейки Z: 5 м.
8. Забирает товар Z (теперь везет Y и Z).
9. Возвращается на базу (0) от Z: 20 м.
10. Выгружает товары Y и Z.

Общее пройденное расстояние: 10 + 10 + 15 + 5 + 20 = 60 м.

Еще один оптимальный маршрут (аналогичный первому, но с разным порядком первых двух):

1. Робот едет с базы (0) до ячейки Z: 20 м.
2. Забирает товар Z.
3. Едет от Z до ячейки Y: 5 м.
4. Забирает товар Y (теперь везет Z и Y).
5. Возвращается на базу (0) от Y: 15 м.
6. Выгружает товары Z и Y.
7. Едет с базы (0) до ячейки X: 10 м.
8. Забирает товар X.
9. Возвращается на базу (0) от X: 10 м.
10. Выгружает товар X.

Общее пройденное расстояние: 20 + 5 + 15 + 10 + 10 = 60 м.

Ответ: 60 м