Материал: Алгоритм, эвристически строящий оптимальный граф для задачи децентрализованного поиска

Алгоритм, эвристически строящий оптимальный граф для задачи децентрализованного поиска

Содержание

Введение

1. Задача об оптимальном графе для децентрализованного поиска

1.1 Формулировка

1.1.1 Жадный алгоритм

1.1.2 Модель Клайнберга

1.1.3 Математическая модель

1.2 Алгоритмы решения

1.2.1 Алгоритм локального поиска

1.2.2 Табу алгоритм

1.2.3 Метод ветвей и границ

1.3 Дополнения к алгоритмам

1.3.1 Выбор между одинаковыми соседями

1.3.2 Стартовый граф

2. Программная реализация

3. Результаты

Вывод

Список литературы

Приложение

Введение

Термин тесный мир (the small world) известен с 60х годов 20 века [1]. Множество математических моделей было предложено для объяснения, как тесный мир возникает в реальных сетях [5][6]. Некоторые из этих моделей были использованы для построения P2P сетей с логарифмической сложностью поиска, например распределенная хэш-таблица (Distributed Hash Table). Системы описанные в работах [2] и [3] основаны на модели Клайнберга [4]. Эта модель основана на том, что вершины графа имеют координаты в D мерном пространстве. Поиск в этой модели осуществляется с помощью жадного алгоритма, где старт начинается в произвольной вершине, и переход осуществляется, основываясь только на локальной информации - информации о соседях. При построении графа по модели Клайнберга жадный алгоритм в среднем делает  шагов.

С развитием технологий и увеличением количества информации, ее хранение и обработка стала трудоемкой. Вначале вся информация могла храниться в одном месте (сервере), и клиенты имели доступ с серверу и могли получать необходимую информацию. Потом информация начала храниться на разных компьютерах, но к ним доступ имел только сервер, поэтому все равно все запросы проходили через него. Такой поиск использует центр поиска. Позже произошел отказ от какого-то специального компьютера, который должен быть центром, и возникли одноранговые компьютерные сети (p2p - peer to peer).

В одноранговых сетях все элементы являются равноправными, и поиск может начинаться с любого элемента и проходить через любые элементы. Пример одноранговой сети можно увидеть на рисунке 1, а пример сети с сервером на рисунке 2.

Так как для поиска в одноранговой сети нет центра, который знает где находится информация. Для того, чтобы избежать необходимости хранения огромного количества информации, каждый узел одноранговой сети хранит информацию только о своих соседях, т.е. о тех узлах, с которыми он соединен. Поэтому для передачи или поиска необходимой информации в общем случае используется так называемы алгоритм broadcast. Этот алгоритм начинается с одного узла, потом передает информацию всем его соседям, и в каждом узле снова передает всем его соседям. Поэтому, если сеть связанная, то поиск точно сможет предоставить необходимую информацию.

В сети присутствует некоторое количество машин, при этом каждая может связаться с любой из других. Каждая из этих машин может посылать запросы другим машинам на предоставление каких-либо ресурсов в пределах этой сети и, таким образом, выступать в роли клиента. Будучи сервером, каждая машина должна быть способной обрабатывать запросы от других машин в сети, отсылать то, что было запрошено. Каждая машина также должна выполнять некоторые вспомогательные и административные функции (например, хранить список других известных машин-«соседей» и поддерживать его актуальность).

Одноранговые сети используются для построения файлообменных сетей, сетей распределенных вычислений, финансовых сетей и др.

Пользователи файлообменной сети выкладывают какие-либо файлы в общую (англ. share - делиться) директорию, содержимое которой доступно для скачивания другим пользователям. Какой-нибудь другой пользователь сети посылает запрос на поиск какого-либо файла. Программа ищет у клиентов сети файлы, соответствующие запросу, и показывает результат. После этого пользователь может скачать файлы у найденных источников. В современных файлообменных сетях информация загружается сразу с нескольких источников. Её целостность проверяется по контрольным суммам.

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

1. Задача об оптимальном графе для децентрализованного поиска

.1 Формулировка

Целью данной работы было проанализировать построенные оптимальные структуры и характер роста целевой функции.

1.1.1 Жадный алгоритм

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

Определим соседей вершины . Тогда жадный поиск в графе будет происходить следующим образом.

GreedyWalk(,)//-начальная вершина, - искомая вершина

2 if  then

return GreedyWalk(,)

else

return

Жадному алгоритму на вход подается две вершины - начальная и финальная. Он рассматривает все вершины из соседей начальной, рассчитывает расстояние от них до финальной вершины и переходит в ту, от которой минимальное расстояние. После этого такие же операции проводит с текущей вершины. Все это продолжается до тех пор пока мы не придем в вершину, расстояние от которой до финальной вершины будет минимально среди всех ее соседей.

Такой алгоритм в общем случае не дает точной гарантии нахождения финальной вершины от любой. См. рисунок 3.

Если использовать в качестве функции расстояния Евклидово расстояние на плоскости. И запустить жадный алгоритм с начальной точкой 1 и финальной точкой 4, то алгоритм после рассмотрения соседей вершины 1, перейдет в вершину 2, как самую ближайшую. И в итоге не сможет найти вершину 4, так как из вершины 2 некуда двигаться.

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

Рассмотрим пример набора точек на плоскости с Евклидовым расстоянием.

Рисунок 4 - разбиение Вороного

На рисунке 4 можно заметить, что любая точка, попавшая в какую-либо область, всегда будет ближе к точке, породившей эту область, чем к любой другой.

После того, как алгоритм разбил плоскость с помощью разбиения Вороного, соединяем ребрами те вершины, которые имеют общую границу.

Рисунок 5 - граф после соединения вершин

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

При запуске жадного поиска от какой-либо вершины, мы какое-то количество раз вызываем функцию подсчета расстояний от одной вершины до другой. Назовем сложностью поиска одной вершины от другой количество вызовов функции подсчета расстояния. Рассмотрим пример поиска вершины 15, от вершины 1 на графе с рисунков 6 - 13.

Рисунок 14 - итоговый путь

Поиск начинается с подсчета расстояния от начальной вершины до финальной . Потом мы рассматриваем соседей начальной вершины 1 - это вершины 2 и 6 и считаем расстояния от них  Так как наименьшее расстояние у вершины 2, то идем в вершину 2 (рисунок 8). Следующим шагом рассматриваем соседей вершины 2. Продолжаем до тех пор, пока не дойдем до вершины 15. В этом поиске мы столкнулись с неопределенностью на шаге номер 3 (рисунок 10). Расстояние от 4 и от 8 вершины одинаково. Возникает вопрос - какую вершину выбирать. На этот вопрос мы ответим при описании нашего алгоритма.

После того, как мы нашли финальную вершину, надо посчитать сложность поиска. Сложность поиска равна 12. На рисунке 14 красными вершинами отмечен путь жадного алгоритма, который включает в себя 7 вершин, и 5 синих вершин, которые не входят в жадный путь, но при этом использовались жадным алгоритмом, поэтому они вносят свой вес в сложность алгоритма.

.1.2 Модель Клайнберга

В своем подходе Клайнберг рассматривает точки на плоскости, которые представляют собой сетку размера . Тогда для того, чтобы жадный алгоритм мог найти необходимые вершины, начиная с любой, начальный граф должен иметь вид сетки, где каждая вершина соединена с вершиной слева, справа, сверху и снизу. Пример такого графа можно увидеть на рисунке 15.

Рисунок 15 - пример графа сетки

При такой структуре графа жадный поиск выполняется за , где . В нашем примере

Поэтому Клайнберг решил проверить, а нельзя ли немного изменить структура графа и при этом ускорить поиск. Оказалось, что можно. В своей модели он в существующую структуру сетку добавляет дополнительные ребра следующим образом:

(1)

В формуле (1)  - коэффициент кластеризации. Такой способ добавления ребер позволяет ускорить жадный поиск в среднем до .

Иногда в формуле (1) вместо коэффициента кластеризации используется просто вводимый пользователем параметр, и в зависимости от него граф может менять свой вид.

Например, при большом q, вероятность уменьшается с увеличением расстояния. Если же q мало, то вероятность длинных ребер возрастает.

.1.3 Математическая модель

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

Переменные:

(2)

(3)

Целевая функция:

(4)

(5)

Ограничения:

(6)

(7)

(8)

(9)

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

Ограничения (6) и (7) являются тривиальными, первое запрещает петли в графе, второе говорит, что начальная и финальная вершина обязательно должны быть в пути жадного алгоритма.

Ограничение (8) нужно для сохранения целостности пути. Оно описывает, что если вершина  находится в пути жадного алгоритма, то хотя бы один из ее соседей тоже должен будет там находиться. По сути для всех вершин, кроме начальной и финальной, таких соседей будет 2 - вершина, из которой пришли, и вершина, в которую уйдем.

Последнее ограничение (9) описывает выбор следующей вершины в пути по принципу жадного алгоритма. Т.е. если вершина  находится в пути, то среди ее соседей обязательно найдется вершина , расстояние от которой будет наименьшее среди всех соседей , и эта вершина будет в пути.

Получившаяся модель является нелинейной 0-1 моделью.

1.2 Алгоритмы решения

.2.1 Алгоритм локального поиска

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

На каждом шагу алгоритм рассматривал действия, которые могли в себя включать добавление ребра, удаление ребра или добавление одного и удаление другого.

Так как при больших значениях числа вершин в графе, количество действий на каждый шаг возрастает, а подсчет сложности жадного алгоритма затратен по времени, то были рассмотрены только симметричные решения. Поэтому если рассмотреть граф 4х4 (рис. 16) то, красным отмечены вершины, которые рассматриваются при выборе вершин для начала ребер для удаления или добавления, а пунктирные линии представляют собой линии симметрии. На рисунке 17 нарисованы примеры симметричных ребер это ребра 5-15, 8-14, 2-12 и 3-9.