Читать реферат по информационному обеспечению, программированию: "Алгоритм, эвристически строящий оптимальный граф для задачи децентрализованного поиска" Страница 1

(Назад) (Cкачать работу)

Содержание Введение

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. Этот алгоритм начинается с одного узла, потом передает информацию всем его соседям, и в каждом узле снова передает всем его соседям. Поэтому, если сеть связанная, то поиск точно сможет предоставить необходимую информацию.

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

Похожие работы