Навчально-дослідна робота
«Переслідування на площині»
Введення
Полягає завдання в дуже простої речі. Є переслідувачі, один або група, і є хтось, хто намагається від них втекти. А нам важливо зрозуміти - це дуже просто тікати і наздоганяти або це можна робити безліччю способів відрізняються один від одного ефективністю. І чи важко знайти найбільш ефективний (або оптимальний) спосіб погоні або навпаки втечі.
Перш ніж приступати до аналізу розглянемо ситуацію, яка на перший погляд здається простою. Нехай деякий шматок площині огороджений парканом у формі кола і в цьому загоні лис намагається зловити кролика який бігає трохи швидше лисиця. Очевидно, що у лисиця не було б жодних шансів, якби кролик мав можливість бігти по прямій. У цьому випадку при будь-якої стратегії поведінки лисиця відстань між ними б тільки збільшувалася. Стіна може бути причиною по якій кролику доведеться розвернутися і побігти в бік лисиця і тут для лисиця виникає унікальна можливість зловити кролика.
Однак ця можливість реальна тільки для дуже спеціальної форми майданчики і при не дуже розумному поведінці кролика. Але і при самій простій формі - кола у лисиця є цікава можливість не відстати від кролика навіть при істотному відмінності в швидкостях. Покажемо, як він може це здійснити.
Попереднє зауваження. Мета кролика бути подалі від лиса. З цього випливає, що при необхідності зміни напряму кролик повинен здійснювати цю зміну так, щоб його напрямок руху становило не гострий кут з напрямком руху лисиця (інакше він почне зближення). Необхідність же зміни напряму виникає при загрозі зіткнення зі стінкою. Максимально тупий кут кролик може забезпечити собі, рухаючись вздовж стінки. Звідси випливає, що при заборі мають форму кола оптимально для кролика бігти по колу якомога більшого радіуса, тобто вздовж стіни.
Як же в цьому випадку вести себе лисицю. Припустимо, що у лисиця швидкість в два рази менше. Тоді якщо він буде бігти по колу центр якої буде співпадати з центром кола кролика але довжина її буде в два рази менше, то за один і той же час і кролик і лисиць оббегут повну окружність і отже в кожен момент часу відстань між ними буде дорівнює різниці R к - R л тобто незалежним від часу. Що й треба було довести.
Цікаве питання. Отже, ми з'ясували, що один лис може не відстати від кролика, чи не означає, що група лисиць (і може бути навіть не дуже велика) в стані кролика зловити.
Даний приклад був покликаний показати, що завдання не тривіальна і потребує ретельного дослідження, яким ми далі і займемося. А для початку сформулюємо ще раз мета дослідження:
Головна мета: З'ясувати, чи існує оптимальна стратегія як для тікає, так і для наздоганяючого і якщо так то, як її побудувати. А оптимальна стратегія - це така стратегія, яка гарантує найкращий результат незалежно від поведінки противника
Для того щоб побудувати будь-яку теорію, ми повинні строго описати основні поняття та об'єкти, а також сформулювати якісь основні твердження які будуть служити апаратом для отримання нового знання.
1 Основні поняття
Гра на переслідування, тікає гравець, група переслідувачів - Це основні поняття, їх зміст ясний інтуїтивно.
Простий рух. Простим рухом називається такий рух, при якому відстань пройдена гравцем є лінійною функцією від часу s (t) = kt. Для тих, хто добре вивчав фізику ця формула можливо асоціюється з рівномірним, прямолінійним рухом. Однак це зовсім не обов'язково. Дана формула може описувати рух, в якому вектор (а наша формула скалярна, а не векторна) швидкості з плином часу змінює напрямок, але не змінює свого модуля.
Гра на переслідування з простим рухом. Така гра - це гра в якій рух будь-якого гравця - це простий рух
Рішення гри. Знайти рішення гри - значить визначити оптимальну стратегію для всіх учасників гри і знайти оптимальний час переслідування.
Оптимальний час переслідування. Час T переслідування називається оптимальним якщо виконуються наступні умови:
При будь-якому поведінці тікає гравця існує спосіб поведінки переслідувачів гарантує зустріч хоча б одного з переслідувачів з втікаючим гравцем не пізніше часу T.
Для тікає гравця існує спосіб поведінки, що гарантує неможливість зустрічі з переслідувачами завчасно T.
Гарантійний час переслідування. Якщо для часу Т виконано тільки перше з умов описаних для оптимального часу переслідування, то час Т це гарантований час переслідування.
Гра з лінією життя. Нехай область, в якій відбувається гра представляє собою опуклу область. Її межа називається лінією життя, а гра відповідно грою з лінією життя, якщо мета тікає гравця - досягти лінії життя, а мета переслідувачів відповідно не допустити цієї події.
Безліч досяжності - це область площині кожну точку якій гравець може досягти не пізніше ніж за час Т рухаючись по якій-небудь траєкторії за законом простого руху.
Зони тікання і зони зустрічі. Зона тікання - це безліч точок площини в яких для тікає гравця є траєкторія тікання від переслідувачів. Відповідно зона зустрічі - це безліч точок в яких не існує траєкторії утікання.
2 Трохи важливих тверджень
Затвердження перше: Безліч досяжності являє собою круг.
Доказ: Ясно, що найбільш віддалена точка безлічі досяжності (віддалена від вихідної) це точка до якої гравець рухається по прямій. Побудуємо безліч всіх прямих проходять через вихідну точку. В силу однорідності властивостей площині рух уздовж однієї з цих прямих нічим не відрізняється від руху вздовж іншої прямої з чого випливає, що на кожній з прямих найбільш віддалена точка безлічі досяжності знаходиться на однаковій відстані від вихідної точки. А геометричне безліч точок знаходяться на однаковій відстані від якогось центру називається колом. У свою чергу геометричне місце точок обмежених колом називається кругом, що й потрібно було довести.
Затвердження друге. Нехай тікає гравець знаходиться в деякій точці, яку ми назвемо вихідної. Побудуємо всі можливі прямі через вихідну точку. Нехай далі переслідувач знаючи напрям руху тікає гравця, рухається по прямій забезпечує зустріч за мінімальної час. Тоді множина всіх точок зустрічі представляє собою коло.
Позначення:
P - Переслідувач
E - Тікай гравець
A - Точка Аполону
M - Точка зустрічі
Ця окружність називається колом Аполону, а точка А (найбільш віддалена точка на прямій PE) називається точкою Аполону.
Доказ: Позначимо через vp - швидкість переслідувача, а через ve швидкість тікає гравця, тоді ve * | EM | = vp * | PM |. Виберемо на площині систему координат x 0 y таким чином, щоб E (0) = (0,0), P = (0, - b), тоді
| EM | = Ö x 2 + y 2 | PM | = Ö x 2 + (y + b) 2
Підставивши цей вираз в перше співвідношення отримуємо
ve * Ö x 2 + y 2 = vp * Ö x 2 + (y + b) 2.
Зведемо обидві частини в квадрат і отримаємо
ve 2 * [x 2 + y 2] = vp 2 * [x 2 + (y + b) 2]
(Ve 2 - vp 2) * x 2 + (ve 2 - vp 2) * y 2 - 2 * b * vp 2 * y = b 2 * vp 2
Розділимо це вираження на (ve 2 - vp 2) згрупуємо. Отримаємо наступне:
x 2 + (y - b * vp 2 / (ve 2 - vp 2)) 2 = (ve * vp * b) 2 / (ve 2 - vp 2) 2
Це і є рівняння кола, що й потрібно було довести.
Окружність Аполону і крапка Аполону є дуже важливі об'єкти, які найбільше серйозне застосування в теорії переслідування на площині. З їх допомогою можна оцінювати різні величини, що характеризують процес переслідування і отримувати траєкторії руху гравців. Наведемо на підтвердження декілька маленьких теорем.
Теорема 1: Нехай тікає гравець і переслідувач переміщуються по своїх півпрямі. Їх положення залежить від часу. Позначимо його через P (t), E (t) тоді будь-який відрізок [P (t), E (t)] паралельний відрізку [P (0), E (0)]. На малюнку внизу ці відрізки виділені:
Теорема 2: Нехай тікає гравець рухається по прямій перетинає коло Аполону в точці М, рух починається з точки Е зі швидкістю V. Тоді переслідувач не може зустрітися з втікаючим раніше ніж за час рівне | EM | / V
Значення цієї теореми важко переоцінити, оскільки вона стверджує, що окружність Аполону - це геометричне місце точок у яких відбувається гарантована зустріч при оптимальному поведінці обох гравців. Не раніше і не пізніше. А так як оптимальний час переслідування одна з головних цілей аналізу теорії, то стає зрозумілим, чому потрібно вміти будувати окружність Аполону
3 Стратегія паралельного зближення
А тепер розглянемо приклад стратегії гонитви. Мета стратегії паралельного зближення полягає в тому, щоб забезпечити переслідувачу максимальне зближення з втікаючим гравцем. Нижче на картинці показані можливі траєкторії переслідувача і тікає гравця при використанні стратегії паралельного переслідування.
Зверніть увагу, що відрізки з'єднують точки, в яких відбулася зміна напрямку руху, паралельні один одному. Цей факт і дав назву стратегії.
Чому саме так. Розглянемо який-небудь ділянку руху на якому обидва учасники погоні рухаються по прямих. Їх поведінка оптимально, це означає, що вони рухаються до точки зустрічі розташованої на відповідній окружності Аполону (позначимо її А1) і це означає (див. вище), що будь-які два відрізки з'єднують положення тікає і наздоганяючого паралельні.
Нехай тепер тікає гравець змінив напрям. Інакше кажучи він перейшов до іншої окружності Аполону (позначимо її А2). Нехай А точка в якій змінив напрям тікає гравець і В точка в якій змінив напрям наздоганяє гравець. Тоді відрізок АВ кінець шляху по траєкторії на А1 і початок шляху по траєкторії А2. Отже будь-який відрізок на траєкторії А1 паралельний АВ і в той же час будь-який відрізок на траєкторії А2 також паралельний АВ. Таким чином, паралельність відрізків з'єднують відповідні точки на траєкторії тікає і наздоганяючого гравців зберігаються і при зміні напрямку руху.
Один кролик і кілька лисиць
Згадаймо завдання з якої почалася робота. Один кролик намагається втекти від групи лисиць. Відомо, що кролик бігає швидше лисиць. Ситуація в якій всі лисиці знаходяться в одній півплощині від кролика можна вважати нецікавою. Його швидкість вище і він неодмінно втече. Якийсь шанс у лисиць з'являється, якщо їм будь-яким чином вдасться кролика оточити. Ось так:
Звичайно, сам по собі факт оточення кролика успіху лисицям не гарантує. Цілком очевидно, що потрібно ще щось. Потрібно мабуть якесь спеціальне відношення відстаней, ставлення швидкостей. Загалом, між різними факторами утворюють ситуацію, необхідна якась закономірність.
Основою, відомого нам, математичного апарату є коло Аполону, але як ми пам'ятаємо з попередньої лекції вона будувалася з тих міркування, що переслідувач швидше тікає, інакше безліч точок зустрічі просто пусте. Тому на перший погляд використовувати окружність Аполону не вийде.
Проведемо невелике формальне перетворення. Нехай кролик буде переслідувачем, а лисиця втікаючим, а щоб цю нову задачу звести до попередньої додамо в умову, що всі напрямки руху від кролика для лисиці заборонені і рухатися вона може тільки до кролика, а кролику дозволено рух тільки по прямій з вихідної точки. З точки зору здорового глузду така постановка абсурдна, але як математики, ми маємо право так вчинити. Нова завдання буде виглядати так: Кілька лис оточили кролика який намагається зловити хоча б одну. Лисиці не заперечують і ведуть себе так, щоб максимально полегшити завдання кролика. Питання, за яких умов на будь-якому напрямку руху кролика по прямій, лисиці зможуть здійснити зустріч кролика хоча б з однією лисицею.
У такій постановці відповідь майже очевидний. Кролик гарантовано зустрінеться з хоча б однієї лисицею, якщо будь-яка пряма по якій він рухається перетне хоча одну окружність Аполону. Тобто має місце наступна ситуація:
Малюнок зроблений з урахуванням того, що швидкості лис можуть бути різні, відмінність у швидкостях лис визначає відмінність в радіусах. Сукупність кіл Аполону обмежують замкнуту внутрішню область в якій розташовується кролик.
Щоб склалася така ситуація необхідно якесь співвідношення між швидкостями лис, кролика і відстанями між ними. А для того, щоб отримати можливість що-небудь вважати нам потрібен радіус кола Аполону.
Радіус кола Аполону:
Для того щоб отримати радіус побудуємо формулу описує коло.
Позначення:
P - Переслідувач
E - Тікай гравець
O - Центр окружності Аполону
M - Точка зустрічі
Виберемо систему координат таким чином, щоб її початок був в центрі кола Аполону і E = (0,0); P = (0, - b)
Очевидно, що | EM | / V e = | PM | / V p
Або, що теж саме | EM | * V p = | PM | * V e
Тоді | EM | = Ö x 2 + y 2 і | PM | = Ö x 2 + (y + b) 2
Підставимо у попередню формулу і отримаємо
V p Ö x 2 + y 2 = V e Ö x 2 + (y + b) 2
Зведемо в квадрат обидві частини рівняння, згрупуємо і отримаємо наступне рівняння
x 2 + (y - (bV e 2) / (V p 2 - V e 2)) 2 = (V e V p b / (V p 2 - V e 2)) 2
Це дійсно рівняння кола і звідси ми можемо отримати вираз для радіуса.
R = V e V p b / (V p 2 - V e 2)
З цього ж рівняння можна визначити і координати переслідувача і тікає гравця
Знання цих величин, і швидкостей дозволяє вирішити цілий ряд завдань. Наприклад наступну:
Три лисиці оточили кролика таким чином, що кролик опинився в центрі кола описаної біля рівностороннього трикутника, в вершинах якого перебувають лисиці. Відомо також, що швидкості всіх лисиць однакові і відомо, що кролику не вдасться втекти, причому, якщо б його швидкість була хоча б трохи більше він би втік. Знайти відношення швидкості лисиць і швидкості кролика.
4. Переслідування на площині з одним переслідувачем
В даній грі існує оптимальна стратегія і для переслідувача і для тікає гравця. Оптимальною стратегією для переслідувача буде стратегія паралельного зближення, а для тікає гравця рух по прямій EA де Е початкова точка тікає гравця і А точка Аполону.
Оптимальність стратегії для тікає очевидна, так як початкова точка переслідувача знаходиться на тій же самій прямій. Дійсно суть стратегії паралельного зближення в тому, що
А) Переслідувач змінює напрямок руху в той же самий момент коли напрямок руху змінює тікає гравець.
Б) Новий напрямок вибирається таким чином, щоб переслідувач і тікає гравець зустрілися на колі Аполону.
З цих двох пунктів і слід оптимальність вибраної стратегії. А тепер визначимо оптимальний час переслідування для такої гри.
Відомо, що точка зустрічі - це точка Аполону. Відомо, також що обидва гравці рухаються по прямій, отже, для визначення часу зустрічі суттєво важливі не абсолютні значення швидкостей, а то наскільки швидкість переслідувача більше швидкості тікає гравця. Тому ми можемо перейти до еквівалентної задачі, в якій тікає гравець стоїть на місці, а переслідувач рухається зі швидкістю одно V p - V e
У цьому завданні переслідувач повинен пройти відстань між його початковим становищем і початковим становищем тікає. Ми вже позначали це відстань через b тоді оптимальний час переслідування буде дано наступним виразом t = b / (V p - V e).
5 Гра з лінією життя
Згадаймо, що грою з лінією життя називається гра з кордоном яку тікає гравець прагне досягти, а переслідувач навпаки прагне цього не допустити. Відразу з визначення випливає наступна нескладна теорема:
Теорема: У грі з лінією життя втікання неможливо тільки в тому випадку, коли лінія життя не перетинається з окружністю Аполону. При цьому форма лінії життя несуттєва.
Теорема очевидна і у доведенні не потребує.
Завдання «про щура загнаної в кут»
З назви вже ясно, що мова йде про гру в якій беруть участь два гравці діючих всередині деякого кута. Ця гра не досліджена вичерпно. Добре відомі тільки деякі окремі випадки, наприклад переслідування в прямому куті.
Теорема. Нехай тікає гравець знаходиться у вершині кута а переслідувач на бісектрисі
Позначимо швидкість тікає гравця через V e тоді, якщо швидкість переслідувача V p = Ö 2 V e, то оптимальний час переслідування t = b / V e
Доказ. Очевидно, що оптимальною стратегією для тікає гравця (щури) буде втеча з катету. Відношення катетів | Pb | та | Eb | одно Ö 2. Тобто дорівнює відношенню їх швидкостей.
Лев і людина
Нехай два гравці (лев і людина) знаходяться всередині круглої арени і їх швидкості рівні. На головне питання «Які їх шанси?» Є однозначна відповідь, людина за будь-яких початкових умовах зможе втекти. Спробуємо довести це твердження.
Синій гурток - це переслідувач і зелений кружок це тікає гравець. Для початку виконаємо невеликий якісний аналіз. Проведемо через переслідувача і тікає пряму лінію і перпендикуляр до неї. Нехай тікає гравець рухається по перпендикуляру якийсь час. Побудуємо трикутник на точках (Лев, Людина, Точка перетину відрізка по якому рухається людина з колом). Цей трикутник тупоугольние і тупий кут при вершині, в якій знаходиться людина. Це випливає з того, що початкове положення Льва і Людини - це єдине положення, коли даний кут дорівнює 90 градусів, гострим цей кут бути не може, отже, він тупий.
Отже ми з'ясували, що в момент початку руху кут при вершині людина збільшується, ми не можемо сказати наскільки, але сам факт не викликає сумніву.
Далі, людина, звичайно ж, не зможе рухатися по даному відрізку нескінченно (попереду стінка огорожі). Тому він повинен повернути на інший відрізок (послідовність відрізків показана на кресленні). Ми цілком можемо момент повороту прийняти за початковий момент руху. Отже, нехай це буде початковий момент, але вище було сказано, що в початковий момент руху кут у вершині Людина збільшується, отже, якщо він був тупим, він стане ще більш тупим.
При кожному повороті ми маємо наступний тупоугольние трикутник
Якщо як уже було сказано, кут при вершині Людина при кожному повороті збільшується, то в межі трикутник має скластися в відрізок.
А за умовою їх швидкості рівні. Природно, що перебуваючи в точності позаду людини, Лев не має жодних шансів його зловити. Єдине, що потрібно людині це правильно визначити послідовність моментів часу в які необхідно здійснювати поворот. Спробуємо зробити це.
Суворе доказ. Позначимо через «а» відстань від точки Людина до точки перетинання відрізка побудованого вказаним вище способом з колом. А через t i тимчасові точки в яких людина буде здійснювати поворот. Нехай ці моменти часу обчислюються наступним чином:
t i = (1 / v) * (a / 2 + a / 3 + .... + a / i) = (a / v) * (1 / 2 + 1 / 3 + ... .. 1 / i)
Таким чином, наша теорема справедлива, якщо отриманий числовий ряд не сходиться. Покажемо, що це дійсно так.
Нехай i = 2 k.
Тоді маємо наступне
(1 / 2 + 1 / 3 + 1 / 4 + 1 / 5 + 1 / 6 + 1 / 7 + 1 / 8 ... 1 / (2 k -1 +1) + .... + 1 / 2 k)>
(1 / 2 + 1 / 4 + 1 / 4 + 1 / 8 +1 / 8 +1 / 8 +1 / 8 + ... 1 / 2 k + ... +1 / 2 k) = k / 2
Звідси випливає, що при до прагнуть до нескінченності час також прагне до нескінченності, що і вимагалося довести.
До речі з цього ж випливає, що хоча лев і не може наздогнати людини, але він може наблизитися до людини як завгодно близько. Це випливає з того міркування, що в момент повороту людина розвертається у бік лева. Може здатися дивним, що нескінченно велику кількість розворотів не дає можливість леву зловити людини. Пояснюється це дуже просто. Кут розвороту щоразу зменшується.
Висновок
В процесі виконання дослідження були розглянуті різні ігри на переслідування і були проаналізовані алгоритми пошуку шляху. В ході роботи була показана взаємозв'язок між іграми на переслідування і окружністю Аполону, що дозволяє деякі завдання ігор на переслідування вирішувати методами, що не виходять за рамки шкільної математики, хоча в основному дані ігри вирішуються методами теорії диференціальних рівнянь.
Список використаних джерел
Гервер М.Л., Про лисицю і собаку / / Квант № 2, 1973, с. 39-44.
Гервер М.Л., Собака біжить напереріз / / Квант № 3, 1973, с. 15-18.
Петросян Л.А., Переслідування на площині / / Петросян Л.А., Ріхсеев Б.Б., - М.: Наука. Гол. ред. фіз.-мат. лит., 1991. - 96 с. - (Попул. лекції з мат.; Вип. 61)