Одна динамическая игра управления агентами в сети

Тимонин Николай Олегович

Одна динамическая игра управления агентами в сети

В работе рассматривается новая постановка некооперативной многошаговой игры управления агентами в сети. Сетевая структура описывается графом, где вершинами являются агенты, а ребра определены как устойчивые связи между агентами. Функция выигрыша каждого зависит от диаметра подграфа, определенного на вершинах, принадлежащих игроку. Диаметром графа является длина кратчайшего пути между двумя наиболее удаленными друг от друга вершинами. Как следствие диаметр графа может быть использован для оценки максимального времени, требующегося для доставки пакета информации от одного агента к другому. Каждый игрок имеет в своем распоряжении подвижного агента, который может быть расположен в любой допустимой позиции для образования нового подграфа. Целью каждого игрока является уменьшение диаметра результирующего расширенного подграфа. Актуальность данного подхода определяется практической значимостью рассмотренной задачи в приложениях, связанных с самоорганизующимися мобильными сетями (MANET).

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36465f1be77c40d58b3f

UUID: abc0255e-5365-47d2-b317-a6a5fb887d78

Язык: Русский

Опубликовано: почти 8 лет назад

Просмотры: 5

Тимонин Николай Олегович

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 680943 bytes

Поделиться работой

Санкт-Петербургский государственный университет Кафедра математической теории игр и статистических решений Тимонин Николай Олегович Выпускная квалификационная работа бакалавра Одна динамическая игра управления агентами в сети Направление 010400 Прикладная математика и информатика Научный руководитель, кандидат физ.-мат. наук, доцент Громова Екатерина Викторовна Санкт-Петербург 2016

Содержание Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . Обзор литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . Глава 1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . 1.1 Многошаговая игра с полной информацией . . . . . . . . . 1.2 Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . Глава 2. Постановка игры управления агентами в сети . . . . . . . 2.1 Общая сетевая структура . . . . . . . . . . . . . . . . . . . 2.2 Подвижный агент: дрон . . . . . . . . . . . . . . . . . . . . 2.3 Альтернативы и выигрыши . . . . . . . . . . . . . . . . . . 2.4 Пример игры . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Условие существования равновесия по Нэшу . . . . . . . . Глава 3. Описание программного обеспечения . . . . . . . . . . . . 3.1 Постановка задачи для программного обеспечения . . . . . 3.2 Обоснование подхода к решению задачи . . . . . . . . . . . 3.3 Описание архитектуры программы . . . . . . . . . . . . . . Глава 4. Тестирование программы на примере игры двух лиц . . . 4.1 Постановка игры . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Результат при условии, что первым «ходит» первый игрок 4.3 Результат при условии, что первым «ходит» второй игрок . 4.4 Вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . Приложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 . . . . . . . . . . . . . . . . . . . . . . . . 3 5 6 8 8 10 12 12 13 14 15 18 21 21 21 22 23 23 23 25 25 27 28 29

Введение В работе введена новая постановка некооперативной многошаговой игры управления агентами в сети. Сетевая структура описывается графом, где вершинами являются агенты, а ребра определены как устойчивые связи между агентами [1]. Выигрыш каждого игрока зависит от диаметра подграфа, определенного на вершинах, принадлежащих игроку. Диаметром графа является длина кратчайшего пути между двумя наиболее удаленными друг от друга вершинами. Диаметр графа используется для оценки максимального времени, требующегося для доставки пакета информации от одного агента к другому. В данной работе будем предполагать, что каждый каждый игрок имеет в своем распоряжении одного подвижного агента, который может быть расположен в любой допустимой позиции для образования нового подграфа. Целью каждого игрока является уменьшение диаметра результирующего расширенного подграфа. Актуальность данного подхода определяется практической значимостью рассмотренной задачи в приложениях, связанных с самоорганизующимися одноранговыми мобильными сетями (MANET) [2]. MANET - сеть, без заранее определенной структуры, которая состоит из набора беспроводных мобильных узлов или хостов (роль которых, в данной работе, берут на себя агенты игроков). Правильная организация сети MANET играет ключевую роль в таких задачах как восстановление связи в местах природных катастроф (землетрясений, наводнений и т. п.), координирование действий спасательных отрядов и т. д. Одной из самых важных проблем, связанных с построением данной сети, является разумное использование ограниченных ресурсов, таких как электромагнитный спектр частот радиоволн, время работы аккумуляторов и т. п. Неразумное использование этих ресурсов может привести к ухудшению производительности всей сети в целом. Большая часть исследований, проведенных с применением теории игр в области мобильных сетей, связано с обнаружения вредоносных или не приносящих пользу узлов. В данном же исследовании используется другой подход: рассматривается совместный сценарий поведения узлов для достижения максимальной выгоды. Основной особенностью данного типа сетей является возможность реорганизовывать структуру сети (топологию, пути передачи данных, распределение спектра и т. д.), основываясь на знаниях предыдущих этапов построения. Таким образом, с течением времени общая производительность сети (скорость доставки пакетов информации, расходы на доставку пакета и т. п.) будет расти. Все узлы сети имеют некоторую область взаимодействия с другими узлами. Таким образом, последовательность узлов может образовывать 3

канал (путь) для передачи данных. Большое количество промежуточных узлов в таком пути может отрицательно сказаться на скорости передачи данных. Или, в некоторых случаях, препятствия на пути (озера, обломки и т. п.) могут вызвать его разрыв. Одним из эффективных способов уменьшения нагрузки на канал или его восстановления является использование беспилотных летательных аппаратов - дронов. Предметом данного исследования является поиск наилучшего места для внедренных мобильных агентов (дронов). Под наилучшим местом понимается такое место, что помещение туда дрона приводит к увеличению производительности сети, а именно уменьшение длины канала передачи данных [3]. В данной задаче жестко ограничено число доступных беспилотных летательных аппаратов. В процессе самоорганизации сеть самостоятельно определяет оптимальное место для помещения в него подвижного узла. В итоге, две части одного маршрута, состоящие из промежуточных неподвижных узлов, будут соединены между собой беспилотником. Так как сеть MANET предполагает динамическую топологию: в каждый момент времени сеть самостоятельно определят как использовать беспилотник наилучшим образом, было принято решение, в качестве инструмента исследования, применять теорию позиционных игр [4], [5]. Особенностью данного класса игр является учет динамики конфликтно - управляемого процесса. Класс конечношаговых игр с полной информацией является одним из классов позиционных игр. Данный класс игр теоретически позволяет построить граф игры, наглядно демонстрирующий поведение игроков в конкретных ситуациях. Для класса конечношаговых игр вводится понятие абсолютного равновесия по Нэшу, что является усилением понятия равновесия по Нэшу для игр в нормальной форме. 4

Постановка задачи В данной выпускной квалификационной работе была предложена новая постановка некооперативной многошаговой игры. Необходимо было решить следующие задачи: 1. исследовать данную игру с применением методов теории позиционных игр; 2. построить дерево решений и сформулировать условие существования абсолютного равновесия по Нэшу; 3. написать программное обеспечение, позволяющее исследовать данную игру; 4. протестировать программный продукт на примере игры двух лиц. 5

Обзор литературы При написани работы была использована литература: 1. Новиков Д. А. Игры и сети. Математическая теория игр и её приложения. В данной статье описаны общие положения и структура современных направлений в играх на сетях. Введена система классификации игр на сетях с точки зрения теории игр и теории графов. Приведены общие положения теории сетевых игр. Изложение материала построено таким образом, чтобы обеспечить целостное представление об играх на сетях. При написании работы использовались материалы из раздела 2 (Игры на сетях) и 3 (Задача управления). 2. Петросян Л. А., Седаков А. А. Многошаговые сетевые игры с полной информацией. В статье рассматриваются многошаговые сетевые игры с полной информацией, в которых в каждый момент игры задается сетевая структура, соединяющая игроков. Демонстрируется метод нахождения оптимального поведения игроков. 3. Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр. В этой книге описаны общие положения математической теории игр как составной части исследования операций. Изложение материала построено таким образом, что понятие модели конфликта (игры) развивается от простой (матричные игры) до наиболее сложной (дифференциальные игры). Во всех главах имеется большое количество примеров, иллюстрирующих основные положения теории. В частности, подробно описана теория многошаговых игр с полной информацией. При написании работы использовались материалы из гл. 4 (Позиционные игры). 4. Wilson R. J. Introduction to Graph Theory. Данная книга является вводным курсом в теорию графов, но вместе с тем затрагивает ряд интересных и сложных задач. Полезна для решения прикладных задач теории графов. При написании работы использовалась для описания взаимодействия между агентами игрока с точки зрения теории графов. 5. Yu F. R. Cognitive Radio Mobile Ad Hoc Networks. В данной книге подробно описаны технологии MANET сетей. Описаны общие принципы построения сетей и дальнейшее изменения их структуры для увеличения производительности сетей. При написании работы книга использовалась как дополнение к описанной выше литературе 6

при построении общей архитектуры сети, описания поведения подвижных агентов и методов взаимодействия агентов, как узлов сети. 6. Zhu Han and Dusit Niyato and Walid Saad and Tamer Başar and Are Hjørungnes. Game Theory in Wireless and Communication Networks. Данная книга позволяет получить общее представление о теории игр, её использование в построении безпроводных коммуникаций и решение проблем, связанных с построением сетей. В частности, описаны 3G сети, LAN, сенсорные и самоорганизующиеся сети. Также материал книги покрывает техническое моделирование, построение архитектуры и анализ сетей с применением теории игр. 7. Dijkstra E. W. A note on two problems in connexion with graphs. В данной статье описан алгоритм, позволяющий находить кратчайшие пути от одной вершины графа, до всех остальных. 7

Глава 1. Основные понятия 1.1 Многошаговая игра с полной информацией Многошаговая игра с полной информацией определяется на древовидном конечном графе G = (X, F ), где X - некоторое конечное множество, а F - отображение из X в X - некоторое правило, которое каждому элементу x ∈ X ставит в соответствие некоторое множество Fx ⊂ X. В частности, возможна ситуация когда Fx = ∅. Элементы множества X будем изображать точками на плоскости. Пары точек x и y, для которых выполняется y ∈ Fx , будем соединять непрерывной линией со стрелкой, направленной от x к y. В дальнейшем, каждый элемент из X будем называть вершиной (узлом) графа, а пару элементов (x, y), для которой y ∈ Fx - дугой графа. Вершины x и y для дуги p = (x, y) являются граничными вершинами, где x - начало, а y - конец дуги. Различные дуги, имеющие общую граничную точку, будем называть смежными. Все множество дуг в графе будем обозначать P . Путем в графе G = (X, F ) будем называть такую последовательность p = (p1 , p2 , . . . , pk , . . . ) дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей. Длина пути p = (p1 , . . . , ps ) - число l(p) = s дуг последовательности. Под ребром графа G = (X, F ) будем понимать множество из двух элементов x, y ∈ X, для которых выполняется (x, y) ∈ P , или (y, x) ∈ P . Заметим, что в ребре ориентация роли не играет, в отличии от дуги. В дальнейшем ребра будем обозначать p, q, а все множество ребер - P . Цепью будем называть такую последовательность ребер (p1 , p2 , . . . ), в которой у каждого ребра pk одна из граничных вершин является также граничной для pk−1 , а другая - граничной для pk+1 . Циклом графа G = (X, F ) будем называть конечную цепь, начинающуюся и оканчивающуюся в одной и той же вершине. Древовидный граф - конечный связный граф без циклов, имеющий не менее двух вершин, в котором существует единственная вершина x0 , такая, что Fx0 = X. Данную вершину x0 будем называть начальной вершиной графа G. Подграфом Gz древовидного графа G = (X, F ), будем называть граф вида (Xz , Fz ), где z ∈ X и Xz = Fz , а Fz x = Fx ∩ Xz . Отображение Fz является сужением отображения F на множество Xz . Данный подгаф будем обозначать Gz = (Xz , Fz ). Далее перейдем к определению многошаговой игры на древовидном конечном графе. Разобьем множество вершин X на n + 1 подмножество X1 , . . . , Xn+1 , такое что 8

n+1 S Xi = X, Xk ∩ Xl = ∅, k 6= l, i=1 где Fx = ∅ для x ∈ Xn+1 . Множество Xi , i = 1, . . . , n является множеством очередности игрока i, а множество Xn+1 - множеством окончательных позиций. На множестве окончательных позиций Xn+1 определены n вещественных функций H1 (x), . . . , Hn (x), x ∈ Xn+1 , которые будем называть функциями выигрышей игроков. Далее опишем процесс игры. Имеется некоторое множество игроков N , пронумерованных натуральными числами. Если x0 ∈ Xi1 , тогда в вершине x0 «ходит» игрок i1 и выбирает вершину x1 ∈ Fx0 . Далее, если x1 ∈ Xi2 , то в вершине X1 «ходит» игрок i2 и выбирает следующую вершину x2 ∈ Fx1 . И так далее, если на k-ом шаге xk−1 ∈ Xik , то «ходит» игрок ik , выбирая следующую вершину из множества Fxk−1 . Игра заканчивается при достижении окончательных вершины xl ∈ Xn+1 , т. е. такой, для которой Fxl = ∅. Последовательный выбор вершин однозначно реализует последовательность x0 , . . . , xk , . . . , xl , определяющую путь в древовидном графе G, с началом в x0 и концом в одной из окончательных позиций игры. Этот путь будем называть партией. Так как граф G древовидный любая партия заканчивается в некоторой окончательной позиции xl и, наоборот, любая окончательная позиция xl однозначно определяет некоторую партию. В окончательной позиции xl каждый из игроков получает выигрыш. Игрок i при совершении выбора в вершине x ∈ Xi знает позицию x, а следовательно, из-за древовидности графа G может восстановить и все предыдущие позиции. В этом случае говорят, что игроки имеют полную информацию. Стратегией игрока i будем называть однозначное отображение ui , которое ставит в соответствие каждой вершине x ∈ Xi некоторую вершину y ∈ Fx . Таким образом, для любой позиции x из множества его очередности Xi , стратегия игрока i предписывает ему однозначный выбор следующей позиции. Ситуацией в игре будем называть упорядоченный набор u = (u1 , u2 , . . . , un ), ui ∈ Ui , где Ui - множество всевозможных стратегий игрока i. Множеством ситуаn Y ций в игре будем называть декартово произведение U = Ui . i=1 Заметим, что каждая ситуация u = (u1 , u2 , . . . , un ) в игре однозначно соответствует партии игры x0 , x1 , . . . , xl и, как следствие, однозначно определяет выигрыш каждого игрока Ki (u1 , u2 , . . . , un ) = Hi (xl ), i = 1, . . . , n. 9

Таким образом, значение выигрыша каждого игрока Ki в ситуации u равно значению выигрыша Hi в окончательной позиции партии x0 , x1 , . . . , xl , которая соответствует ситуации u = (u1 , u2 , . . . , un ). В итоге мы получили некоторую игру в нормальной форме Γ = (N, {Ui }i∈N , {Ki }i∈N ), где N - множество игроков, Ui - множество стратегий игрока i, Ki - функция выигрыша игрока i. Ситуацию u∗ = (u∗1 , u∗2 , . . . , u∗n ) будем называть равновесием по Нэшу, если выполняется неравенство: Ki (u∗1 , . . . , u∗i−1 , u∗i , u∗i+1 , . . . , u∗n ) ≥ Ki (u∗1 , . . . , u∗i−1 , ui , u∗i+1 , . . . , u∗n ), где ui ∈ Ui , i ∈ N Подыгрой Γz будем называть игру определенную на подграфе Gz = (Xz , F ), z ∈ X. Ей соответствует подыгра в нормальной форме Γz = (N, {Uiz }i∈N , {Kiz }i∈N ), где ui ∈ Ui , i ∈ N , а функции выигрыша Kiz , i = 1, . . . , n определены на n Y декартовом произведении U z = Uiz . i=1 Ситуацию равновесия по Нэшу основной игры u∗ = (u∗1 , u∗2 , . . . , u∗n ) будем называть абсолютным равновесием по Нэшу в игре Γ, если для любого z ∈ X ситуация (u∗ )z = ((u∗1 )z , (u∗2 )z , . . . , (u∗n )z ), где (u∗i )z - сужение стратегии u∗i на подигру Γz , является ситуацией равновесия по Нэшу в подигре Γz . 1.2 Алгоритм Дейкстры Данный алгоритм позволяет найти кратчайшие пути от некоторой вершины v графа G = (V, E) до всех остальных вершин этого графа [6]. Каждой вершине графа сопоставляется метка, означающая минимальное расстояние от v до этой вершины. Работа алгоритма выполняется пошагово: на каждом шаге берется одна вершина и выполняется попытка уменьшения значения метки. Алгоритм заканчивает свою работу после перебора всех вершин. 1. Начальное состояние. Значение метки самой вершины v устанавливается в 0, а значение меток других вершин - в бесконечность (что, по сути, отражает неизвестность расстояния от v до других вершин). Все вершины графа помечаются как нетронутые. 2. Шаг алгоритма. Если все вершины были взяты, алгоритм завершается. В противном случае, из множества не взятых вершин выбирается 10

вершина s, у которой минимальное значение метки. Рассматриваются всевозможные маршруты, для которых s является предпоследним пунктом. Вершины, к которым ведут ребра из s, будем называть соседями этой вершины. Для каждого не взятого соседа s рассмотрим новую длину пути, которая равна сумме значений текущей ветки s и длины ребра, соединяющего s с этим соседом. Если полученное значение длины меньше значения метки соседа, тогда заменим значение метки полученным значением длины. После рассмотрения всех соседей, пометим вершину s как взятую. Повторим шаг алгоритма. Недостаток данного алгоритма заключается том, что он будет некорректно работать если граф имеет дуги отрицательного веса. 11

Глава 2. Постановка игры управления агентами в сети 2.1 Общая сетевая структура Задано множество игроков N = {1, . . . , n}. Каждый игрок i имеет не пустое множество Mi агентов, расположенных в подпространстве W = {1, . . . , Wx } × {1, . . . , Wy } ⊂ R2 , т. е. в узлах целочисленной решетки, где Wx , Wy ∈ N . Возможно расположение агентов разных игроков в одном узле решетки. Позиция каждого агента описывается положительными координатами в ДПСК. Далее агентов будем обозначать точками на плоскости. Будем говорить, что между агентами vpi и vsi , s 6= p, игрока i установлена устойчивая связь (vpi , vsi ), если они находятся в соседних узлах целочисленной решетки. Связи будем обозначать на плоскости непрерывным отрезком, соединяющим точки (см. рис. 1). Рис. 1: Агенты и связи между ними Таким образом множество агентов (точек) vpi ∈ Mi , i = 1, . . . , n, и связей (отрезков) e = (vpi , vsi ), vpi ∈ Mi , vsi ∈ Mi , s 6= p, i = 1, . . . , n, определяет подграф Ri = (Vi , Ei ) ∈ R = (V, E), где V — не пустое конечное множество элементов, называемых вершинами (или точками), E — конечное множество неупорядоченных пар элементов из V , называемых ребрами (или линиями) [7]. Подграфом Ri графа R, будем называть граф, все вершины которого принадлежат V , а все ребра принадлежат E. n S Заметим, что Ri = R. Граф R определяет общую сетевую струкi=1 туру игры, в которой имеется Wx × Wy возможных позиций для агентов на сетке. Количество незанятых позиций агентами |O| может быть оценено 12

следующим образом Wx × Wy − (n1 + n2 + · · · + nN ) ≤ |O| ≤ Wx × Wy − max{ni } i∈N В дальнейшем, будем считать, что подграф Ri связный. Это гарантирует существование пути между любыми двумя его вершинами. Заметим отсутствие связей между элементами разных подграфов, т. е. неподвижные агенты одного игрока не взаимодействуют с неподвижными агентами других игроков в процессе передачи информации. Путем в подграфе Ri будем называть такую последовательность e = (e1 , . . . , ek , . . . ) ребер, что конец каждого предыдущего ребра совпадает с началом следующего. Длина пути e = (e1 , . . . , ek ) — число d(e) = k ребер последовательности. Очевидно, что длина каждого такого ребра равна единице. Диаметром подграфа D(Ri ) будем называть число ребер в кратчайшем простом незамкнутом пути между двумя наиболее удаленными друг от друга вершинами (см. рис. 2). D(Ri ) = max (vk ,vl )∈Vi ×Vi d(vk , vl ), где d(vk , vl ) - путь между вершинами vk и vl . Рис. 2: Диаметр подграфа Так как каждый подграф Ri связный, то его диаметр может быть ограничен следующим образом: √ 2(b Mi c − 1) ≤ D(Ri ) ≤ Mi − 1. 2.2 Подвижный агент: дрон В распоряжении каждого игрока имеется один подвижный агент. Подвижным агентом q i , i ∈ N , будем называть такого агента, положение которого на целочисленной решетке может изменяться в процессе игры, в то время как другие агенты имеют фиксированные положения (см. рис. 3). Связь подвижного агента с другим агентом определяется аналогично связи между неподвижными агентами. Подвижный агент может устанавливать 13

связи с любым подвижным агентом q i , i ∈ N , и с любыми неподвижными агентами vpi , p ∈ Mi , i ∈ N . Будем считать, что в начальный момент времени все дроны расположены в такой начальной позиции q o , что длина пути от них до любого подвижного агента больше единицы: d(q o , vpi ) > 1, p ∈ Mi , i ∈ N . Это условие гарантирует, что ни один дрон не может установить связь с ни с одним неподвижным агентом в начальной стадии игры. Рис. 3: Подвижный агент Подграф Ri∗ будем называть расширенными подграфом, где множество вершин: n S ∗ V (Ri ) = Mi ∪ q i , i = 1, . . . , n, i=1 а множество ребер определяется связями на множестве V (Ri∗ ) (см. рис. 4). Заметим возможность установления связи между расширенными подграфами, которая зависит от расположения подвижных агентов. 2.3 Альтернативы и выигрыши Каждый из игроков стремится так расположить своего подвижного агента, чтобы минимизировать диаметр на своем результирующем расширенном подграфе. Игроки ходят по очереди. На каждом шаге игрок i выбирает одни элемент из своего множества альтернатив Wi∗ . Под множеством альтернатив Wi∗ игрока i будем понимать все те возможные положения на целочисленной решетке для установления в них подвижного агента, которые дадут уменьшение диаметра расширенного подграфа игрока i по сравнению с текущим диаметром (или начальным диаметром, если это первый шаг). Это 14

Рис. 4: Расширенный подграф означает что на каждом шаге игрок рассматривает только те позиции для дрона, которые дадут ему уменьшение диаметра в сравнении с текущим его значением. Заметим, что множество альтернатив игрока i на каждом шаге зависит от его предыдущих ходов, и от предыдущих ходов других игроков. Таким образом, каждый игрок решает задачу следующего вида: q̄i = argminD(Ri ) qi ∈Wi∗ Будем считать, что игрок «помнит» свои предыдущие ходы и «знает» предыдущие ходы других игроков. Следовательно, данный процесс может быть сформулирован как многошаговая игра с полной информацией. Игра заканчивается когда ни один из игроков не может далее уменьшить диаметра своего расширенного подграфа. Функция выигрыша i-го игрока задается следующим образом: Hi = d(Ri ) − d(Ri∗ ) ≥ 0. 2.4 Пример игры Проиллюстрируем данную игру на примере. Игра Γ происходит на сетевой структуре, изображенной на рис. 5. Множество N состоит из двух игроков: N = {1, 2}. Агентов первого игрока будем изображать в виде заполненных кружков, а второго игрока — в виде квадратиков. Подвижного агента первого игрока будем изображать в виде крестика, а второго игрока — в виде кружка. Положение каждого агента задается двумя координатами в декартовой прямоугольной системе координат (ДПСК). Связи между агентами на рис. 5 изображены в виде линий, которые соединяют соответствующих агентов. Диаметр подграфа первого игрока d(R1 ) = 16, а второго — d(R2 ) = 16. 15

Рис. 5: Сетевая структура игры Рис. 6: Сетевая структура игры после хода первого игрока Первым «ходит» игрок 1. Ему выгодно перемещение подвижного агента в одну из позиций: (3, 5), (7, 3), так как в каждой из этих позиций он достигнет уменьшения диаметра своего подграфа. Пусть он перемещает своего подвижного агента в позицию (3, 5) (см. рис. 6). В результате диаметр образовавшегося расширенного подграфа d(R1∗ ) = 14, что дает ему уменьшение диаметра на две единицы. Далее «ходит» игрок 2. Одними из возможжных позиций для перемещения подвижного агента являются (4, 3), (7, 4), (7, 5). Пусть он перемещает своего подвижного агента в позицию (4, 3) (см. рис. 7). Тогда диаметр образовавшегося расширенного подграфа d(R2∗ ) = 12. Далее снова делает ход первый игрок. С учетом позиции подвижного агента второго игрока, он может расположить своего агента в одной из позиций: (3, 3), (7, 3). Пусть он перемещает своего агента в позицию (3, 3), в результате чего диаметр нового результирующего подграфа d(R1∗ ) = 10 16

Рис. 7: Сетевая структура игры после хода второго игрока Рис. 8: Конечная сетевая структура игры (см. рис. 8). Далее ни один из игроков не может уменьшить диаметр своего расширенного подграфа, и игра заканчивается с выигрышами H1 = 6 и H2 = 4. Данная проблема может быть сформулирована как многошаговая игра с полной информацией [4]. Граф G, частично иллюстрирующий дерево решений многошаговой игры, изображен на рис. 9, где элементы множества очередности первого игрока X1 изображены в виде кружков, а элементы множества очередности второго игрока X2 — в виде квадратиков. Позиции, входящие в множества X1 , X2 , пронумерованы двойными индексами, а дуги — одним индексом. Выигрыши игроков записаны в окончательных позициях. Первый игрок на первом шаге выбирает из двух альтернатив. Двойными индексами обозначены позиции дрона в ДПСК после хода игрока. В вершине (3, 5) второй игрок выбирает из трех альтернатив и т. д. 17

Рис. 9: Игра с полной информацией на древовидном графе G На данном дереве можем видеть две ситуации абсолютного равновесия по Нэшу [4] (u11 , u12 ) и (u21 , u22 ) при условии, что второй игрок выберет вершину (4, 3) вместо (7, 4) для левой ветки дерева решений ((3, 3) вместо (7, 4) для правой), не смотря на то, что в обеих вершинах он получает одинаковый выигрыш. Стратегии u11 = (1, 1), u12 = (2), u21 = (2, 1), u22 = (1) указывают в каждой вершине номер дуги, по которой следует двигаться дальше. 2.5 Условие существования равновесия по Нэшу Ситуация абсолютного равновесия по Нэшу существует в любой многошаговой игре с полной информацией на конечном древовидном графе G = (X, F ) [4]. Подчеркнем различие графов G и R = (V, E): граф R описывает сетевую структуру игры, а граф G - дерево дерево игры. Покажем, что в данной игре ситуация равновесия по Нэшу существует не всегда. Конечность древовидного графа означает, что каждый из игроков сделает конечное число шагов в игре. Таким образом, для гарантирования существования абсолютного равновесия по Нэшу в игре с полной информацией, мы должны гарантировать её конечность. Рассмотрим пример игры с отсутствием равновесия по Нэшу. Сетевая структура изображена на рис. 10. Множество игроков N = {1, 2}. Неподвижные агенты первого игрока изображены в виде виде заполненных кружков, а второго игрока — в виде квадратиков. Диаметр подграфа первого игрока d(R1 ) = 10 с началом в точке (1, 4) и концом в (7, 4), а второго — d(R2 ) = 15 с началом в (5,1) и концом в (7,4). Связи между агентами, находящимися в одинаковых координатах, отсутствуют. 18

Рис. 10: Сетевая структура игры с отсутствием равновесия по Нэшу 1. Шаг № 1. Делает ход первый игрок. Единственная позиция для подвижного агента доступная ему - (5, 5). Устанавливая дрон в эту позицию, он добивается уменьшения диаметра своего расширенного подграфа на две единицы. Таким образом d(R1∗ ) = 8. Его ход никак не повлиял на диаметр другого игрока: d(R2∗ ) = 15. 2. Шаг № 2. Далее ходит второй игрок. Он может установить своего активного агента в позицию (4, 4). В результате этого хода d(R2∗ ) = 11 и d(R1∗ ) = 8. Таким образом, он уменьшил свой диаметр на 4 единицы. 3. Шаг № 3. Снова ход первого игрока. Он перемещает своего агента в позицию (5, 4). Этот подвижный агент устанавливает связь с активным агентом другого игрока, который на данном шаге в позиции (4, 4), и с неподвижным агентом в позиции (6, 4). Таким образом, используя в своих целях агента второго игрока, первый игрок получает уменьшение диаметра еще на две единицы: d(R1∗ ) = 6, d(R2∗ ) = 9. Заметим также, что результатом его хода стало также уменьшение диаметра второго игрока на две единицы. 4. Шаг № 4. Желая использовать дрон первого игрока, второй игрок перемещает своего агента в позицию (5, 3) и получает d(R2∗ ) = 5. Но в результате его хода, перестает существовать построенный путь первого игрока, и его диаметр устанавливается в первоначальное значение: d(R1∗ ) = 10. 5. Шаг № 5. Первый игрок снова поместит дрон в позицию (5, 5), разрушив построенный путь второго игрока и получив d(R1∗ ) = 8. Для второго игрока d(R2 ) = 15. 6. Шаг № 6. Второй игрок переместит агента в позицию (4, 4). И так далее. 19

Таким образом дрон первого игрока будет постоянно перемещаться между позициями (5, 5) и (5, 4), а второго - (4, 4) и (5, 3). Следовательно, данная игра не конечношаговая и в ней отсутствует абсолютное равновесие по Нэшу. Сформулируем условие существования абсолютного равновесия по Нэшу: каждый игрок перемещает своего дрона так, чтобы диаметр остальных игроков не увеличился. Будем называть это условие условием «благожелательности» игроков. Очевидно, что после введения данного условия количества альтернатив для каждого игрока может уменьшиться. Рассмотрим теперь эту же игру, но теперь на каждого игрока наложим условие «благожелательности». Пусть, первый шаг делает первый игрок. Он помещает своего агента в позицию (5, 5). На втором шаге второй игрок устанавливает агента в позицию (4, 4). На третьем шаге первый игрок, желая использовать дрон второго игрока, перемещает активного агента в позицию (5, 4) (см. рис. 11). На этом игра заканчивается: второй игрок не может переместить беспилотник в позицию (5, 3), т. к. это приведет к увеличению текуРис. 11: Дерево игры щего диаметра первого игрока. Очевидно, что в дан- при условии, что перном случае единственное решение и будет равновесным вым «ходит» первый игрок по Нэшу. Рассмотрим теперь случай, когда первый шаг делает второй игрок. Он устанавливает подвижного агента в позицию (4, 4). После его хода, первый игрок имеет две альтернативы: позиция (5, 4) и (5, 5). Помещая дрон в любую из этих позиций, первый игрок заканчивает игру (см. рис. 12). В данном случае стратегии u1 = (1), u2 = (1) приведут к абсолютному равновесию по Нэшу с выигрышам для первого игрока 4, для второго - 6. Рис. 12: Дерево игры при условии, что первым «ходит» второй игрок 20

Глава 3. Описание программного обеспечения В рамках данной работы автором было реализовано программное обеспечение, позволяющее исследовать игру, описанную в главе 2. 3.1 Постановка задачи для программного обеспечения Программный продукт должен удовлетворять следующим требованиям: 1. Должен быть реализован алгоритм, позволяющий по имеющимся входным данным о расположении агентов построить все сценарии развития игры. 2. Архитектура программы должна позволять относительно легкую масштабируемость, изменение деталей постановки игры и количества игроков. 3.2 Обоснование подхода к решению задачи Наглядно продемонстрировать все сценарии развития игры можно с помощью дерева решений. Данное дерево состоит из единственного узла - корня и присоединенных к нему поддеревьев, которые также являются деревьями. Таким образом это дерево может быть определено через само себя. Поэтому было принято решение использовать рекурсию для построения дерева решений. Рекурсивная процедура работает следующим образом: «рисует» одну линию (до разветвления), а затем вызывает сама себя для «рисования» поддеревьев. Эти поддеревья отличаются своими корнями и количеством содержащихся в них разветвлений. В данном случае корень соответствует одной вершине из множества очередности игрока, а разветвления - множеству альтернатив этого же игрока. Параметр Step P Pos Dpr CurrPayoff P1 GlobPayoff P2 GlobPayoff Значение Номер шага Номер игрока Новая позиция подвижного агента Диаметр на предыдущем шаге Выигрыш игрока от этого шага Текущий общий выигрыш первого игрока Текущий общий выигрыш второго игрока Таблица 1: Параметры 21

Листьями мы будем называть узлы, не содержащие поддеревьев. Множество листьев соответствует множеству окончательных позиций, т. е. таких позиций, в которых у игроков нет альтернатив для выбора положения дрона. Глубина рекурсии соответствует общему количеству шагов, сделанных игроками. Вывод программы состоит из параметров, приведенных в таблице 1. 3.3 Описание архитектуры программы Данный программный продукт написан на объектно ориентированном языке высокого уровня Objective-C с использованием фреймворка Foundation. В качестве среды для разработки использовался X-Code. Фреймворк Foundation определяет базовый слой Objective-C классов, представляет множество парадигм, которые определяют функциональность не охватываемую языком Objective-C. Фреймворк включает в себя корневой класс (NSObject), классы представляющие базовые типы данных, такие как строки (NSString) и числа (NSNumber), классы коллекции для хранения других объектов (NSArray, NSDictionary, NSSet) и т. д. В качестве библиотеки для описания графов использовалась библиотека с открытым исходным кодом: PESGraph. Она содержит классы для описания графа (PESGraph), ребер (PESGraphEdge), вершин (PESGraphNode), маршрута (PESGraphRoute) и шага в маршруте между двумя вершинами (PESGraphRouteStep). Были написаны следующие основные классы: NTPosition, NTSpace, NTPlayer. Класс NTPosition описывает положение в ДПСК, а также дает возможность проверки узлов на соседство. Класс NTPlayer описывает игрока. NTSpace описывает подпространство, в котором происходит игра. Этот класс является синглтоном. Для добавления методов к уже существующим классам библиотеки PESGraph использовались категории. Использование данных технологий позволяет не вносить изменения в исходные файлы классов, что облегчает разработку и возможность обновления версии библиотеки без влияния на добавленные методы. Добавленные в категорию методы доступны всем классам, унаследованным от существующего. В программе была добавлена категория PESGraph+Diameter с методом diameter, который возвращает объект типа PESGraphRoute, описывающий диаметр для текущего графа. Для добавления свойств к уже существующим классам использовались расширения классов. В программе создано расширение класса PESGraphNode, добавляющее свойство типа NTPosition. Название расширения PESGraphNode_Position. 22

Глава 4. Тестирование программы на примере игры двух лиц 4.1 Постановка игры Игра Γ происходит на сетевой структуре, изображенной на рис. 13. Имеется два игрока: N = {1, 2}. Вершины подграфа первого игрока будем изображать в виде заполненных кружков, а второго игрока — в виде квадратиков. Заметим, что в позиции (3, 5) находятся одновременно два неподвижных агента разных игроков. Однако связь между ними отсутствует. Рис. 13: Сетевая структура игры Диаметр подграфа первого игрока d(R1 ) = 8 с началом в точке (2, 3) и концом в (5, 3). Диаметр второго игрока d(R2 ) = 17 с началом в точке (3, 8) и концом в (3, 1). Целью каждого из игроков на протяжении всей игры является минимизация своего диаметра. 4.2 Результат при условии, что первым «ходит» первый игрок Результат работы программы представлен на рис. 14. Данный результат означает, что на первом шаге первый игрок может установить своего агента в позицию (3, 3), что дает ему уменьшение его диаметра на 4 единицы. Видим, что данный ход никак не влияет на диаметр второго игрока (P2 GlobalPayoff: 0). Далее «ходит» второй игрок. После хода первого игрока, для него имеются три альтернативы для установления подвижного агента: (3, 4), (6, 5), (7, 5). При установлении подвижного агента в одну из этих позиций он получит выигрыш 10, 4, и 2 соответственно. После любого 23

Рис. 14: Вывод программы при условии, что первым «ходит» первый игрок из этих ходов игра заканчивается, так как нет больше альтернатив ни для одного игрока. Рассмотрим другую ветку дерева игры. Первый игрок на первом шаге может установить подвижного агента позицию (3, 4). На втором шаге второй игрок имеет в качестве альтернатив позиции (3, 3), (6, 5), (7, 5). Например, если второй игрок установит агента в позицию (6, 5), то на третьем ходе первый игрок сможет установить дрон в позицию (3, 3) и т. д. Рис. 15: Дерево игры при условии, что первым «ходит» первый игрок Дерево решений данной игры, полученное на основании результатов программы, изображено на рис. 15. На данном дереве множество очередности первого игрока изображено в виде кружков, а второго - квадратиков. Каждая вершина из множеств очередности помечена двойным индексом, означающим новое положение дрона на ДПСК. Одиночный индекс означает номер альтернативы для игрока. В окончательных позициях записаны выигрыши игроков. 24

4.3 Результат при условии, что первым «ходит» второй игрок Рассмотри теперь ситуацию, когда первый ход делает второй игрок. Результат программы в этом случае приведен на рис. 16. Рис. 16: Вывод программы при условии, что первым «ходит» второй игрок Данный результат интерпретируется аналогично предыдущему результату и соответствует дереву решений, изображенному на рис. 17. Рис. 17: Дерево игры при условии, что первым «ходит» второй игрок 4.4 Вывод Заметим принципиальное различие между деревьями игры в двух случаях. Также минимальный выигрыш, который может гарантировать себе второй игрок когда «ходит» первым 4, а когда вторым - 2. 25

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

Заключение Анализ проблемы оперативного восстановления связи в местах природных катастроф показал, что ключевую роль здесь играет разумное использование ограниченных ресурсов, в частности, беспилотников (дронов). С учетом динамики развития процесса, было принято решение в качестве сетевой структуры использовать MANET сеть. В данном исследовании использовался подход, позволяющий рассмотреть совместный сценарий поведения узлов сети для достижения максимальной выгоды. Рассмотрена новая постановка динамической игры управления агентами в сети. Данная игра была исследована с применением методов теории многошаговых игр. Найден алгоритм, позволяющий построить дерево решений для конечношаговой игры. Сформулировано условие существования абсолютного равновесия по Нэшу. Приведен пример игры двух лиц с отсутствием такого равновесия. Написано программное обеспечение, позволяющее построить дерево решений для конечношаговой игры. Программный продукт протестирован на примере игры двух лиц. Данное исследование может быть расширено использованием других типов решеток, в частности треугольной и шестиугольной. Данные типы решеток более точно соответствуют архитектуре MANET сетей. Также может быть введен кооперативный поход, позволяющий более точно описать координирование действий спасательных отрядов. Некоторые результаты данного исследования нашли отражение в следующих публикациях [8], [9]. 27

Список литературы [1] Новиков Д. А. Игры и сети. // Математическая теория игр и её приложения, 2010. Т. 2. Вып. 1. С. 107–124. [2] Yu F. R. Cognitive Radio Mobile Ad Hoc Networks. Springer, 2011. 507 c. [3] Zhu Han, Dusit Niyato, Walid Saad, Tamer Başar, Are Hjørungnes. Game Theory in Wireless and Communication Networks. Theory, Models, and Applications. Cambridge University Press, 2012. 554 c. [4] Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр. СПб.: БХВ-Петербург, 2012. 424 c. [5] Петросян Л. А., Седаков. А. А. Многошаговые игры с полной информацией. // Математическая теория игр и её приложения, 2009. Вып. 26.1. С. 121–138. [6] Dijkstra E. W. A note on two problems in connexion with graphs. // Numerische Matematik, 1959. С. 269–271. [7] Wilson R. J. Introduction to Graph Theory. Edinburgh: Oliver and Boyd, 1972. 209 c. [8] Тимонин Н. О. Одна динамическая игра управления агентами в сети. // Процессы управления и устойчивость: Труды 47-й международной научной конференции аспирантов и студентов / под ред. Н. В. Смирнова, Т. Е. Смирновой. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2016. Принято к публикации. [9] Gromova E., Gromov D., Timonin N., Kirpichnikova A., Blakeway S. A dynamic game of mobile agents placement on MANET. Submitted to IEEE conference SIMS 2016. 28

Приложение main.m 1 2 3 #import <Foundation/Foundation.h> #import "NTPlayer.h" #import "NTSpace.h" 4 5 6 7 8 9 10 11 12 13 14 15 16 /* * Game tree creation. * * @param i index of player * @param players array of players * @param step step * @param benevolenceCondition condition for benevolence */ void moveForPlayer(int i, NSArray *players, int step, BOOL benevolenceCondition) { NTPlayer *player = players[i]; step++; 17 18 19 20 for (NTPosition *position in [NTSpace sharedInstance].freePositions) { NTPosition *previousActiveAgentPosition = player.activeAgent. position; NSUInteger previousDiameterLength = player.currentDiameterRoute. length; 21 22 23 24 25 for (NTPlayer *player in players) { player.previousDiameterLength = player.currentDiameterRoute. length; } [player moveActiveAgentToPosition:position]; 26 27 28 29 30 31 32 33 34 35 // Check benevolence for players BOOL benevolence = YES; if (benevolenceCondition) { for (NTPlayer *otherPlayer in players) { if (![otherPlayer isEqual:player]) { benevolence = (otherPlayer.currentDiameterRoute.length > otherPlayer.previousDiameterLength) ? NO : YES; } } } 36 37 if ((player.currentDiameterRoute.length < player. previousDiameterLength) && benevolence) { 29

NSMutableString *logStirng = [NSMutableString stringWithFormat:@" Step:%i P%lu Pos:(%lu,%lu) Dpr:%2lu Dn:%2.f CurrPayoff:%2.f", step,(unsigned long)player.playerId + 1, position.x, position. y, (unsigned long)previousDiameterLength, player. currentDiameterRoute.length, previousDiameterLength - player. currentDiameterRoute.length]; 38 39 for (NTPlayer *player in players) { [logStirng appendString:[NSString stringWithFormat:@" P%lu GlobPayoff:%2.f",(unsigned long)player.playerId+1, player. startDiameterRoute.length - player.currentDiameterRoute. length]]; } NSLog(@"%@",logStirng); 40 41 42 43 44 for (NTPlayer *nextPlayer in players) { if (![nextPlayer isEqual:player]) { moveForPlayer((int)nextPlayer.playerId, players, step, benevolenceCondition); } } 45 46 47 48 49 50 } [player moveActiveAgentToPosition:previousActiveAgentPosition]; 51 52 } 53 54 } 55 56 57 int main(int argc, const char * argv[]) { 58 59 @autoreleasepool { 60 61 62 NTPlayer *p1 = [[NTPlayer alloc] initWithDefaultConfig1]; NTPlayer *p2 = [[NTPlayer alloc] initWithDefaultConfig4]; 63 64 65 [p2.agents addObject:p1.activeAgent]; [p1.agents addObject:p2.activeAgent]; 66 67 NSArray *players = @[p1, p2]; 68 69 [NTSpace sharedInstance].players = players; 70 71 72 NSLog(@"P1 startDiameterRoute: %lu", (unsigned long)p1. startDiameterRoute.length); NSLog(@"P2 startDiameterRoute: %lu", (unsigned long)p2. startDiameterRoute.length); 73 74 75 moveForPlayer(0, players, 0, YES); // Player 1 makes first step moveForPlayer(1, players, 0, YES); // Player 2 makes first step 30

76 } return 0; 77 78 79 } NTSpace.h 1 2 3 #import <Foundation/Foundation.h> #import "NTPosition.h" #import "NTPlayer.h" 4 5 6 @interface NTSpace : NSObject 7 8 9 10 11 /** * Players */ @property (nonatomic, strong, readwrite) NSArray<NTPlayer *> *players; 12 13 14 15 16 /** * Free positions for drons */ @property (nonatomic, strong, readonly) NSArray<NTPosition *> *freePositions ; 17 18 19 20 21 22 23 /** * This class is a singleton. Convenience method to get NTSpace instance * * @return NTSpace instance */ + (instancetype)sharedInstance; 24 25 @end NTSpace.m 1 #import "NTSpace.h" 2 3 4 @interface NTSpace () 5 6 7 8 9 /** * Free positions for drons */ @property (nonatomic, strong, readwrite) NSArray<NTPosition *> * freePositions; 10 11 @end 12 31

13 @implementation NTSpace 14 15 16 #pragma mark - Initializators 17 18 19 20 21 22 23 24 + (instancetype)sharedInstance { static NTSpace *space = nil; static dispatch_once_t onceToken; dispatch_once(&onceToken, ^{ space = [[self alloc] init]; space.freePositions = [NSMutableArray new]; }); 25 return space; 26 27 } 28 29 #pragma mark - Setter/Getter 30 31 32 - (NSString *)description { NSMutableString *descr = [NSMutableString new]; 33 for (NTPosition *position in self.freePositions) { [descr appendString:[NSString stringWithFormat:@" (%lu, %lu) ", position.x, position.y]]; } 34 35 36 37 return descr; 38 39 } 40 41 42 43 - (NSArray<NTPosition *> *)freePositions { NSMutableArray *resultPositions = [NSMutableArray new]; 44 45 46 NTPosition *leftBottom = [NTPosition positionWithX:0 Y:0]; NTPosition *rightTop = [NTPosition positionWithX:0 Y:0]; 47 48 49 50 NSMutableArray *takenPositions = [NSMutableArray new]; for (NTPlayer *p in self.players) { for (PESGraphNode *node in p.agents) { 51 52 53 leftBottom.x = (node.position.x < leftBottom.x) ? node.position.x : leftBottom.x; leftBottom.y = (node.position.y < leftBottom.y) ? node.position.y : leftBottom.y; 54 55 56 rightTop.x = (node.position.x > rightTop.x) ? node.position.x : rightTop.x; rightTop.y = (node.position.y > rightTop.y) ? node.position.y : rightTop.y; 32

57 [takenPositions addObject:node.position]; 58 } 59 } 60 61 for (int j = (int)leftBottom.x; j <= (int)rightTop.x; j++) { for (int i = (int)leftBottom.y; i <= (int)rightTop.y; i++) { 62 63 64 BOOL flag = YES; for (NTPosition *position in takenPositions) { if ((int)position.x == j && (int)position.y == i) { flag = NO; } } 65 66 67 68 69 70 71 if (flag) { [resultPositions addObject:[NTPosition positionWithX:j Y:i]]; } 72 73 74 75 } 76 } 77 78 return [NSArray arrayWithArray:resultPositions]; 79 80 } 81 82 83 1 @end NTPosition.h #import <Foundation/Foundation.h> 2 3 @interface NTPosition : NSObject 4 5 6 7 8 /** * X coordinate in Cartesian coordinate system */ @property (nonatomic, readwrite) NSUInteger x; 9 10 11 12 13 /** * Y coordinate in Cartesian coordinate system */ @property (nonatomic, readwrite) NSUInteger y; 14 15 16 17 18 /** * Convenience initializer that allows create NTPositon with two Cartesian coordinates * * @param x X coordinate 33

19 20 21 22 23 * @param y Y coordinate * * @return NTPosition instance */ + (instancetype)positionWithX:(NSUInteger)x Y:(NSUInteger)y; 24 25 26 27 28 29 30 31 32 /** * Check, is the position nearby another position * * @param position NTPosition to check * * @return YES/NO */ - (BOOL)isNearWithPosition:(NTPosition *)position; 33 34 @end NTPosition.m 1 #import "NTPosition.h" 2 3 @interface NTPosition () 4 5 @end 6 7 @implementation NTPosition 8 9 10 11 12 13 14 + (instancetype)positionWithX:(NSUInteger)x Y:(NSUInteger)y { NTPosition *p = [[self alloc] init]; p.x = x; p.y = y; return p; } 15 16 17 18 19 - (BOOL)isNearWithPosition:(NTPosition *)position { BOOL result = (sqrt( pow((double)self.x - (double)position.x, 2) + pow(( double)self.y - (double)position.y, 2)) == 1) ? YES : NO; return result; } 20 21 @end NTPlayer.h 1 2 3 4 5 #import <Foundation/Foundation.h> #include "NTPosition.h" #import "PESGraph.h" #import "PESGraph+Diameter.h" #import "PESGraphNode_Position.h" 34

6 7 #import "PESGraphEdge.h" #import "PESGraphRoute.h" 8 9 @interface NTPlayer : NSObject 10 11 12 13 14 /** * Player identifier */ @property (nonatomic, readonly) NSUInteger playerId; 15 16 17 18 19 /** * Players previous diameter length */ @property (nonatomic, readwrite) NSUInteger previousDiameterLength; 20 21 22 23 24 /** * All agents */ @property (nonatomic, strong, readonly) NSMutableArray<PESGraphNode *> * agents; 25 26 27 28 29 /** * Drone */ @property (nonatomic, strong, readonly) PESGraphNode *activeAgent; 30 31 32 33 34 /** * Diameter at first game stage */ @property (nonatomic, strong, readonly) PESGraphRoute *startDiameterRoute; 35 36 37 38 39 /** * Diameter at current game stage */ @property (nonatomic, strong, readonly) PESGraphRoute *currentDiameterRoute; 40 41 42 43 44 45 46 /** * Move active agent to new position * * @param position New active agent position */ - (void)moveActiveAgentToPosition:(NTPosition *)position; 47 48 49 50 51 52 53 /** * Initializators with different agents positions * * @return instance of NTPlayer */ - (instancetype)initWithDefaultConfig1; 35

54 55 56 57 58 59 60 - (instancetype)initWithDefaultConfig2; (instancetype)initWithDefaultConfig3; (instancetype)initWithDefaultConfig4; (instancetype)initWithDefaultConfig5; (instancetype)initWithDefaultConfig6; (instancetype)initWithDefaultConfig7; (instancetype)initWithDefaultConfig8; 61 62 @end NTPlayer.m 1 2 #import "NTPlayer.h" #import "NTSpace.h" 3 4 @interface NTPlayer () 5 6 7 8 9 /** * Players graph */ @property (nonatomic, strong, readwrite) PESGraph *graph; 10 11 12 13 14 /** * Source node in diameter */ @property (nonatomic, strong, readwrite) PESGraphNode *sourse; 15 16 17 18 19 /** * Destignation node in diameter */ @property (nonatomic, strong, readwrite) PESGraphNode *destignation; 20 21 22 23 24 /** * All agents */ @property (nonatomic, strong, readwrite) NSMutableArray<PESGraphNode *> * agents; 25 26 27 28 29 /** * Diameter at first game stage */ @property (nonatomic, strong, readwrite) PESGraphRoute *startDiameterRoute; 30 31 32 33 34 /** * Diameter at current game stage */ @property (nonatomic, strong, readwrite) PESGraphRoute *currentDiameterRoute ; 35 36

36 37 @end 38 39 40 @implementation NTPlayer 41 42 #pragma mark - Setter/Getter 43 44 45 - (PESGraph *)graph { PESGraph *graph = [PESGraph new]; 46 for (int i = 0; i < (int)self.agents.count; i++) { for (int j = 0; j < (int)self.agents.count; j++) { if (i > j) { PESGraphNode *fromNode = self.agents[i]; PESGraphNode *toNode = self.agents[j]; 47 48 49 50 51 52 if ([fromNode.position isNearWithPosition:toNode.position]) { PESGraphEdge *newEdge = [PESGraphEdge edgeWithName:[ NSString stringWithFormat:@"%@ <-> %@", fromNode. identifier, toNode.identifier] andWeight:@1]; [graph addBiDirectionalEdge:newEdge fromNode:fromNode toNode:toNode]; } 53 54 55 56 57 } 58 } 59 } 60 61 return graph; 62 63 } 64 65 66 67 68 69 - (PESGraphRoute *)startDiameterRoute { PESGraphRoute *route; if (!_startDiameterRoute) { route = [self.graph diameter]; 70 self.sourse = route.startingNode; self.destignation = route.endingNode; _startDiameterRoute = route; 71 72 73 74 } else { route = _startDiameterRoute; } 75 76 77 78 return route; 79 80 } 81 37

82 83 84 85 86 - (PESGraphRoute *)currentDiameterRoute { if (!self.startDiameterRoute) { [self startDiameterRoute]; } 87 return [self.graph shortestRouteFromNode:self.sourse toNode:self. destignation]; 88 89 } 90 91 92 #pragma mark - Initializators 93 94 95 96 - (instancetype)initWithDefaultConfig1 { self = [super init]; if (self) { 97 _playerId = 0; 98 99 PESGraphNode *node1 = [PESGraphNode nodeWithIdentifier:@"1" :[NTPosition positionWithX:1 Y:3]]; PESGraphNode *node2 = [PESGraphNode nodeWithIdentifier:@"2" :[NTPosition positionWithX:2 Y:3]]; PESGraphNode *node3 = [PESGraphNode nodeWithIdentifier:@"3" :[NTPosition positionWithX:2 Y:4]]; PESGraphNode *node4 = [PESGraphNode nodeWithIdentifier:@"4" :[NTPosition positionWithX:2 Y:5]]; PESGraphNode *node5 = [PESGraphNode nodeWithIdentifier:@"5" :[NTPosition positionWithX:3 Y:5]]; PESGraphNode *node6 = [PESGraphNode nodeWithIdentifier:@"6" :[NTPosition positionWithX:4 Y:5]]; PESGraphNode *node7 = [PESGraphNode nodeWithIdentifier:@"7" :[NTPosition positionWithX:4 Y:4]]; PESGraphNode *node8 = [PESGraphNode nodeWithIdentifier:@"8" :[NTPosition positionWithX:4 Y:3]]; PESGraphNode *node9 = [PESGraphNode nodeWithIdentifier:@"9" :[NTPosition positionWithX:5 Y:3]]; 100 101 102 103 104 105 106 107 108 position position position position position position position position position 109 PESGraphNode *activeNode = [PESGraphNode nodeWithIdentifier:@"100" position:[NTPosition positionWithX:0 Y:0]]; 110 111 _agents = [NSMutableArray arrayWithArray:@[node1, node2, node3, node4, node5, node6, node7, node8, node9, activeNode]]; _activeAgent = activeNode; 112 113 } 114 115 return self; 116 117 } 118 38

119 120 121 122 - (instancetype)initWithDefaultConfig2 { self = [super init]; if (self) { _playerId = 1; 123 PESGraphNode *node1 = [PESGraphNode nodeWithIdentifier:@"1" :[NTPosition positionWithX:1 Y:2]]; PESGraphNode *node2 = [PESGraphNode nodeWithIdentifier:@"2" :[NTPosition positionWithX:2 Y:2]]; PESGraphNode *node3 = [PESGraphNode nodeWithIdentifier:@"3" :[NTPosition positionWithX:2 Y:1]]; PESGraphNode *node4 = [PESGraphNode nodeWithIdentifier:@"4" :[NTPosition positionWithX:3 Y:1]]; PESGraphNode *node5 = [PESGraphNode nodeWithIdentifier:@"5" :[NTPosition positionWithX:4 Y:1]]; PESGraphNode *node6 = [PESGraphNode nodeWithIdentifier:@"6" :[NTPosition positionWithX:4 Y:2]]; PESGraphNode *node7 = [PESGraphNode nodeWithIdentifier:@"7" :[NTPosition positionWithX:5 Y:2]]; 124 125 126 127 128 129 130 position position position position position position position 131 PESGraphNode *activeNode = [PESGraphNode nodeWithIdentifier:@"200" position:[NTPosition positionWithX:0 Y:0]]; 132 133 _agents = [NSMutableArray arrayWithArray:@[node1, node2, node3, node4, node5, node6, node7, activeNode]]; _activeAgent = activeNode; 134 135 } 136 137 return self; 138 139 } 140 141 142 143 144 - (instancetype)initWithDefaultConfig3 { self = [super init]; if (self) { _playerId = 1; 145 146 147 148 149 150 151 152 PESGraphNode *node1 = [PESGraphNode nodeWithIdentifier:@"1" :[NTPosition positionWithX:1 Y:2]]; PESGraphNode *node2 = [PESGraphNode nodeWithIdentifier:@"2" :[NTPosition positionWithX:2 Y:2]]; PESGraphNode *node3 = [PESGraphNode nodeWithIdentifier:@"3" :[NTPosition positionWithX:2 Y:1]]; PESGraphNode *node4 = [PESGraphNode nodeWithIdentifier:@"4" :[NTPosition positionWithX:3 Y:1]]; PESGraphNode *node5 = [PESGraphNode nodeWithIdentifier:@"5" :[NTPosition positionWithX:4 Y:1]]; PESGraphNode *node6 = [PESGraphNode nodeWithIdentifier:@"6" :[NTPosition positionWithX:5 Y:1]]; PESGraphNode *node7 = [PESGraphNode nodeWithIdentifier:@"7" 39 position position position position position position position

:[NTPosition positionWithX:5 Y:2]]; PESGraphNode *node8 = [PESGraphNode nodeWithIdentifier:@"8" position :[NTPosition positionWithX:6 Y:2]]; 153 154 PESGraphNode *activeNode = [PESGraphNode nodeWithIdentifier:@"200" position:[NTPosition positionWithX:0 Y:0]]; 155 156 _agents = [NSMutableArray arrayWithArray:@[node1, node2, node3, node4, node5, node6, node7, node8, activeNode]]; _activeAgent = activeNode; 157 158 } 159 160 return self; 161 162 } 163 164 165 166 167 - (instancetype)initWithDefaultConfig4 { self = [super init]; if (self) { _playerId = 1; 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 PESGraphNode *node1 = [PESGraphNode nodeWithIdentifier:@"1" position :[NTPosition positionWithX:3 Y:7]]; PESGraphNode *node2 = [PESGraphNode nodeWithIdentifier:@"2" position :[NTPosition positionWithX:3 Y:6]]; PESGraphNode *node3 = [PESGraphNode nodeWithIdentifier:@"3" position :[NTPosition positionWithX:4 Y:6]]; PESGraphNode *node4 = [PESGraphNode nodeWithIdentifier:@"4" position :[NTPosition positionWithX:5 Y:6]]; PESGraphNode *node5 = [PESGraphNode nodeWithIdentifier:@"5" position :[NTPosition positionWithX:6 Y:6]]; PESGraphNode *node6 = [PESGraphNode nodeWithIdentifier:@"6" position :[NTPosition positionWithX:7 Y:6]]; PESGraphNode *node7 = [PESGraphNode nodeWithIdentifier:@"7" position :[NTPosition positionWithX:8 Y:6]]; PESGraphNode *node8 = [PESGraphNode nodeWithIdentifier:@"8" position :[NTPosition positionWithX:8 Y:5]]; PESGraphNode *node9 = [PESGraphNode nodeWithIdentifier:@"9" position :[NTPosition positionWithX:8 Y:4]]; PESGraphNode *node10 = [PESGraphNode nodeWithIdentifier:@"10" position:[NTPosition positionWithX:7 Y:4]]; PESGraphNode *node11 = [PESGraphNode nodeWithIdentifier:@"11" position:[NTPosition positionWithX:6 Y:4]]; PESGraphNode *node12 = [PESGraphNode nodeWithIdentifier:@"12" position:[NTPosition positionWithX:6 Y:3]]; PESGraphNode *node13 = [PESGraphNode nodeWithIdentifier:@"13" position:[NTPosition positionWithX:6 Y:2]]; PESGraphNode *node14 = [PESGraphNode nodeWithIdentifier:@"14" position:[NTPosition positionWithX:5 Y:2]]; PESGraphNode *node15 = [PESGraphNode nodeWithIdentifier:@"15" 40

position:[NTPosition positionWithX:4 Y:2]]; PESGraphNode *node16 = [PESGraphNode nodeWithIdentifier:@"16" position:[NTPosition positionWithX:3 Y:2]]; PESGraphNode *node17 = [PESGraphNode nodeWithIdentifier:@"17" position:[NTPosition positionWithX:3 Y:1]]; PESGraphNode *node18 = [PESGraphNode nodeWithIdentifier:@"18" position:[NTPosition positionWithX:3 Y:5]]; PESGraphNode *node19 = [PESGraphNode nodeWithIdentifier:@"19" position:[NTPosition positionWithX:3 Y:8]]; 184 185 186 187 188 PESGraphNode *activeNode = [PESGraphNode nodeWithIdentifier:@"200" position:[NTPosition positionWithX:0 Y:0]]; 189 190 _agents = [NSMutableArray arrayWithArray:@[node1, node2, node3, node4, node5, node6, node7, node8, node9, node10, node11, node12, node13, node14, node15, node16, node17, node18, node19, activeNode]]; _activeAgent = activeNode; 191 192 } 193 194 return self; 195 196 } 197 198 199 200 201 - (instancetype)initWithDefaultConfig5 { self = [super init]; if (self) { _playerId = 0; 202 203 204 205 206 207 208 209 210 211 212 213 PESGraphNode *node1 = [PESGraphNode nodeWithIdentifier:@"1" position :[NTPosition positionWithX:1 Y:3]]; PESGraphNode *node2 = [PESGraphNode nodeWithIdentifier:@"2" position :[NTPosition positionWithX:2 Y:3]]; PESGraphNode *node3 = [PESGraphNode nodeWithIdentifier:@"3" position :[NTPosition positionWithX:2 Y:4]]; PESGraphNode *node4 = [PESGraphNode nodeWithIdentifier:@"4" position :[NTPosition positionWithX:2 Y:5]]; PESGraphNode *node5 = [PESGraphNode nodeWithIdentifier:@"5" position :[NTPosition positionWithX:2 Y:6]]; PESGraphNode *node6 = [PESGraphNode nodeWithIdentifier:@"6" position :[NTPosition positionWithX:3 Y:6]]; PESGraphNode *node7 = [PESGraphNode nodeWithIdentifier:@"7" position :[NTPosition positionWithX:4 Y:6]]; PESGraphNode *node8 = [PESGraphNode nodeWithIdentifier:@"8" position :[NTPosition positionWithX:5 Y:6]]; PESGraphNode *node9 = [PESGraphNode nodeWithIdentifier:@"9" position :[NTPosition positionWithX:5 Y:5]]; PESGraphNode *node10 = [PESGraphNode nodeWithIdentifier:@"10" position:[NTPosition positionWithX:5 Y:4]]; PESGraphNode *node11 = [PESGraphNode nodeWithIdentifier:@"11" 41

position:[NTPosition positionWithX:5 Y:3]]; PESGraphNode *node12 = [PESGraphNode nodeWithIdentifier:@"12" position:[NTPosition positionWithX:6 Y:3]]; PESGraphNode *node13 = [PESGraphNode nodeWithIdentifier:@"13" position:[NTPosition positionWithX:6 Y:2]]; PESGraphNode *node14 = [PESGraphNode nodeWithIdentifier:@"14" position:[NTPosition positionWithX:7 Y:2]]; PESGraphNode *node15 = [PESGraphNode nodeWithIdentifier:@"15" position:[NTPosition positionWithX:8 Y:2]]; PESGraphNode *node16 = [PESGraphNode nodeWithIdentifier:@"16" position:[NTPosition positionWithX:8 Y:3]]; PESGraphNode *node17 = [PESGraphNode nodeWithIdentifier:@"17" position:[NTPosition positionWithX:9 Y:3]]; PESGraphNode *node18 = [PESGraphNode nodeWithIdentifier:@"18" position:[NTPosition positionWithX:4 Y:5]]; 214 215 216 217 218 219 220 221 PESGraphNode *activeNode = [PESGraphNode nodeWithIdentifier:@"100" position:[NTPosition positionWithX:0 Y:0]]; 222 223 _agents = [NSMutableArray arrayWithArray:@[node1, node2, node3, node4, node5, node6, node7, node8, node9, node10, node11, node12, node13, node14, node15, node16, node17, node18, activeNode]]; _activeAgent = activeNode; 224 225 } 226 227 return self; 228 229 } 230 231 232 233 234 - (instancetype)initWithDefaultConfig6 { self = [super init]; if (self) { _playerId = 1; 235 236 237 238 239 240 241 242 243 PESGraphNode *node1 = [PESGraphNode nodeWithIdentifier:@"1" :[NTPosition positionWithX:4 Y:1]]; PESGraphNode *node2 = [PESGraphNode nodeWithIdentifier:@"2" :[NTPosition positionWithX:4 Y:2]]; PESGraphNode *node3 = [PESGraphNode nodeWithIdentifier:@"3" :[NTPosition positionWithX:3 Y:2]]; PESGraphNode *node4 = [PESGraphNode nodeWithIdentifier:@"4" :[NTPosition positionWithX:2 Y:2]]; PESGraphNode *node5 = [PESGraphNode nodeWithIdentifier:@"5" :[NTPosition positionWithX:2 Y:3]]; PESGraphNode *node6 = [PESGraphNode nodeWithIdentifier:@"6" :[NTPosition positionWithX:2 Y:4]]; PESGraphNode *node7 = [PESGraphNode nodeWithIdentifier:@"7" :[NTPosition positionWithX:3 Y:4]]; PESGraphNode *node8 = [PESGraphNode nodeWithIdentifier:@"8" :[NTPosition positionWithX:4 Y:4]]; 42 position position position position position position position position

PESGraphNode *node9 = [PESGraphNode nodeWithIdentifier:@"9" position :[NTPosition positionWithX:5 Y:4]]; PESGraphNode *node10 = [PESGraphNode nodeWithIdentifier:@"10" position:[NTPosition positionWithX:6 Y:4]]; PESGraphNode *node11 = [PESGraphNode nodeWithIdentifier:@"11" position:[NTPosition positionWithX:6 Y:5]]; PESGraphNode *node12 = [PESGraphNode nodeWithIdentifier:@"12" position:[NTPosition positionWithX:6 Y:6]]; PESGraphNode *node13 = [PESGraphNode nodeWithIdentifier:@"13" position:[NTPosition positionWithX:7 Y:6]]; PESGraphNode *node14 = [PESGraphNode nodeWithIdentifier:@"14" position:[NTPosition positionWithX:8 Y:6]]; PESGraphNode *node15 = [PESGraphNode nodeWithIdentifier:@"15" position:[NTPosition positionWithX:8 Y:5]]; PESGraphNode *node16 = [PESGraphNode nodeWithIdentifier:@"16" position:[NTPosition positionWithX:8 Y:4]]; PESGraphNode *node17 = [PESGraphNode nodeWithIdentifier:@"17" position:[NTPosition positionWithX:9 Y:4]]; 244 245 246 247 248 249 250 251 252 253 PESGraphNode *activeNode = [PESGraphNode nodeWithIdentifier:@"200" position:[NTPosition positionWithX:0 Y:0]]; 254 255 _agents = [NSMutableArray arrayWithArray:@[node1, node2, node3, node4, node5, node6, node7, node8, node9, node10, node11, node12, node13, node14, node15, node16, node17, activeNode]]; _activeAgent = activeNode; 256 257 } 258 259 return self; 260 261 } 262 263 264 265 266 - (instancetype)initWithDefaultConfig7 { self = [super init]; if (self) { _playerId = 0; 267 268 269 270 271 272 273 274 PESGraphNode *node1 = [PESGraphNode nodeWithIdentifier:@"1" :[NTPosition positionWithX:1 Y:4]]; PESGraphNode *node2 = [PESGraphNode nodeWithIdentifier:@"2" :[NTPosition positionWithX:2 Y:4]]; PESGraphNode *node3 = [PESGraphNode nodeWithIdentifier:@"3" :[NTPosition positionWithX:3 Y:4]]; PESGraphNode *node4 = [PESGraphNode nodeWithIdentifier:@"4" :[NTPosition positionWithX:3 Y:5]]; PESGraphNode *node5 = [PESGraphNode nodeWithIdentifier:@"5" :[NTPosition positionWithX:3 Y:6]]; PESGraphNode *node6 = [PESGraphNode nodeWithIdentifier:@"6" :[NTPosition positionWithX:4 Y:6]]; PESGraphNode *node7 = [PESGraphNode nodeWithIdentifier:@"7" 43 position position position position position position position

:[NTPosition positionWithX:5 Y:6]]; PESGraphNode *node8 = [PESGraphNode nodeWithIdentifier:@"8" position :[NTPosition positionWithX:6 Y:6]]; PESGraphNode *node9 = [PESGraphNode nodeWithIdentifier:@"9" position :[NTPosition positionWithX:6 Y:5]]; PESGraphNode *node10 = [PESGraphNode nodeWithIdentifier:@"10" position:[NTPosition positionWithX:6 Y:4]]; PESGraphNode *node11 = [PESGraphNode nodeWithIdentifier:@"11" position:[NTPosition positionWithX:7 Y:4]]; PESGraphNode *node12 = [PESGraphNode nodeWithIdentifier:@"12" position:[NTPosition positionWithX:4 Y:5]]; 275 276 277 278 279 280 PESGraphNode *activeNode = [PESGraphNode nodeWithIdentifier:@"100" position:[NTPosition positionWithX:0 Y:0]]; 281 282 _agents = [NSMutableArray arrayWithArray:@[node1, node2, node3, node4, node5, node6, node7, node8, node9, node10, node11, node12, activeNode]]; _activeAgent = activeNode; 283 284 } 285 286 return self; 287 288 } 289 290 291 292 293 - (instancetype)initWithDefaultConfig8 { self = [super init]; if (self) { _playerId = 1; 294 295 296 297 298 299 300 301 302 303 304 PESGraphNode *node1 = [PESGraphNode nodeWithIdentifier:@"1" position :[NTPosition positionWithX:5 Y:1]]; PESGraphNode *node2 = [PESGraphNode nodeWithIdentifier:@"2" position :[NTPosition positionWithX:5 Y:2]]; PESGraphNode *node3 = [PESGraphNode nodeWithIdentifier:@"3" position :[NTPosition positionWithX:3 Y:2]]; PESGraphNode *node4 = [PESGraphNode nodeWithIdentifier:@"4" position :[NTPosition positionWithX:3 Y:3]]; PESGraphNode *node5 = [PESGraphNode nodeWithIdentifier:@"5" position :[NTPosition positionWithX:3 Y:4]]; PESGraphNode *node6 = [PESGraphNode nodeWithIdentifier:@"6" position :[NTPosition positionWithX:2 Y:4]]; PESGraphNode *node7 = [PESGraphNode nodeWithIdentifier:@"7" position :[NTPosition positionWithX:2 Y:5]]; PESGraphNode *node8 = [PESGraphNode nodeWithIdentifier:@"8" position :[NTPosition positionWithX:2 Y:6]]; PESGraphNode *node9 = [PESGraphNode nodeWithIdentifier:@"9" position :[NTPosition positionWithX:3 Y:6]]; PESGraphNode *node10 = [PESGraphNode nodeWithIdentifier:@"10" position:[NTPosition positionWithX:4 Y:6]]; 44

PESGraphNode *node11 = [PESGraphNode nodeWithIdentifier:@"11" position:[NTPosition positionWithX:5 Y:6]]; PESGraphNode *node12 = [PESGraphNode nodeWithIdentifier:@"12" position:[NTPosition positionWithX:6 Y:6]]; PESGraphNode *node13 = [PESGraphNode nodeWithIdentifier:@"13" position:[NTPosition positionWithX:6 Y:5]]; PESGraphNode *node14 = [PESGraphNode nodeWithIdentifier:@"14" position:[NTPosition positionWithX:6 Y:4]]; PESGraphNode *node15 = [PESGraphNode nodeWithIdentifier:@"15" position:[NTPosition positionWithX:7 Y:4]]; PESGraphNode *node16 = [PESGraphNode nodeWithIdentifier:@"16" position:[NTPosition positionWithX:4 Y:5]]; 305 306 307 308 309 310 311 PESGraphNode *node17 = [PESGraphNode nodeWithIdentifier:@"17" position:[NTPosition positionWithX:4 Y:2]]; 312 313 PESGraphNode *activeNode = [PESGraphNode nodeWithIdentifier:@"200" position:[NTPosition positionWithX:0 Y:0]]; 314 315 _agents = [NSMutableArray arrayWithArray:@[node1, node2, node3, node4, node5, node6, node7, node8, node9, node10, node11, node12, node13, node14, node15, node16, node17, activeNode]]; _activeAgent = activeNode; 316 317 } 318 319 return self; 320 321 } 322 323 324 #pragma mark - Methods 325 326 327 328 - (void)moveActiveAgentToPosition:(NTPosition *)position { self.activeAgent.position = position; } 329 330 331 @end PESGraph+Diameter.h 1 #import "PESGraph.h" 2 3 @interface PESGraph (Diameter) 4 5 6 7 8 9 /** * Returns the route object that describes the diameter of graph. * * @return either a PESGraphRoute object or nil, if no diameter is possible */ 45

10 - (PESGraphRoute *)diameter; 11 12 1 2 3 4 @end #import #import #import #import PESGraph+Diameter.m "PESGraph+Diameter.h" "PESGraphNode.h" "PESGraphRoute.h" "PESGraphEdge.h" 5 6 @implementation PESGraph (Diameter) 7 8 - (PESGraphRoute *)diameter { 9 PESGraphRoute *result = nil; for (NSString *sourseKey in self.nodes) { PESGraphNode *sourse = [self.nodes objectForKey:sourseKey]; 10 11 12 13 for (NSString *destignationKey in self.nodes) { PESGraphNode *destignation = [self.nodes objectForKey: destignationKey]; 14 15 16 if (![sourse isEqual:destignation]) { PESGraphRoute *route = [self shortestRouteFromNode:sourse toNode:destignation]; result = (route.length > result.length) ? route : result; } 17 18 19 20 } 21 } return result; 22 23 24 } 25 26 @end PESGraphNode_Position.h 1 2 #import "PESGraphNode.h" #import "NTPosition.h" 3 4 @interface PESGraphNode () 5 6 7 8 9 /** * Node position in Cartesian system */ @property (nonatomic, strong) NTPosition *position; 10 11 @end 46

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв