Перечень условных обозначений 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 Заключение
Литература
Купить

В данной работе рассматриваются один из частных случаев задачи поиска на графах — игра «полицейские и грабитель». Здесь и далее вместо «полицейские и грабитель» будет использоваться англоязычное сокращение 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] содержится более полный список модификаций игры, а также описания их правил и для некоторых из них доказываются содержательные теоремы (в частности там доказывается несколько утверждений про игру с быстрым грабителем).
В данной работе будет рассматриваться наиболее простая вариация игры — простая C&Д-игра.
В этой работе для простой C&Д-игры строятся некоторые эмпирические алгоритмы («потенциальный алгоритм») для уклонения и поимки грабителя («сопряженный алгоритм»), а также для них даются некоторые числовые характеристики («эмпирическое полицейское число»).
Построенный в работе «потенциальный алгоритм» не является универсальным решением задачи, однако, оп может оказаться пригодным в некоторых частных случаях. В частности, в работе показывается работоспособность алгоритма в наиболее простых случаях: циклы, деревья, сетки, графы с некоторыми другими характеристиками вершин и минимальных циклов, и т.п. В работе также численными методами строятся некоторые статистики для случайно сгенерированных графов.
В рамках работы разработано приложение, моделирующее поведение полицейских и грабителей. Приложение состоит из трёх частей: основной модуль — game.js (программа, написанная па языке JavaScript), и два фроптепда: веб-страничка index.html, используемая для наглядной визуализации игры, и модуль для запуска программы в консольном режиме ng. js.
Полицейские и грабитель. Игра на графах.
При запуске в визуальном режиме программа генерирует граф (либо случайный, либо один из выбранных частных случаев) и даёт возможность пользователю делать ходы за полицейского. Ходы за грабителя делаются по упомянутому выше потенциальному алгоритму. У пользователя есть возможность тестировать «двойственный алгоритм» полицейских, нажимая кнопку «автоход».
В консольном режиме программа запускается посредством утилиты node.js. Консольный режим используется для построения статистик численным методом (т.е. для запуска большого количества игр на случайно сгенерированных графах и подведения статистик).

Купить