Дорога и робот

[Clayton]

Робот стоит в точке A. На расстоянии не более, чем 1 км от точки А проходит дорога. Какое наименьшее расстояние нужно проехать роботу, чтобы гарантированно найти дорогу? (робот находит дорогу, только если выезжает на нее).

Я вот не пойму:задача действительно легкая и ответ $1+2\pi $,или можно придумать меньше?
Сначала думал про спираль и треугольник Рело,но длина спирали получилась больше,а на счет треугольника Рело вообще не уверен.

[RIP]

topic4252.html, особенно post36512.html#p36512.

[Clayton]

RIP в сообщении #589072 писал(а):

http://dxdy.ru/topic4252.html, особенно post36512.html#p36512.

Спасибо!

-- 25.06.2012, 23:40 --

Что-то я не могу найти этой книги J.R.Isbell. An optimal search pattern. (Исбелл.Метод оптимальных поисков).Не могли бы Вы сказать,где ее можно скачать?

[Евгений Машеров]

В худшем случае дорога проходит касательно к окружности радиусом 1 км с центром в месте стояния робота. Чтобы гарантировано её найти, надо проверить весь периметр окружности. Плюс выехать на окружность. То есть простейший ответ - он, видимо, правильный.

[Sender]

Евгений Машеров в сообщении #589258 писал(а):

Чтобы гарантировано её найти, надо проверить весь периметр окружности.

Достаточно потрогать все касательные к этой окружности.

[longstreet]

А это не одно и то же, что проехать всю длину окружности?

[Clayton]

Действительно,в Шклярском (задача №40 кажись) был показан путь,который удовлетворяет условию задачи и равен $d(1+\sqrt { 3 } +\frac { 7\pi }{ 6 } )$,где $d$-расстояние до дороги.Но на доказательство минимальности этого расстояния идет ссылка на книгу "J.R.Isbell. An optimal search pattern" ,которую я не могу найти.

[longstreet]

Ладно пока с доказательством того, что $d(1+\sqrt{3}+\frac{7\pi}{6})$ $-$ самое минимальное из всех. Я вообще не могу представить, как можно выиграть в пути по сравнению с $d+2\pi d$.

-- 26.06.2012, 15:37 --

Clayton в сообщении #589291 писал(а):

Действительно,в Шклярском (задача №40 кажись) был показан путь,который удовлетворяет условию задачи и равен $d(1+\sqrt { 3 } +\frac { 7\pi }{ 6 } )$,где $d$-расстояние до дороги.

Там разве эта формула приведена и показан путь? Я посмотрел, задачу нашёл, а вот указания пути $d(1+\sqrt { 3 } +\frac { 7\pi }{ 6 } )$ $-$ нет.

-- 26.06.2012, 15:41 --

Нашёл статью "Lost in a forest" 2003 года, с рассмотрением этой задачи:
http://mathdl.maa.org/images/upload_library/22/Ford/Finch645-654.pdf

-- 26.06.2012, 15:48 --

Вот так выглядит минимальный путь длиной $d(1+\sqrt{3}+\frac{7\pi}{6})\approx 6.397242\, d$:


Этот путь короче пути $d+2\pi d\approx 7,283185$ примерно на $0,885943\, d$. Класс!!!

-- 26.06.2012, 16:00 --

В статье, которую я привёл выше, сказано, что в 1957 году Isbell описал этот путь. Полное и детальное доказательство приведено в работе 1980 года Joris:

Цитата:

H. Joris, Le chasseur perdu dans la foret, Elem. Math. 35 (1980) 1-14

-- 26.06.2012, 16:04 --

Из картинки видно, что использовалось дополнительное условие: искомая дорога имеет форму прямой линии. Тогда понятно, что выиграть в пути можно. Без этого условия, очевидно, ответ всё же $\boxed{d(1+2\pi)}$.

[Clayton]

longstreet в сообщении #589300 писал(а):

Там разве эта формула приведена и показан путь? Я посмотрел, задачу нашёл, а вот указания пути нет.

Да,вроде в решении пункта б) был точно такой же рисунок и ссылка на книгу.

longstreet в сообщении #589300 писал(а):

H. Joris, Le chasseur perdu dans la foret, Elem. Math. 35 (1980) 1-14

Печально,если бы хотя бы на английском.. Все-таки хотелось бы увидеть доказательство.

[longstreet]

Joris, "Le chasseur perdu dans la foret":
http://gdz.sub.uni-goettingen.de/ru/dms/load/img/

[Clayton]

longstreet в сообщении #589351 писал(а):

Joris, "Le chasseur perdu dans la foret":
http://gdz.sub.uni-goettingen.de/ru/dms/load/img/

Ошибку выдает

[longstreet]

Какую? Возможно, стоит попробовать другим браузером. Например, Chrome.

[Clayton]

longstreet в сообщении #589358 писал(а):

Какую?

Ошибка сервера

longstreet в сообщении #589358 писал(а):

Возможно, стоит попробовать другим браузером. Например, Chrome.

Так я и так хром использую.Да и опера тоже ошибку показывает.

[longstreet]

Попробуйте другую ссылку. Например:
http://infoscience.epfl.ch/record/130395/files/PPN378850199_0035__0_0.pdf

-- 26.06.2012, 17:53 --

Также в "Lost in a forest" сказано, что эту задачу рассматривал и Melzak в
"Companion to Concrete Mathematics: Mathematical Techniques and Various Applications"
[Wiley, New York, 1973, pp. 150-153].

Эту книгу можно скачать, например, здесь. Доказательство там приведено.

[longstreet]

Clayton, если Вы разобрались в доказательстве, было бы очень здорово, если бы Вы написали сюда о нём пару слов, хотя бы идею.