Заказать работу


Тип работы:
Предмет:
Язык работы:


Моделирование уклонения в задаче поиска на графе

Работа №61248
Тип работыДипломные работы, ВКР
Предметматематика
Объем работы35
Год сдачи2016
Стоимость4210 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 124
Не подходит работа?

Узнай цену на написание

Перечень условных обозначений 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. Консольный режим используется для построения статистик численным методом (т.е. для запуска большого количества игр на случайно сгенерированных графах и подведения статистик).


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!


Результатом данной работы стали пара алгоритмов для грабителя и полицейских. Алгоритмы были протестированы для многомерных графов- сеток. Кроме того, был указан способ «бесплатного» построения алгоритма для полицейских, в случае наличия функции оценки позиции для грабителя (в частности, в случае наличия потенциального алгоритма). В работе вводится понятие «эмпирического полицейского числа», позволяющее давать оценку относительной эффективности пар алгоритмов (или стратегий), что продемонстрированно на примере пар потенциального и дуального алгоритмов.
Другим результатом работы стало приложение, предоставляющее удобный пользовательский и программный интерфейс для экспериментов, связанных с C&R(а также удобный способ демонстрации). Данное приложение публикуется вместе с этой работой.
Построенные в данной работе программные средства и алгоритмы нельзя воспринимать как конечную цель. Автор видит широкие возможности для дальнейшей работы. Так использованный в процессе построения статистик алгоритм содержит большое количество эмпирических параметров. Эти эмпирические параметры, возможно, имеет смысл находить генетическим алгоритмом или с помощью нейронных сетей. Кроме того, в работе построены только самые простые статистики, в то время как потенциал программы позволяет строить множество «тонких» статистик.



[AF84] Martin Aigner and Michael Fromme. A game of cops and robbers, Discrete Appl. Math. 8 (1984), no. 1, 1-11.
MR 739593 (85f:90124)
[BB12] William Baird, Anthony Bonato MeynieTs conjecture on the cop number: a survey, Journal of Combinatorics Volume 0, Number 0 (2012), 1-8
[Fra87a] Peter Frankl Cops and robbers in graphs with large girth and cayley graphs, Discrete Applied Mathematics, 17 (1987), 301-305.
[NS14] Nicolas Nisse. Algorithmic Complexity Between Structure and Knowledge.How Pursuit-evasion Games help, HDR Univ. Nice Sophia Antipolis, CNRS, I3S, UMR 7271, Sophia Antipolis, France, (May 26th 2014), 1-43
[NW83] Richard J. Nowakowski and Peter Winkler. Vertex-to-vertex pursuit in a graph. Discrete Mathematics, 43 (1983), 235-239.
[SchOl] Bernd S. W. Schroder The copnumber of a graph is bounded by |_3genus(g) + 3_|, Categorical perspectives, Trends in Mathematics (2001), 243-263


Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!


Подобные работы


© 2008-2021 Cервис помощи студентам в выполнении работ
.