R
R
Roman Popov2017-02-01 20:02:23
Algorithms
Roman Popov, 2017-02-01 20:02:23

Algorithm to bypass the area in the minimum time?

The task is to bypass the rectangular room in the minimum time. It is necessary to cover the entire area, there are no obstacles. Is there something better than "snake"?
If it's important - start from the corner

Answer the question

In order to leave comments, you need to log in

2 answer(s)
M
Mercury13, 2017-02-01
@Roman_Popov

If the turn is "free", all non-self-intersecting routes are equivalent.
If not, I don’t see an exact proof, but, apparently, it is also optimal (2h−2 turns).
UPD1. If, due to some peculiarities of cornering at speed, 180° turns are undesirable, then a spiral with the first segment along the long side.

Z
zergon321, 2017-02-01
@zergon321

There is a "bull move" - ​​like this:
1 2 3 4 5
12 13 14 15 6
11 10 9 8 7
I don't think it's better.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question