Задачка про муравья

← →
ocean © (2005-09-09 11:07) [40]

конечно, спирали бывают разные. мне помнится только слово эпициклоида. радиус у спирали разве есть? Ну, допустим, 2 шага вперед, один влево

← →
wal © (2005-09-09 11:13) [41]

По окружности радиусом L/2. В граничных случаях (начал по касательной к "разделительной" полосе дороги, или перпендикулярно ей) получаем четверть окружности = (2*pi*L/2)/4=L*pi/4

← →
wal © (2005-09-09 11:14) [42]

> [41] wal © (09.09.05 11:13)
Сори, ошибся

← →
Lexer © (2005-09-09 12:16) [43]

КаПиБаРа, а правильный ответ будет? Интересно, всё-таки...

← →
КаПиБаРа © (2005-09-09 12:19) [44]

Lexer © (09.09.05 12:16) [43]
Когда MBo сдастся :)

← →
КаПиБаРа © (2005-09-09 12:24) [45]

Пока даже не предложили легкое решение, которое дает второй по длинне (корочине) путь.

← →
MBo © (2005-09-09 12:25) [46]

>КаПиБаРа
Известно ли решение с результатом менее 1.6 ?

← →
КаПиБаРа © (2005-09-09 12:29) [47]

MBo © (09.09.05 12:25) [46]
Мне известно решение с результатом ~1,628
Решение не мое. Сам я только до 1,707 додумался

← →
Lexer © (2005-09-09 12:34) [48]

(1+0,5^0,5) * L
1,707 :(

← →
КаПиБаРа © (2005-09-09 12:40) [49]

Lexer © (09.09.05 12:34) [48]
Есть решение?

← →
MBo © (2005-09-09 12:44) [50]

1,707 - это, видимо, Sqrt(2)/2 по прямой, затем поворот на 135 градусов и 1 по прямой.

В общем, задача состоит в нахождении фигуры с диаметром 1/2 и при этом с минимальным периметром.
Такие фигуры бывают достаточно сложны, в данном случае мне сдается, что будет 3 отрезка и дуга - но оптимум пока не нашел

(диаметр произвольной фигуры - макс. расстояние между точками в любой паре, принадлежащей границе - например, треугольник Рело - фигура с мин. площадью при заданном диаметре (так. наз. кривая постоянной ширины)).

← →
Lexer © (2005-09-09 13:05) [51]

1,618 - только вот сомнения терзают

0,5 * (5^0,5 + 1) * L

← →
КаПиБаРа © (2005-09-09 13:15) [52]

Lexer © (09.09.05 13:05) [51]
Правильно терзают.

> в данном случае мне сдается, что будет 3 отрезка и
> дуга

← →
Lexer © (2005-09-09 13:20) [53]

точно, сорри, нашел ошибку в вычислениях, всё с меня хватит! =) лично я сдаюсь

← →
Lexer © (2005-09-09 13:20) [54]

точно, сорри, нашел ошибку в вычислениях, всё с меня хватит! =) лично я сдаюсь

← →
КаПиБаРа © (2005-09-09 13:23) [55]

Если MBo не против могу решение привести.

← →
VICTOR_ (2005-09-09 13:27) [56]

По прямой
0,5
+ длина дуги окружности между отрезками 0,5 и 0,707(гипотенуза треугольника), соединенными под углом 135градусов
Ее длина, наверное, и выйдет 1,128
:)

← →
stud © (2005-09-09 13:48) [57]

а как муравей расположен относительно дороги? т.е. куда он начинает двигаться?
в зависимости от первоначального положения "как можно скорее" будет разное

← →
MBo © (2005-09-09 13:59) [58]

>КаПиБаРа
Результат 1.628 получен (благодаря моральной помощи подсказки ;)), но очень громоздко...

← →
stud © (2005-09-09 14:00) [59]

гарантировано дойти можно - пройти L/2, если не достиг обочины повернуть направо (в любую сторону) на 90 градусов, пройти еще столько же, не попал - опять на право и еще раз - не попал - теперь повернуть на 90 градусов налево и он гарантировано достигает обочины, осток пути посчитать исходя из угла под которым он шел

← →
MBo © (2005-09-09 14:00) [60]

>stud © (09.09.05 13:48) [57]
Ему известно только, что он на середине дороги и ее ширина.
Нужно выбрать стратегию, минимизирующую путь в худшем случае

← →
КаПиБаРа © (2005-09-09 14:02) [61]

Решение для дороги единичной ширины (задачу достаточно решить для l=1 в силу свойств преобразования подобия) :

Муравей должен пройти прямо расстояние sqrt(3)/3, затем повернуть на угол p/3 к направлению, противоположному направлению только что пройденного пути и снова идти прямо расстояние, равное половине расстояния, пройденного перед этим (т.е. sqrt(3)/6); затем идти расстояние p/12 по дуге окружности (так, чтобы кривая пути осталась выпуклой) радиуса 1/2 с центром в начале исходной точки пути, и окончательно пройти прямо расстояние 1/2 в направлении касательной к этой окружности проведенной в точке, завершающей пройденную дугу. Общая длина пути составит приблизительно 1,628.

Обсуждение: (См. рисунок) http://forum.dubinushka.ru/index.php?act=Attach&type=post&id=1135

Муравей находится где-то на разделительной линии дороги, т.е. на расстоянии 1/2 до любой из обочин. Это значит, что все внутренние точки круга O радиуса 1/2 с центром в месте нахождения муравья лежат на полотне дороги. Где именно находится обочина муравей не знает. Пока муравей не пройдет расстояние 1/2, он должен двигаться вдоль любого из радиусов этого круга.

Утверждения

Пусть x - некоторое пройденное муравьем расстояние по прямой вдоль любого из радиусов.

Утв. 1 При x = 1/2 кривая наименьшей длины (в дальнейшем – решение) будет состоять из прямого отрезка величиной 1/2, дуги окружности O 1-го квадранта (величиной p/4) и отрезка величиной 1/2 в направлении противоположном направлению первого отрезка.

Утв.2 При 1/2 > x > 1/sqrt(2) решение представляет собой кривую вида OABCD (которая при x = 1/sqrt(2) вырождается в решение SnowGuitar). Отрезок AB лежит на касательной к окружности O, проведенной из точки A. Отрезок CD лежит на касательной к этой же окружности, проведенной в точке C (или, что то же самое — перпендикуляре к касательной к окружности O, проведенной в точке B”, которая получена путем отражения точки B сначала относительно оси абсцисс, а затем центра окружности O) Дуга BC вырезается углом f, величина которого определяется параметром x. Общая длина пути L выражается через x, как указано на рисунке.

Утв. 3 Двухзвенная ломаная (синий пунктир) – предельное решение SnowGuitar, при x = 1/sqrt(2). Для всех x > 1/sqrt(2) решениями будут также двухзвенные ломаные с острыми углами, большими p/4. Вторые звенья будут отрезками единичной длины, имеющими начало в соответствующей т-ке x и лежащими на перпендикуляре к той из касательных к окружности O, проведенной из точки x, для которой этот перпендикуляр составит острый угол с Ox.

Замечания:

Локусом точек вида D будет дуга окружности (синий пунктир) радиуса 1/sqrt(2), а величина отрезка CD всегда равна величинам отрезков OB” = OC = OB = 1/2. В случае оптимальной траектории углы a и f, показанные на рисунке, оба равны p/6. Функция L(x) при 1/2 > x > 1/sqrt(2) имеет единственный минимум в точке x0=sqrt(3)/3, а кривая OABCD(x0) и дает общее решение задачи.

Все обсуждаемые кривые заведомо достигают "края дороги", так как муравей при движении по ним в целом "заметает" дугу, составляющую половину окружности O. Мы считаем, что муравей, находящийся вне O, "заметает" дугу путем ее вырезания из окружности O отрезками касательных проведенных из точки, где он находится.

(с) imagic

← →
stud © (2005-09-09 14:05) [62]

а получить конкретное число исходя из поставленных условий невозможно. т.к. минимум равен 0,5 а максимум .....
все остальные решения находятся между ними и соотв зависят от начальных условий движения
если я не прав - поправьте

← →
Lexer © (2005-09-09 14:17) [63]

stud © (09.09.05 14:05) [62]
>если я не прав - поправьте
Поправляю.
Ответом задачи может являтся конкретное число и никак иначе.

Как ему следует двигаться, чтобы гарантированно (и как можно скорее) достигнуть одной из обочин?

Т.е. минимальный гарантированный путь до обочины. Например путь 0,5 по прямой - не гарантирует дочтижения обочины, а значит не является решением.

КаПиБаРа, спасибо, задачка понравилась, ведь иногда всё-таки надо давать мозгам немного поработать =)

← →
MBo © (2005-09-09 14:25) [64]

>КаПиБаРа © (09.09.05 14:02) [61]
Я решал относительно угла, пройденного по дуге (Pi/6), но решение по ссылке относительно координаты, компактнее.

← →
stud © (2005-09-09 14:47) [65]

> Ответом задачи может являтся конкретное число и никак
> иначе.

если изменить начальный угол движения муравья на +-1 градус ?

← →
stud © (2005-09-09 14:50) [66]

внимание вопрос!

> Как ему следует двигаться, чтобы гарантированно (и как
> можно скорее) достигнуть одной из обочин?

ответ 1.628
?????

← →
Lexer © (2005-09-09 14:52) [67]

stud © (09.09.05 14:50) [66]
гарантированно
ответ 1.628

← →
stud © (2005-09-09 15:03) [68]

Как ему следует двигаться

т.е. результат - маршрут а не расстояние! правильно?
может всетаки вопрос некоректен?))

← →
Кабан (2005-09-09 15:31) [69]

2 stud 68
зная маршрут, можно получить расстояние, наоборот - затруднительно

ответ дан в виде расстояния, чтобы не разглашать другим участникам решение задачи

так а как насчет

> если изменить начальный угол движения муравья на +-1
> градус ?

кроме того если пройти ВС не по дуге а по прямой - вроде короче будет?

все равно)))
я утверждаю, не зная начального угла движения муравья получить оптимальный маршрут невозможно!!!!!

>stud © (09.09.05 15:39) [72]
Ты все-таки неправильно воспринял условие.
Задача состоит в том, чтобы при любом начальном угле гарантированно найти край при пробеге не более X - вот это значение X и нужно найти

> при пробеге не более X

ой ли?)) (Х в условии никак не фигурирует)
решение гарантирует достижение цели при максимальных затратах равных Х

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

> Lexer © (09.09.05 17:13) [75] [Новое
> сообщение][Ответить]

> решении найдена траектория движения муравья, с
> минимальным путем

гарантированых путей гораздо больше.
выбраный путь

> гарантирует достижение цели при максимальных затратах
> равных Х

а минимальный путь равен 0,5 а в какую сторону он пойдет это важно
т.к. в данном решении величина будет варьироваться от 0,5 до 1,628

> Попробуй получше вникнуть в само задание.

>stud
Порыля в инете, нашел подобную задачу - может, будет понятнее:
Грибник находится на расстоянии 1 км от прямой границы леса.
Про расстояние он знает, а направление - нет. Как он должен идти, чтобы быстрее и гарантированно выйти из леса

> Задачка про муравья
>КаПиБаРа © (09.09.05 09:35)

>Слепой муравей очутился посередине прямолинейной трассы шириной L. Как ему следует
>двигаться, чтобы гарантированно (и как можно скорее) достигнуть одной из обочин?

Задача не так проста, какой кажется.

Он, ведь слепой. И обладает размером.
Значит выбор пути будет статистическим, ограниченным рамками ширины шоссе. L.
И размерами муравья. Представьте на минуту, что он больше L? Во что превратится задача?

Cравним постановку задачи с такой почти уже класической задачей, как задача
о произвольно бросаемой иголке Бюффона (1760 г.)

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

Если длина самого муравья равна L1, то вероятность выбора всякой траектории,
а значит и нужной равна P=(2/Pi)(L/L1) - это следствие теоремы Коши, которая
(в данном, в тривиальном случае, касается бесконечного числа попыток муравья,
длиной L1 пересечь, достигнуть границы области, шириной L).

Понятно, что при уменьшении размеров муравья (L1) задача осложняется.

Вообще-то таковыми задачами занимается интегральная геометрия.
Когда случайное бросание единичной иголки рождает статистическую
"кинематическую меру", и пр. хитроумные штуки.

Как ему следует двигаться? Cлепому? Cлучайно, конечно!
При сравнимых размерах самого муравья и ширины дороги он с вероятностью 2/Pi достигнет,
наконец, обочины:))

Тысяча извинений за опечатку!
P=(2/Pi)(L1/L), конечно.

← →
Маклауд (2005-09-16 15:41) [80]

Я чегото не понял почему сразу нельзя пройти от центральной разметки дороги под прямым углом к обочене?

Задачка про муравья Найти похожие ветки