Задача - обойти прямоугольное помещение за минимальное время. Надо покрыть всю площадь, препятствий нет. Есть что-то оптимальней "змейки"?
Если принципиально - старт из угла
Денис Загаевский: По времени, т.е. минимум поворотов и не ездить по одним и тем же квадратам. Nwton: Цель именно такая - побывать везде и снять данные.
Андрей: По диагонали можно, но тогда условные квадраты тоже по диагоналям расположены, т.к. квадрат = габарит робота. Робот останавливается, берет пробу, проезжает свой габарит и цикл повторяется. "Стоимость" поворота грубо 90 градусов = проезд одного квадрата по прямой
Если поворот «бесплатен», эквивалентны все несамопересекающиеся маршруты.
Если нет — точного доказательства не вижу, но, по-видимому, тоже оптимальна (2h−2 поворота).
UPD1. Если из-за каких-то особенностей прохождения поворотов на скорости нежелательны развороты на 180° — тогда спираль с первым отрезком по длинной стороне.
Mercury13 , ну Вы же знаете задачку о том, как зачеркнуть девять точек, расположенных квадратом 3х3, проведя строго 4 отрезка и не отрывая при этом карандаша от бумаги ? Так что не всегда спираль самая оптимальная (в маленьких пространствах) ...
Средний
