Алгоритм обхода площади за минимальное время?

Question

[Роман Попов]

Задача - обойти прямоугольное помещение за минимальное время. Надо покрыть всю площадь, препятствий нет. Есть что-то оптимальней "змейки"?
Если принципиально - старт из угла

Comments

[Денис Загаевский]

мало инфы. Надо покрыть m*n квадратов, в любом случае. оптимизировать-то по какому параметру надо?

[Nwton]

1) А чем змейка не устраивает? 2) Назовите цель обхода. Просто побывать на каждой единице площади?

[Роман Попов]

Денис Загаевский: По времени, т.е. минимум поворотов и не ездить по одним и тем же квадратам.
Nwton: Цель именно такая - побывать везде и снять данные.

[Андрей]

Сколько "стоит" один поворот в условных единицах стоимости проезда одного квадрата ?

[Андрей]

Можно ли двигаться по диагонали ? Стоимость движения по диагонали равна 1,414 стоимости параллельно сторонам ?

[Роман Попов]

Андрей: По диагонали можно, но тогда условные квадраты тоже по диагоналям расположены, т.к. квадрат = габарит робота. Робот останавливается, берет пробу, проезжает свой габарит и цикл повторяется. "Стоимость" поворота грубо 90 градусов = проезд одного квадрата по прямой

Answer 1

[Mercury13]

Если поворот «бесплатен», эквивалентны все несамопересекающиеся маршруты.
Если нет — точного доказательства не вижу, но, по-видимому, тоже оптимальна (2h−2 поворота).

UPD1. Если из-за каких-то особенностей прохождения поворотов на скорости нежелательны развороты на 180° — тогда спираль с первым отрезком по длинной стороне.

Comments

[Роман Попов]

Посидел порисовал - похоже лучше спирали действительно ничего не придумать.

[Андрей]

Mercury13 , ну Вы же знаете задачку о том, как зачеркнуть девять точек, расположенных квадратом 3х3, проведя строго 4 отрезка и не отрывая при этом карандаша от бумаги ? Так что не всегда спираль самая оптимальная (в маленьких пространствах) ...

[Роман Попов]

Андрей: Ну у меня минимум 8х8 квадратов

[Андрей]

Это я к тому, что самые последние шаги (короткие) по спирали не всегда оптимально

Answer 2

[zergon321]

Есть "ход быка" - вот так:

1 2 3 4 5
12 13 14 15 6
11 10 9 8 7

Не думаю, что оптимальнее.

Comments

[Mercury13]

Это и есть змейка :)