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

← →
КаПиБаРа © (2005-09-09 09:35) [0]

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

← →
MBo © (2005-09-09 09:42) [1]

муравью известна ширина дороги?

← →
КаПиБаРа © (2005-09-09 09:46) [2]

MBo © (09.09.05 9:42) [1]
Вы должны ему путь проложить.

← →
boalse © (2005-09-09 09:47) [3]

Ну дык... прямо к обочине???? В чём подвох???

← →
Macrodens © (2005-09-09 09:48) [4]

Прислушаться к шуму проезжающих машин и потом идти перпендикулярно проходящему звуку.

← →
Sergey13 © (2005-09-09 09:49) [5]

Строго от разделительной полосы короткими перебежками. 8-)

← →
linesoft © (2005-09-09 09:50) [6]

Судя по всему, неизвестна.
Алгоритм от этого будет зависеть

← →
КаПиБаРа © (2005-09-09 09:51) [7]

boalse © (09.09.05 9:47) [3]
Он не знает где обочина

Macrodens © (09.09.05 9:48) [4]
Машин как назло нет

Sergey13 © (09.09.05 9:49) [5]
Строго от разделительной полосы короткими перебежками
Он слепой.

← →
linesoft © (2005-09-09 09:51) [8]

>Ну дык... прямо к обочине???? В чём подвох???
Он слепой, наверно

← →
MBo © (2005-09-09 09:53) [9]

>КаПиБаРа © (09.09.05 09:46) [2]
>MBo © (09.09.05 9:42) [1]
>Вы должны ему путь проложить.
Это я понимаю, но существенно разные задачи -
1) муравей знает, что до обочины L/2
2) не знает

← →
КаПиБаРа © (2005-09-09 09:54) [10]

linesoft © (09.09.05 9:50) [6]
Ширина трассы L дана, что бы определить максимально длинный путь по предложенному вами алгоритму. Оценивается именно максимально длинный путь.

← →
КаПиБаРа © (2005-09-09 09:54) [11]

MBo © (09.09.05 9:53) [9]
Знает.

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

Если муравей заранее измерил дорогу и знает её ширину (w), то он пойдет прямо в любом направлении на расстояние 0,5^0,5 * W , если не дойдет, то повернет на 90 градусов и максимум пройдет 2^0,5 * W.

Тока это если муравей шибко умный. :)

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

Ответ: максимум 0,5^0,5 * W + 2^0,5 * W

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

У меня пока ~2.07 L получается

← →
Котик Бегемотик (2005-09-09 10:00) [15]

Вероятно муравью при его размерах совсем необязательно быть слепым :)

Ему нужно двигаться в любом направлении на расстояние L/2 и если не достиг еще обочины то повернуть на 90 градусов и двигаться пока не встретит обочину.

← →
Котик Бегемотик (2005-09-09 10:03) [16]

Во блиннн... пока писал сколько ответов появилось :)
Хотя первое что пришло в голову - это спросить другого муравья :) он то слепой но не глухой же :)))

← →
Думкин © (2005-09-09 10:03) [17]

> MBo © (09.09.05 09:59) [14]

Ну да. (1+Пи)/2.
Может и короче есть?

← →
Lexer © (2005-09-09 10:03) [18]

[15] Котик Бегемотик (09.09.05 10:00)

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

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

MBo © (09.09.05 9:59) [14]
Много

← →
КаПиБаРа © (2005-09-09 10:05) [20]

Lexer © (09.09.05 9:59) [13]
Меньше

← →
Котик Бегемотик (2005-09-09 10:06) [21]

Уточненная версия :)
Нужно двигаться в любом направлении на расстояние Sqrt(2)*(L/2) и далее по сценарию...

← →
MBo © (2005-09-09 10:06) [22]

Похоже, 1.78L (1+Pi/4)

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

MBo © (09.09.05 10:06) [22]
много

← →
Владислав © (2005-09-09 10:09) [24]

А он по окружности может двигаться? :)
Пи * L / 2

← →
КаПиБаРа © (2005-09-09 10:10) [25]

Владислав © (09.09.05 10:09) [24]
Может, но это длинный путь

← →
Труп Васи Доброго © (2005-09-09 10:13) [26]

Ну до одной из обочин он дойдёт гарантированно и по прямой. Вероятность того что он пойдёт параллельно дороге равна 0. А вот как быстрее? Ну скорее всего по окружности радиуса L/2.

← →
Думкин © (2005-09-09 10:14) [27]

> Владислав © (09.09.05 10:09) [24]

похоже, так.

← →
Труп Васи Доброго © (2005-09-09 10:18) [28]

Только как вот СЛЕПОЙ может идти по окружности?!?!? Откуда он вообще знает что такое окружность и как она выглядит?

← →
Котик Бегемотик (2005-09-09 10:19) [29]

Это же муравей а не циркуль ...
Представьте - КАК муравью размером 3 мм описать ПРАВИЛЬНУЮ окружность радиусом примером 3 метра ?
Хотя как ему ТОЧНО отмерить расстояние L/2 я тоже не представляю...

← →
boalse © (2005-09-09 10:20) [30]

Пройти минимум на расстояние L/2 в любую сторону, потом по окружности центр у которой в начальной точке движения.

← →
boalse © (2005-09-09 10:21) [31]

> Это же муравей а не циркуль ...

Сказано же:

> Вы должны ему путь проложить.

← →
Владислав © (2005-09-09 10:21) [32]

2 * L / cos(45 градусов)
:)

← →
Владислав © (2005-09-09 10:24) [33]

> Владислав © (09.09.05 10:09) [24]
> КаПиБаРа © (09.09.05 10:10) [25]
и
> Владислав © (09.09.05 10:21) [32]

Туплю :)

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

boalse © (09.09.05 10:20) [30]
Есть более короткий путь.

← →
ocean © (2005-09-09 10:46) [35]

> Есть более короткий путь.
Имеется в виду более короткий путь в самом худшем случае?

← →
ocean © (2005-09-09 10:47) [36]

ну по спирали, допустим все время уходя влево. Формулу забыл лет 15 назад

← →
КаПиБаРа © (2005-09-09 10:51) [37]

ocean © (09.09.05 10:46) [35]
Имеется в виду более короткий путь в самом худшем случае?

да

← →
boalse © (2005-09-09 10:52) [38]

> ну по спирали, допустим

Путь ещё длиннее чем у меня получится :))

← →
Lexer © (2005-09-09 11:00) [39]

> ну по спирали, допустим

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

← →
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

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

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

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

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

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

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

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

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

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

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

ответ 1.628
?????

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

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

← →
Кабан (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]

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

> Маклауд (16.09.05 15:41) [80]
> Я чегото не понял почему сразу нельзя пройти от центральной
> разметки дороги под прямым углом к обочене?

Можно, если знать куда идти. :)

← →
Маклауд (2005-09-16 16:10) [82]

ну если мы знаем что разметка дороги идет ровно посередине дороги то в любую от нее сторону по углом 90 градусов

Какая разметка? Может стоит прочитать внимательно условие?

> ну если мы знаем что разметка дороги идет ровно
> посередине дороги

так он слепой и разметку не видит

> так он слепой и разметку не видит

а он ее усиками, усиками.. :)))

← →
Маклауд (2005-09-16 22:22) [86]

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

> муравей то слепой, но по условию задачи путь ему
> пролажить должны мы

тогда нужно взять бедного зверька и бережно руками перенести через дорогу, а то не дай Бог задавят еще!

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