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

Некоторые из этих моделей были использованы для построения P2P сетей с логарифмической сложностью поиска, например распределенная хэш-таблица (Distributed Hash Table). Поиск в этой модели осуществляется с помощью жадного алгоритма, где старт начинается в произвольной вершине, и переход осуществляется, основываясь только на локальной информации - информации о соседях. Вначале вся информация могла храниться в одном месте (сервере), и клиенты имели доступ с серверу и могли получать необходимую информацию. В одноранговых сетях все элементы являются равноправными, и поиск может начинаться с любого элемента и проходить через любые элементы. Так как для поиска в одноранговой сети нет центра, который знает где находится информация.Целью данной работы было проанализировать построенные оптимальные структуры и характер роста целевой функции.Жадному алгоритму на вход подается две вершины - начальная и финальная. Он рассматривает все вершины из соседей начальной, рассчитывает расстояние от них до финальной вершины и переходит в ту, от которой минимальное расстояние. Все это продолжается до тех пор пока мы не придем в вершину, расстояние от которой до финальной вершины будет минимально среди всех ее соседей. И запустить жадный алгоритм с начальной точкой 1 и финальной точкой 4, то алгоритм после рассмотрения соседей вершины 1, перейдет в вершину 2, как самую ближайшую. И в итоге не сможет найти вершину 4, так как из вершины 2 некуда двигаться.В своем подходе Клайнберг рассматривает точки на плоскости, которые представляют собой сетку размера . Тогда для того, чтобы жадный алгоритм мог найти необходимые вершины, начиная с любой, начальный граф должен иметь вид сетки, где каждая вершина соединена с вершиной слева, справа, сверху и снизу. Пример такого графа можно увидеть на рисунке 15. Поэтому Клайнберг решил проверить, а нельзя ли немного изменить структура графа и при этом ускорить поиск.Также проанализировать характер роста целевой функции. Целевая функция (4) представляет собой сумму сложностей всех жадных поисков от каждой вершины до каждой. Сложность в математической форме записана в (5) есть мощность множества вершин, которые являются соседями вершин, находящихся в пути жадного алгоритма. Ограничения (6) и (7) являются тривиальными, первое запрещает петли в графе, второе говорит, что начальная и финальная вершина обязательно должны быть в пути жадного алгоритма. Оно описывает, что если вершина находится в пути жадного алгоритма, то хотя бы один из ее соседей тоже должен будет там находиться.Алгоритм начинал работу с графа-сетки, а потом производил локально оптимальные действия на каждом шагу, до тех пор пока не достигнет локального минимума. На каждом шагу алгоритм рассматривал действия, которые могли в себя включать добавление ребра, удаление ребра или добавление одного и удаление другого. Так как при больших значениях числа вершин в графе, количество действий на каждый шаг возрастает, а подсчет сложности жадного алгоритма затратен по времени, то были рассмотрены только симметричные решения. 16) то, красным отмечены вершины, которые рассматриваются при выборе вершин для начала ребер для удаления или добавления, а пунктирные линии представляют собой линии симметрии. На рисунке 17 нарисованы примеры симметричных ребер это ребра 5-15, 8-14, 2-12 и 3-9.Для изменения алгоритма были добавлены новые входные параметры, такие как количество шагов алгоритма, на которое действие помещается в табу лист, и количество раз, когда алгоритм доходит до локального минимума без улучшений подряд. Этот алгоритм отличается от предыдущего тем, что при достижении локального минимума он не останавливается, а делает действие, которое меньше всего ухудшает целевую функцию, затем заносит действие обратное сделанному в табу лист и продолжает работу. Тем самым мы можем сдвинуться с локального минимума и перейти в другой локальный минимум. Теперь он ищет не самое оптимальное действие на каждом шаге, а первое действие, которое улучшает целевую функцию. Псевдокод работы этого алгоритма представлен ниже: Tabu(G) //G - графПосле получения результатов работы второго алгоритма, нужно было проверить предположение о существовании оптимального решения, которое содержит в себе только симметричные ребра. Так как и первый и второй алгоритм являются эвристическими, т.е. не дают гарантии нахождения глобально оптимального решения, то для проверки этой гипотезы был придуман метод ветвей и границ, который является точным алгоритмом, т.е. находит глобально оптимальное решение. Рассмотрим алгоритм подсчета нижней границы для релаксированной задачи с матрицей смежности (таблица 1) В таблице выше представлена матрица смежности графа с шестью вершинами, где 1 означает, что ребро есть; 0 означает, что ребра нет, но может быть проведено;-1 означает, что этого ребра не может быть в графе, построенном далее. Но когда алгоритм рассматривает соседей вершины, то он рассматривает не только те вершины, с которыми она соединена, но и те вершины, с которыми она может быть соедин

Содержание

Введение

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.

Рисунок 1 - Одноранговая сеть Рисунок 2 - Клиент-серверная сеть

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

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

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

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

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