пятница, 14 января 2011
22:07

все записи пользователя в сообществе Trotil
Исходные данные: путник, лес, прямая дорога на расстоянии 1 км от путника.

Путник в лесу ночью и не знает, где дорога. У путника есть возможность идти по любой заданной траектории.

Задача - найти наилучшую по расстоянию траекторию, которая выведет путника на дорогу. Наилучшей признаётся такая траектория, которая короче всех в наихудшем случае расположения дороги для путника.

@темы: Поп-математика

URL
Комментарии
14.01.2011 в 22:14

Garryncha
Холодно. Пью.
Trotil прямая дорога на расстоянии 1 км от путника
в наихудшем случае расположения дороги для путника
А разве не все расположения дороги для путника одинаковы?
URL
14.01.2011 в 22:16

Trotil
Да, все направления для путника равновероятны.
URL
14.01.2011 в 22:27

Garryncha
Холодно. Пью.
Trotil, тогда надо найти траекторию, которая просто короче всех остальных, так?
URL
14.01.2011 в 22:30

Trotil
Да.
URL
14.01.2011 в 22:34

Garryncha
Холодно. Пью.
Как вариант для сравнения с другими траекториями — прёмся в любую сторону на 1 км, а потом делаем круг с центром в первоначальной точке и радиусом 1 км. Не буду выяснять, оптимальный это вариант или нет.
URL
14.01.2011 в 22:38

Trotil
Хорошо, оставим для ориентира другим участникам. В наихудшем случае в варианте Garryncha нужно пройти (1+2Pi) км. Кто меньше? :)
URL
15.01.2011 в 00:09

Диана Шипилова
Quod erat demonstrandum
У меня меньше: 14(sqrt(2) – 1) + 2/sqrt(2 + sqrt(2)) ≈ 6.8813.
Не знаю, оптимален ли маршрут, вот худший случай:

URL
15.01.2011 в 00:21

Диана Шипилова
Quod erat demonstrandum
just normal
Точно! :friend:
11sqrt(2) – 10 + 2/sqrt(2 + sqrt(2)) ≈ 6.6387
URL
15.01.2011 в 00:26

just normal
Махнёмся жизнями?)
странно, я пересчитал у меня больше получилось)
даже коммент удалил со стыда)
URL
15.01.2011 в 00:29

Диана Шипилова
Quod erat demonstrandum
just normal
А вдруг это у меня неправильно?
URL
15.01.2011 в 00:48

just normal
Махнёмся жизнями?)
да, я сглупил
У вас как раз все правильно, только что тоже 6.639 получил
URL
15.01.2011 в 02:31

Vovanium
Маршрут длиной 7/6*%pi + sqrt(3) + 1 ~ 6,397 км получился так:
1. Идём прямо в произвольном направлении 2/3*sqrt(3) км.
2. Поворачиваем (скажем направо) на угол 2/3*%pi и идём прямо 1/3*sqrt(3) км.
3. Идём по дуге радиусом 1 км (заворачивая в ту же сторону) 7/6*%pi км.
4. Идём прямо 1 км.
Из всей серии маршрутов с данной конфигурацией (прямая, поворот, прямая, дуга с центром в начальной точке, прямая, причём точка поворота и конец траектории лежат на прямой на расстоянии 1 км) это кратчайший.
URL
15.01.2011 в 10:15

Диана Шипилова
Quod erat demonstrandum
Vovanium
Да, согласна. Я ночью уже поняла, что надо было скруглить углы и идти под углом в 30° — дифференцирование дает такой минимум :(
URL