Задача про убегание от хищников

vitamin8808

Такая задача: вы находитесь на плоскости и окружены львами. Например, 3 льва расположены в вершинах равностороннего треугольника со стороной 10, а вы в центре. Львы всегда бегут прямо на вас. У двух скорость 20, у третьего 10. Ваша от 0 до 10(по желанию). Насколько максимально можно продлить время своей жизни?
Один русский проф мне сказал, что это известная головоломка и решение у неё очень трудное и распечатки с этой задачей немцы разбрасывали над Англией, чтобы отвлечь английских математиков от расшифровки Энигмы :lol: (уж не знаю, правда это или нет)
Кто-нибудь знает, как подобные задачи вообще решаются? Хотя бы численно.
Проблема в том, что оптимальное глобально решение может быть не оптимальным локально. Например, в 1-мерном случае, когда только 2 льва, медленный очень близко, а быстрый далеко, нужно сначала к быстрому льву бежать.

gr_nik

А львы как бегают? Всегда на тебя или тоже время как-то минимизируют?

vitamin8808

Львы всегда бегут прямо на вас.

Suveren

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

a7137928

Например, в 1-мерном случае, когда только 2 льва, медленный очень близко, а быстрый далеко, нужно сначала к быстрому льву бежать.
Это неверно. Так делать можно, но не "нужно".
В одномерном случае нельзя прожить дольше, чем время, которое потребуется двум львам, чтобы сойтись в одной точке, когда они тебя гарантированно поймают.
Таким образом, если ты доберешься до этой точки встречи раньше, чем любой из львов, и будешь там спокойно ждать своей судьбы, то ты решил задачу, прожил максимум времени. Но подобных оптимальных решений целая куча: ты можешь выйти в точку встречи и стоять там, или погулять вокруг, пока львы подходят, или двигаться туда по какой-нибудь хитрой траектории.
Так что в описанном тобой одномерном случае, когда быстрый далеко, медленный близко, и наша максимальная скорость равна скорости медленного, совершенно не обязательно "сначала к быстрому льву бежать". Можно, например, сначала побежать к медленному, сблизиться с ним на произвольное (в т.ч. бесконечно малое) расстояние, потом развернуться и со скоростью медленного льва (т.е. со своей максимальной) двигать к точке встречи. Достигнув её, ждать съедения.
Куча решений, короче.
************************************
По общей задаче. Изначально я думал предложить составить некую "функцию безопасности" и локально её максимизировать в каждый момент времени. Например, в качестве такой функции может служить время, которое ты проживёшь, если будешь стоять на месте. Т.е. в каждый момент времени ты перемещаешься в доступную точку, где тебе наиболее выгодно (наиболее долго) ждать смерти.
Такой способ, видимо, не приведёт к универсальному решению, так как нужно угадать правильную функцию безопасности. А с учётом того, что локально лучшее решение не обязано являться глобально лучшим, такой функции вообще может и не быть.
Но таким способом, видимо, можно найти какие-то нетривиальные траектории, более оптимальные, чем "стоять на месте".
А вообще, конечно, задача очень хитрая. И явно наличие решений очень сильно зависит от начальных условий (расположение и скорости львов, максимальная скорость человека).

a7137928

Да, пожалуй, в одномерном случае с двумя львами всё просто. Нужно смотреть, успеешь ли ты прийти в точку встречи львов раньше всех.
Если не успеешь, то у тебя единственное решение - двигать туда. По дороге тебя догонят и сожрут.
Если успеешь, то почти любая траектория, приводящая тебя в точку встречи к моменту встречи львов, является решением. "Почти любая" - потому что надо исключить траектории, на которых ты несколько (четное число) раз пересекаешься с львами. Такие траектории появляются, когда твоя максимальная скорость больше скорости хотя бы одного из львов.

a7137928

Зараза, не отпускает :)
Такой вопрос появился: а вообще тигр на плоскости имеет шансы схавать человека, если его скорость равна скорости человека? По ходу дела, не может он этого сделать, разве что человек будет идти ему чётко навстречу. Если же человек хоть чуток отклонится, то тигр как ракета с головкой самонаведения совершит крутой вираж, окажется сзади и при равенстве скоростей никогда не догонит.
Если эта гипотеза верна, то исходная задача (три тигра на плоскости) решается просто. Медленный тигр не есть угроза, из соображений симметрии человеку надо держаться на одинаковом расстоянии от двух быстрых. Т.е. идти точно на медленного, поблизости от него совершить бесконечно малый манёвр (и медленный больше не страшен потом топать по прямой, пока не догонят быстрые.

svetik5623190

Меня бесит, когда лиди пишут такие вот вещи, потому что непонятно, что имеется в виду:
сблизиться с ним на произвольное (в т.ч. бесконечно малое) расстояние, потом развернуться

совершить бесконечно малый манёвр
"Сколь угодно малое число" - это я понимаю, что такое. "Бесконечно малое" - не понимаю.

freya83

Короче в каждый момент времени надо двигаться с максимальной скоростью по направлению вектора суммы скоростей всех львов.

a100243

хм, я уже постил её, только разделом ошибся:

mong

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

mong

чё ? прямиком на медленного льва с макс скоростью !? :shocked:

freya83

чё ? прямиком на медленного льва с макс скоростью !?

ага :)

mong

это как-т немного странна

freya83

Беги на быстрого - дольше проживешь :)
а вообще, да, где-то косяк, должно еще как-то расстояние до львов входить.

stm7524300

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

a7137928

"Сколь угодно малое число" - это я понимаю, что такое. "Бесконечно малое" - не понимаю.
Это значит: я могу сблизиться со львом на сколь угодно малое расстояние, потом совершить манёвр, и лев меня не поймает. Значит, в пределе я могу не совершать никакого манёвра, и лев меня не поймает.

mainbest

Я так понимаю у львов нет какой-то особой стратегии, просто они в любой момент времени бегут на жертву.

stm7524300

ну да, именно это я и пропустила мимо ушей : )

mainbest

По-моему это не верно, Скорость льва (медленного) будет всегда больше (кроме случая совпадающих курсов) проекции скорости человека на прямую лев-человек.

tinka2302

Ну вообще-то, как я понимаю, убежать от "медленного" льва можно только в том случае, если двигаться от него строго по прямой лев-человек.
Не знаю, можно ли совершить такой маневр, чтобы оказаться от льва по другую сторону на этой же прямой.
По-моему это не верно, Скорость льва (медленного) будет всегда больше (кроме случая совпадающих курсов) проекции скорости человека на прямую лев-человек.
Да, это так. Но до определенного момента можно позволить льву догонять себя.
Главное успеть встать на нужный курс до того, как лев тебя догонит.
Вот и интересно, возможно ли это.

freya83

Беги на быстрого - дольше проживешь

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

k11122nu

Молиться надо.
____________________________________________
16 Тогда царь повелел, и привели Даниила, и бросили в ров львиный; при этом царь сказал Даниилу: Бог твой, Которому ты неизменно служишь, Он спасет тебя!
17 И принесен был камень и положен на отверстие рва, и царь запечатал его перстнем своим, и перстнем вельмож своих, чтобы ничто не переменилось в распоряжении о Данииле.
18 Затем царь пошел в свой дворец, лег спать без ужина, и даже не велел вносить к нему пищи, и сон бежал от него.
19 Поутру же царь встал на рассвете и поспешно пошел ко рву львиному,
20 и, подойдя ко рву, жалобным голосом кликнул Даниила, и сказал царь Даниилу: Даниил, раб Бога живаго! Бог твой, Которому ты неизменно служишь, мог ли спасти тебя от львов?
21 Тогда Даниил сказал царю: царь! вовеки живи!
22 Бог мой послал Ангела Своего и заградил пасть львам, и они не повредили мне, потому что я оказался пред Ним чист, да и перед тобою, царь, я не сделал преступления.
Дан. 6:16-22

mainbest

Это понятно, но бежать на льва глупо. Я так думаю надо бежать между медленным и быстрым львами, так, чтобы их относительные скорости (относительно человека) равнялись (будет что-то вроде v=20-10*cos(\alpha)=10+10*cos(\beta-\alpha где \alpha - угол между траекториями движения быстрого льва и человека, \beta - угол между траекториями движения львов. В начальный момент времени \beta=4/6pi

mainbest

Осталось выписать уравнение для поиска \beta...

seregaohota

Ну вообще-то, как я понимаю, убежать от "медленного" льва можно только в том случае, если двигаться от него строго по прямой лев-человек
Нет, если ты бежишь по прямой Ox с постоянной скоростью, а лев скажем в точке (0,y y>0, то лев тебя не догонит за конечное время. Его траектория будет что-то типа гиперболы, с асимптотой - твоей прямой, по которой ты бежишь. То же если ты бегаешь по окружности с центром в начальном положении льва, его траектория будет что-то типа раскручивающейся спирали с асимптотической окружностью в конце (а может с окружностью я ошибаюсь).
Мне кажется если бежать с максимальной скоростью, и чтобы проекция моей скорости на вектор я-лев была неположительна, то есть достаточно большой набор моих траекторий, что лев не догонит. Главное чтобы асимптотическим я бежал почти по направлению от него.
Для быстрых львов всё грустнее.

a7137928

Нет, если ты бежишь по прямой Ox с постоянной скоростью, а лев скажем в точке (0,y y>0, то лев тебя не догонит за конечное время. Его траектория будет что-то типа гиперболы, с асимптотой - твоей прямой, по которой ты бежишь.
Вот-вот! Я про это и писал. Вроде интуитивно именно так и получается. Но по-хорошему надо бы вывести уравнение траектории, из которого это будет следовать. Там будет система из двух диффуров, надо с ней покопаться.

luherstag

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

tinka2302

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

mainbest

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

vitamin8808

тогда подзадача: лев начинает с точки [math]$(0, -a a>0$[/math], вы из начала координат, ваша траектория [math]$(10t,0)$[/math]. Найти координаты льва как функцию от времени.У меня какая-то страшная система получается.
 А вообще да, если медленного льва можно обогнуть, то да, нужно на медленного бежать.

vitamin8808

Я так думаю надо бежать между медленным и быстрым львами, так, чтобы их относительные скорости (относительно человека) равнялись (будет что-то вроде v=20-10*cos(\alpha)=10+10*cos(\beta-\alpha где \alpha - угол между траекториями движения быстрого льва и человека, \beta - угол между траекториями движения львов. В начальный момент времени \beta=4/6pi
это локальное условие, а оптимальное решение запросто может ему не удовлетворять.

seregaohota

Выбирая систему единиц, в которой скорости льва и человека 1, и взяв для простоты положение льва в начальный момент в точке (0,1 человек в момент t находится в точке (t,0) а лев в точке (x,y вектор лев-человек будет (t-x, 0-y) длины [math]$\sqrt{(t-x)^2 + y^2}$[/math], скорость льва 1 и паралельна данному вектору, проекции скорости находятся из пропорции (ну или соответствующие направляющие косинусы этого вектора - просто нормируем вектор лев-человек, получим скорость льва)
[math]  $$  \begin{cases}  \frac{dx}{dt} = \frac{t-x}{\sqrt{(t-x)^2 + y^2}} \\  \frac{dy}{dt} = \frac{0-y}{\sqrt{(t-x)^2 + y^2}}  \end{cases}  \quad x(0)=0,\; y(0)=1  $$  [/math]
Путного решения у меня не получилось.
Можно (чтобы x в бесконечность не уходил) взять за новые переменные координаты вектора лев-человек X=t-x, Y=-y и следить, собственно нас интересует чтобы этот вектор в 0 не обратился за конечное время.
[math]  $$  \begin{cases}  \frac{dX}{dt} = 1-\frac{X}{\sqrt{X^2 + Y^2}} \\  \frac{dY}{dt} = \phantom{0}-\frac{Y}{\sqrt{(X^2 + Y^2}}  \end{cases}  \quad X(0)=0,\; Y(0)=1  $$  [/math]
В общем случае, когда человек движется по заданному закону со скоростью [math]$(u(tv(t\; u^2+v^2=1$[/math] - скорости льва и человека 1 получим для вектора лев-человек
[math]  $$  \begin{cases}  \frac{dX}{dt} = u(t)-\frac{X}{\sqrt{X^2 + Y^2}} \\  \frac{dY}{dt} = v(t)-\frac{Y}{\sqrt{(X^2 + Y^2}}  \end{cases}  \quad X(0)=X_0,\; Y(0)=Y_0  $$  [/math]
при скорости льва q и скорости человека 1 получим
[math]  $$  \begin{cases}  \frac{dX}{dt} = u(t)-q\frac{X}{\sqrt{X^2 + Y^2}} \\  \frac{dY}{dt} = v(t)-q\frac{Y}{\sqrt{(X^2 + Y^2}}  \end{cases}  \quad X(0)=X_0,\; Y(0)=Y_0  $$  [/math]
При q>1 (например 2) это быстрый лев, при q=1 медленный, при q<1 вообще тормоз, при q<0 он от нас вообще убегает - трус. :)
Вроде всё так.
Вообще для 3 львов это будет три системы дифуров и задача оптимизации на время встречи [math]$T \to \sup$[/math] и поиска оптимального управления [math]$(u(tv(t$[/math] при ограничении что скорость человека 1: [math]$u^2+v^2=1$[/math]. Подобные задачи дают на мехмате на 4 курсе по чмам, но мне не попадалась. Подвалите к своему преподу (я не могу, я не в МГУ сейчас) и попытайте на предмет численного решения :) Если что-то красивое получится следующему курсу через год в задания включат и они вам будут признательны ;)

vitamin8808

у меня точно такая же система получалась. Но как её решать?

seregaohota

Мой любимый клён то бишь Maple меня послал я минут пять днём повозился. А сейчас что-то влом. А может я там в dsolve(sysODE, ICs) чего намудрил из-за спешки. Численно не интегрировал ни в Maple, ни так. Мне правда некогда было всё горит, даже сгорело. Я сегодня на работе последний день, а надо проект передать - в базу выложить. Придётся в выходные париться. И ещё проставиться надо было под вечер коллегам.
Ищу работу кстати. Умею флудить на форумах по делу. :) Ну и всякие компьютерно-математическо-механические дела. Правда я старый, у меня дочка MM уже закончила. Из-за неё и на флокал попал, да так и завис чего-й то не только в привате. Поэтому я лужу-паяю, чмы починяю по инерции у кого прохудились. В приват короче.

vitamin8808

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

luherstag

Охх, не помню. В семидесятых-восьмидесятых (но полной уверенности нет). Там вроде формулировалось про лису и собаку, может где в названии промелькнёт...

aldo63

На самом деле, это же ясно: всегда можно разложить скорость догоняющего объекта на скорость, перпендикулярную движению убегающего, и скорость, параллельную движению убегающего.
Чтобы догоняющий мог догнать, необходимо, чтобы параллельная проекция скорости была больше, чем у убегающего. В случае равенства модулей скоростей это возможно только в том случае, если убегающий сам бежит про прямой на догоняющего.

romanenkoroman1

А может можно всех трёх тигров бошками столкнуть? Может, после этого их характеристики поослабнут? :grin:

a100243

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

vitamin8808

да это-то тривиально. Просто может там есть ссылки на решение с двумя-тремя львами.

vitamin8808

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

romanenkoroman1

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

вот и нет: сначала быстрый наскакивает на медленного, в результате травмы теряет скорость, и потом на него наскакивает второй быстрый. Таким макаром есть шанс не максимизировать время оставшейся жизни (весьма жалкой - проводимой в убегании от трёх зверей а спастись :)

vitamin8808

С системой сделать можно так: помножить первое уравнение на Х, второе на Y и сложить. После преобразований всё получается. В моих обозначениях, когда бежим на север(0,1 выходит
[math]$v\sqrt{x^2(t)+(y(t)-t)^2}-y(t)=-v^2t+C$[/math], где v — скорость динозаврика.
Ещё одно уравнение(но оно не интегрируется) получается, если первое умножить на Y, второе на X, и вычесть из первого. Выходит что-то типа(в моих обозначениях)
[math]$\dfrac{d}{dt}\left(\dfrac YX\right)=\dfrac 1X$[/math].