1 Перечень условных обозначений 2
2 Введение 4
2.1 Мотивация 8
2.2 Правила игры и постановка задачи 9
3 Некоторые факты о полицейском числе 11
4 Построение алгоритмов уклонения 13
4.1 Простейшее уклонение методом потенциалов 13
4.2 Улучшение алгоритма для некоторых частных случаев ... 18
4.3 Сопряженный алгоритм (для полицейских) 20
5 Моделирование C&R на JavaScript 22
5.1 Визуальное моделирование 22
5.2 Консольное приложение 24
6 Оценка эффективности пар алгоритмов с помощью эмпи­рического полицейского числа 27
7 Заключение 32
Список литературы 33
Купить

В данной работе рассматриваются один из частных случаев задачи по­иска на графах — игра «полицейские и грабитель». Здесь и далее вместо «полицейские и грабитель» будет использоваться англоязычное сокра­щение C&R (cops and robber).
Впервые определение игры C&R было дано в работе Winkler & Nowakowski [NW83], там рассматривался только случай с одним полицейским, и неза­висимо Alain Quilliot.
В наиболее общем случае C&R можно описать как класс пошаговых игр на графах, в которых два игрока в каждый момент времени зани­мают некоторое множество вершин своими фишками, и один из двух игроков (играющий за полицейских) своими ходами (передвижениями фишек) «преследует» другого (грабителя) и пытается его «поймать». Количество фишек игроков, их начальная растановка, процесс пресле­дования, правила захвата грабителя и прочее зависит от конкретных правил игры.
Наиболее распространённые правила (и в то же время наиболее про­стые) можно кратко описать так:
у грабителя 1 фишка, у полицейских — несколько. В начале игры игроки расставляют свои фишки в выбранные ими вершины и далее по очереди передвигают их вдоль рёбер графа, пока грабитель не будет пойман. Если игра не заканчивается за конечное количество ходов, то победа присуждается грабителю. Для избежания путаницы с другими возможными правилами, эта вариация игры называется в работе про­стой C &Я-игрой.
Кроме простой C&R-ugpbi существует довольно много её разновид­ностей, однако большинство из них лишь немного дополняют её правила. Вот некоторые примеры модификаций игры C&R:
1. Игра с «быстрыми» грабителями и/или полицейскими (т.е. игрок может передвигать свои фишки вдоль нескольких рёбер за один ход)
2. Игра с неполной информацией (полицейские и грабитель имеют определённый «радиус видимости»)
3. Игра с «радиусом захвата» (полицейские захватывают грабителя па растояпии)
4. «Стреляющий» грабитель (и/или полицейские)
В статье [XS14] содержится более полный список модификаций иг­ры, а также описания их правил и для некоторых из них доказывают­ся содержательные теоремы (в частности там доказывается несколько утверждений про игру с быстрым грабителем).
Рис. 1: Пример C&Д-игры с двумя полицейскими и одним грабителем па случайно сгенерированном связном пеориептироваппом графе.
В данной работе будет рассматриваться наиболее простая вариация игры — простая C&Д-игра.
В этой работе для простой C&Д-игры строятся некоторые эмпириче­ские алгоритмы («потспциальпый алгоритм») для уклонения и поимки грабителя («сопряженный алгоритм»), а также для них даются некото­рые числовые характеристики («эмпирическое полицейское число»).
Построенный в работе «потспциальпый алгоритм» не является уни­версальным решением задачи, однако, он может оказаться пригодным в некоторых частных случаях. В частности, в работе показывается рабо­тоспособность алгоритма в наиболее простых случаях: циклы, деревья, сетки, графы с некоторыми другими характеристиками вершин и мини­мальных циклов, и т.п. В работе также численными методами строятся некоторые статистики для случайно сгенерированных графов.
В рамках работы разработано приложение, моделирующее поведение полицейских и грабителей. Приложение состоит из трёх частей: основ­ной модуль — game.js (программа, написанная па языке JavaScript), и два фроптепда: веб-страничка index.html, используемая для наглядной визуализации игры, и модуль для запуска программы в консольном ре­жиме ng. js.
Рис. 2: Пример работы программы: визуализация C&R на тессеракте.
При запуске в визуальном режиме программа генерирует граф (либо случайный, либо один из выбранных частных случаев) и даёт возмож­ность пользователю делать ходы за полицейского. Ходы за грабителя делаются по упомянутому выше потенциальному алгоритму. У пользо­вателя есть возможность тестировать «двойственный алгоритм» поли­цейских, нажимая кнопку «автоход».
В консольном режиме программа запускается посредством утилиты node.js. Консольный режим используется для построения статистик чис­ленным методом (т.е. для запуска большого количества игр на случайно сгенерированных графах и подведения статистик).
2.1 Мотивация
На данный момент существуют точные алгоритмы для поимки грабите­ля в C&Д-игре лишь в некоторых частных случаях. Так, например, в [NW83] рассматривается случай одного полицейского и строится необ­ходимое и достаточное условие существования алгоритма для поимки грабителя (которое даёт ключ к построению алгоритма).
В работе [AF84] рассматривается способ поимки грабителя двумя по­лицейскими с помощью контроля каждым из полицейских одного наи­кратчайшего пути (на графах, на которых это возможно). Так, напри­мер, в случае сетки достаточно двух полицейских: один контролирует строку, другой — столбец. Поочерёдно сдвигая контролируемые столбцы и строки, грабитель прижимается в угол и там захватывается.
Однако, способ предлагаемый в [AF84] не может быть использован в общем случае. Столкнувшись с задачей C&R-игр, мне в первую очередь стало интересно, как могли бы выглядеть алгоритмы уклонения или по­имки грабителя, работающие пусть и не точно, но в какой-то степени эффективно на произвольных графах и с произвольным количеством полицейских.
В этой работе строятся эмпирические алгоритмы для построения стра­тегий поимки и уклонения грабителем.
2.2 Правила игры и постановка задачи
Как уже упоминалось в введении, существует огромное множество вари­аций игры «полицейские и грабитель». Дадим детальное описание наи­более простой вариации:
Определение 1. Простая C&Я-игра.
Пусть, дан связный неориентированный граф G = G(V,E), где V — множество вершин графа, a E — множество его рёбер. В игре два участ­ника. Первый из них играет за полицейских, второй — за грабителя. Для краткости в некоторых случаях для обозначения игроков будут исполь­зоваться сокращения C (cops — полицейские), R (robber — грабитель). У C имеется k фишек, а у R — одна (число фишек у каждого из игроков в течение игры не меняется). От начала и до конца игры оба игрока полно­стью видят текущее состояние игры, т.е. это игра с полной информацией. Игроки делают ходы по очереди.
В первый ход, основываясь только на графе G, C расставляет свои фишки C = (ci,..., ck), тдр с-1, ...,ck 2 V в произвольные вершины графа.
Во второй ход, основываясь на графе G и расположении фишек сопер­ника, R выбирает произвольную вершину r 2 V для своей фишки. Во все последующие ходы игроки двигают свои фишки вдоль рёбер графа. За свой ход C может подвинуть все свои фишки, a r только свою единствен­ную. Допустимым также считается оставить одну или несколько фишек на месте. Две или более фишек C могут занимать одну и ту же вершину. Игра заканчивается в момент, когда хотя бы одна из а оказывается рав­ной г, т.е. когда один из полицейских оказывается на той же вершине, что и грабитель. Если грабитель был пойман, то победа присуждается полицейским. Если игра не заканчивается за конечное количество ходов, то победа присуждается грабителю.
Определение 2. Стратегия, Sr для, R есть пара (IR, aR) где IR 2 V начальная позиция грабителя, и aR : Vk х V ! V — функция, которая сопоставляет новую позицию грабителя г’ каждой конфигурации игры S = (ci,...,cfc,r) 2 Vk х V.
Определение 3. Стратегия для, C — есть пара SC = (IC,aC), где IC 2 Vk начальные позиции k полицейских, и aC : Vk х V ! Vk функция, ко­торая сопоставляет новые позиции полицейских (c/1,...,c/k) каждой кон­фигурации игры S = (c1,..., ck, r) 2 Vk х V
Определение 4. Полицейское число (сор number) cn(G) связного графа есть минимальное количество полицейских необходимое для достовер­ной поимки R в независимости от поведения R Полицейским числом несвязного графа будем называть сумму полицейских чисел его компо­нент связности.
Заметим, что полицейское число является характеристикой графа и не зависит от стратегий игроков.
В данной работе ставится задача построения алгоритмов уклонения для грабителя при cn(G) > |C|.
Купить