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

Главная

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

Задача об оптимальном графе для децентрализованного поиска. Жадный алгоритм. Модель Клайнберга. Математическая модель. Алгоритмы решения. Алгоритм локального поиска. Табу алгоритм. Метод ветвей и границ. Выбор между одинаковыми соседями. Стартовый граф.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
GreedyWalk (,)//-начальная вершина, - искомая вершина
Жадному алгоритму на вход подается две вершины - начальная и финальная. Он рассматривает все вершины из соседей начальной, рассчитывает расстояние от них до финальной вершины и переходит в ту, от которой минимальное расстояние. После этого такие же операции проводит с текущей вершины. Все это продолжается до тех пор пока мы не придем в вершину, расстояние от которой до финальной вершины будет минимально среди всех ее соседей.
Такой алгоритм в общем случае не дает точной гарантии нахождения финальной вершины от любой. См. рисунок 3.
Размещено на http://www.allbest.ru/
Если использовать в качестве функции расстояния Евклидово расстояние на плоскости. И запустить жадный алгоритм с начальной точкой 1 и финальной точкой 4, то алгоритм после рассмотрения соседей вершины 1, перейдет в вершину 2, как самую ближайшую. И в итоге не сможет найти вершину 4, так как из вершины 2 некуда двигаться.
Для того, чтобы избежать такой ситуации исходный граф должен иметь определенную структуру, такая структура может быть построена с помощью разбиения Вороного. Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
Рассмотрим пример набора точек на плоскости с Евклидовым расстоянием.
На рисунке 4 можно заметить, что любая точка, попавшая в какую-либо область, всегда будет ближе к точке, породившей эту область, чем к любой другой.
После того, как алгоритм разбил плоскость с помощью разбиения Вороного, соединяем ребрами те вершины, которые имеют общую границу.
Рисунок 5 - граф после соединения вершин
После построения всех необходимых ребер, получаем граф, в котором жадный алгоритм всегда найдет нужную вершину, начиная с любой. Такой граф называется графом Делоне.
При запуске жадного поиска от какой-либо вершины, мы какое-то количество раз вызываем функцию подсчета расстояний от одной вершины до другой. Назовем сложностью поиска одной вершины от другой количество вызовов функции подсчета расстояния. Рассмотрим пример поиска вершины 15, от вершины 1 на графе с рисунков 6 - 13.
Рисунок 8- выбор после первого шага
Поиск начинается с подсчета расстояния от начальной вершины до финальной . Потом мы рассматриваем соседей начальной вершины 1 - это вершины 2 и 6 и считаем расстояния от них Так как наименьшее расстояние у вершины 2, то идем в вершину 2 (рисунок 8). Следующим шагом рассматриваем соседей вершины 2. Продолжаем до тех пор, пока не дойдем до вершины 15. В этом поиске мы столкнулись с неопределенностью на шаге номер 3 (рисунок 10). Расстояние от 4 и от 8 вершины одинаково. Возникает вопрос - какую вершину выбирать. На этот вопрос мы ответим при описании нашего алгоритма.
После того, как мы нашли финальную вершину, надо посчитать сложность поиска. Сложность поиска равна 12. На рисунке 14 красными вершинами отмечен путь жадного алгоритма, который включает в себя 7 вершин, и 5 синих вершин, которые не входят в жадный путь, но при этом использовались жадным алгоритмом, поэтому они вносят свой вес в сложность алгоритма.
При такой структуре графа жадный поиск выполняется за , где . В нашем примере
Поэтому Клайнберг решил проверить, а нельзя ли немного изменить структура графа и при этом ускорить поиск. Оказалось, что можно. В своей модели он в существующую структуру сетку добавляет дополнительные ребра следующим образом:
В формуле (1) - коэффициент кластеризации. Такой способ добавления ребер позволяет ускорить жадный поиск в среднем до .
Иногда в формуле (1) вместо коэффициента кластеризации используется просто вводимый пользователем параметр, и в зависимости от него граф может менять свой вид.
Например, при большом q, вероятность уменьшается с увеличением расстояния. Если же q мало, то вероятность длинных ребер возрастает.
Рисунок 16 - Вершины для выбора начала ребер
Принцип построения таких ребер описан ниже:
1. У нас есть одно ребро с началом в вершине , а концом в вершине .
2. Для построения симметричного ребра считаем его начало и конец
В примере на рисунке 17 , тогда , получается ребро 3-9.
, получаем ребро 5-15. И последнее ребро 8-14. Таким образом при добавлении или удалении ребра a-b, происходит удаление или добавление от 0 до 3х симметричных ему ребер.
При использовании этого предположения количество вариантов изменения решения на каждом шаге заметно сокращается, поэтому локальный поиск приходит к локально оптимальному решению значительно быстрее.
Ниже представлен псевдокод этого алгоритма:
25. add reverse tabu_action to tabu list for number_of_tabu steps
В этом алгоритме на первом шаге идет проверка табу листа, во-первых, на уменьшение для каждого элемента количество шагов в табу листе, во-вторых, удаление тех элементов, счетчик которых достиг нуля.
Так же изменения произошли в первом цикле. Во-первых, выбирается не самое оптимальное действие, как говорилось ранее, а первое действие, которое приносит улучшение. Во-вторых, при выборе действия проверяется не лежит ли оно в табу, тем самым это помогает нам не возвращаться обратно в тот же локальный минимум. Однако если действие, которое лежит в табу листе, все же улучшает решение до такого, что оно лучше самого лучшего известного, то это действие совершается и удаляется из табу списка.
Небольшие отличия от предыдущего алгоритма есть в моменте после нахождения локального минимума. Во-первых, идет проверка улучшили мы или нет текущее оптимальное, если да, то алгоритм сохраняет новое оптимальное, обнуляет количество неудач (fails) и продолжает работу. Если же алгоритм не нашел решение лучшее, чем текущее оптимальное, то количество неудач увеличивается на 1, сравнивается с глобальным параметром. Если количество неудач сравнялось с фиксированным числом, то алгоритм останавливается. Если алгоритм не остановлен, то программа находит действие, которое приводит к наименьшему ухудшению целевой функции. Делает его и добавляет обратное действие в табу список на определенное количество шагов.
Рисунок 18 - Ветвление в методе ветвей и границ
Таким образом это дерево представляет собой все возможные варианты существующих графов. Для того, чтобы не рассматривать все решения, используют границы. На каждом шаге идет подсчет нижней границы для определения наименьшего возможного значения целевой функции для текущего релаксированного графа.
Рассмотрим алгоритм подсчета нижней границы для релаксированной задачи с матрицей смежности (таблица 1)
В таблице выше представлена матрица смежности графа с шестью вершинами, где 1 означает, что ребро есть; 0 означает, что ребра нет, но может быть проведено; -1 означает, что этого ребра не может быть в графе, построенном далее.
При вычислении нижней границы для такой матрицы смежности алгоритм выполняет жадный поиск от каждой вершины до каждой. Но когда алгоритм рассматривает соседей вершины, то он рассматривает не только те вершины, с которыми она соединена, но и те вершины, с которыми она может быть соединена (те, где 0 в матрице), при этом игнорирует вершины, с которыми нет возможности соединиться (где -1 в матрице). Однако при подсчета сложности поиска от одной вершины до другой в сумму целевой функции входят только те вершины, до которых есть ребро. Например, если мы рассмотрим вторую вершину у нее 2 соседа (1 и 4) и 3 возможных соседа (3,5 и 6). При поиске от нее алгоритм рассмотрит все 5 вершин и выберет ту, которая ближе к финальной точке, но при этом в целевую функцию внесет только 2 единицы.
При проведении жадного поиска от одной вершины до другой может появится случай, когда у алгоритма будет несколько вершин с одинаковым расстоянием до финальной точки. Возникает вопрос, какую вершину выбрать для продолжения пути. В нашем алгоритме есть входной параметр, который отвечает за способ выбора одной вершины из множества одинаковых.
Эта переменная может принимать три значения:
· 0 - выбираем вершину с наименьшей степенью. Таким образом она внесет наименьший вклад в целевую функцию, что улучшит решение.
· 1 - выбираем вершину с наибольшей степенью. Хоть она и внесет в целевую функцию максимально возможный вклад, но при этом из нее можно будет рассмотреть наибольшее количество вершин для дальнейшего пути, что может сократить поиск.
Рассмотрим на примере, как изменится значение сложности жадного поиска.
Рисунок 20 - выбор следующей вершины
На рисунке 20 видим, что расстояние от вершины 4 до вершины 15 равно расстоянию от вершины 8 до 15, таким образом мы используем входной параметр для определения следующей вершины. Если он равен 0, то выбирается вершина 4, так как она имеет степень 3 4 - степени вершины 8. Если он равен 1, то выбирается вершина 8. Если он равен 2, то с вероятностью 0.5 выбирается вершина 4, с вероятностью 0.5 выбирается вершина 8.
Различный выбор будет влиять на путь и значение целевой функции. На следующих рисунках показано, как выглядит пути в каждом из двух случаев.
Теперь можно посчитать сложность поиска от вершины 1 до вершины 15. В первом случае сложность равна 12, во втором случае - 13.
Рисунок 23 - Переменные класса Graph
Edge представляет собой структуру данных, которая содержит в себе начало ребра (start), конец ребра (finish), количество шагов алгоритма, на которое это ребро помещается в табу список (tabuSteps) и действие, которое запрещено делать (tabuAction).
Также алгоритм принимает на вход файл конфигурации, который содержит в себе параметры для алгоритмов. Эти параметры отвечают за количество fails в табу алгоритме, количество табу шагов, на которое ребро помещается в табу список и способ перехода к следующему шагу алгоритма (в локальном и табу алгоритме). Способ перехода либо выбираем самое лучшее действие из всех локальных переходов, либо первое действие, который уменьшает нашу целевую функцию.
Рисунок 61 - L1, 0, 13356 c полного
Рисунок 62 - L2, 2, 13452 с полного
Рисунок 63 - LI, 0, 13882 и с полного и с сетки
Рисунок 64 - L1, 0, 28177 с полного
Рисунок 65 - L2, 0, 29095 с полного
Рисунок 66 - LI, 0, 29498 с полного
Для метода ветвей и границ на вход были поданы матрицы меньших размеров, так как этот алгоритм ищет точное оптимально решение и это занимает много времени. Тесты проводились на этом алгоритме, чтобы проверить корректность предположения, что среди всех оптимальных решений обязательно найдется хотя бы одно, которое содержит в себе только симметричные ребра.
Рисунок 68 - оптимальный граф для 2х4
Рисунок 69 - оптимальный граф для 2х6
Можно заметить, что для графов 2х3, 2х4 и 2х5 получившиеся оптимальные графы являются симметричными, однако для 1х11 уже возникает несимметричное решение. При этом симметричное все же присутствует. Однако не всегда так. Рассмотрим следующие результаты для 3х4.
Получившиеся решения не симметричны, однако для каждого несимметричного есть симметричное ему другое несимметричное решение. Таким образом гипотеза, что всегда есть симметричное решение не подтвердилась, поэтому нужно либо отказываться от симметричности и перебирать все ребра, либо находить такой способ, чтобы при жадный поиск строил симметричные пути.
Также табу алгоритм был запущен на графах с 1х4 до 1х42 и с 2х2 до 2х25, по результатам работы были построены графики зависимости сложности поиска от количества вершин. Результаты приведены на следующих рисунках.
Рисунок 85 - Сложность поиска от количества вершин для 1х
Рисунок 86 - Сложность поиска от количества вершин для 2х
Для того, чтобы понять какая зависимость представлена на графике, то построим зависимость сложности от квадрата логарифма количества вершин.
Рисунок 87 - Сложность от квадрата логарифма количества вершин для 1х
Рисунок 88 - Сложность от квадрата логарифма количества вершин для 2х
Можно заметить, что сложность поиска для таких графов будет .
Построим зависимость сложности от количества вершин для графов 2х2, 3х3, 4х4, 5х5, 6х6, 7х7, 8х8, 9х9.
Рисунок 89 - Сложность поиска от количества вершин для nxn
Рисунок 90 - Сложность поиска от квадрата логарифма количества вершин для nxn
Можно заметить, что тут также присутствует сложность поиска .
1. Milgram, Stanley. "The small world problem." Psychology today 2, no. 1 (1967): 60-67.
2. Maymounkov, Petar, and David Mazieres. "Kademlia: A peer-to-peer information system based on the xor metric." In Peer-to-Peer Systems, pp. 53-65. Springer Berlin Heidelberg, 2002.
3. Beaumont, Olivier, Anne-Marie Kermarrec, Loris Marchal, and Etienne Riviere. "VoroNet: A scalable object network based on Voronoi tessellations." In Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International, pp. 1-10. IEEE, 2007.
4. Kleinberg, Jon. "The small-world phenomenon: An algorithmic perspective." In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 163-170. ACM, 2000.
5. Watts, Duncan J., and Steven H. Strogatz. "Collective dynamics of `small-world'networks." nature 393, no. 6684 (1998): 440-442.
6. Bollobбs, Bйla, and Oliver Riordan. "The diameter of a scale-free random graph." Combinatorica 24, no. 1 (2004): 5-34.
Описание алгоритма сортировки с двоичным включением, выбор структур данных. Пример сортировки массива, отсортированного случайным образом. Алгоритм покрытия по методу "Построение одного кратчайшего покрытия". Волновой алгоритм поиска длиннейшего пути. курсовая работа [78,2 K], добавлен 24.09.2010
Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов. курсовая работа [43,8 K], добавлен 19.10.2010
Алгоритм поиска по первому наилучшему совпадению на графе. Основные классы для поиска пути в лабиринте. Тестирование нахождения кратчайшего пути в лабиринте. Порядок обхода вершин. Тестирование поведения программы при отсутствии пути в лабиринте. курсовая работа [888,7 K], добавлен 19.12.2013
Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ. презентация [441,5 K], добавлен 19.10.2014
Задача о кратчайшем пути как одна из важнейших классических задач теории графов. Общий обзор трех наиболее популярных алгоритмов для решения задачи о кратчайшем пути. Написание программы, которая реализует алгоритм Дейкстры и алгоритм Форда-Беллмана. курсовая работа [2,1 M], добавлен 23.06.2014
Представление задач в виде графов AND/OR, примеры. Задача с ханойской башней. Формулировка процесса игры в виде графа. Основные процедуры поиска по заданному критерию. Эвристические оценки и алгоритм поиска. Пример отношений с определением задачи. лекция [154,6 K], добавлен 17.10.2013
Понятие алгоритма как набора инструкций, описывающего порядок действий. Поиск в ширину - метод обхода графа и поиска пути в нем. Пример работы алгоритма поиска в ширину, его неформальное и формальное описание. Реализация с помощью структуры "очередь". курсовая работа [684,8 K], добавлен 05.04.2015
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Алгоритм, эвристически строящий оптимальный граф для задачи децентрализованного поиска дипломная работа. Программирование, компьютеры и кибернетика.
Как Осмысливать Философские Учения Эссе
Клише Для Итогового Сочинения Со
Реферат: Виды финансово экономического контроля
Учение Йоги В Древней Индии Реферат
Реферат по теме Эпоха возрождения, титаны ренессанса
Курсовая работа по теме Зобов’язальне право, основні його види, їх характеристика
Прибыль Предприятия Эссе
Реферат: Физическое воспитание в средних специальных учебных заведениях
Реферат по теме Constitutional stipulation of freedom of a person
Эссе Мечта
Реферат На Тему Искусство И Религия
Курсовая работа: Правовые системы стран мира
Сочинение По Пословице В 6 Классе
Контрольная работа по теме Экспертные методы в психодиагностике
Дипломная работа: Детские передачи на Казахстанском телевидении. Скачать бесплатно и без регистрации
Реферат по теме Захаров Марк Анатольевич
Реферат по теме Процесс становления личности
Техническое Обслуживание Дипломная Работа
Курсовой Проект На Тему Булочка С Маком
Преимущества И Недостатки Рыночной Экономики Реферат
Офіційна позиція США щодо визнання незалежності Абхазії та Південної Осетії - Политология статья
Сущность и значение процессов профилактики и предотвращение возникновения конфликтов - Менеджмент и трудовые отношения курсовая работа
Сказки Екатерины ІІ - Литература курсовая работа