Содержание
Введение
1. Обзор алгоритмов решения задачи
1.1 Точные методы
1.2 Генетический алгоритм
1.3 Жадный алгоритм
2. Жадный алгоритм
2.1 Описание алгоритма
2.2 Анализ точности приближения
2.3 Анализ вычислительной сложности
2.4 Программная реализация
2.5 Экспериментальная проверка корректности и быстродействия
Заключение
Список использованных источников
Нужна помощь в написании курсовой?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
Приложение 1
Приложение 2
Введение
алгоритм жадный вычислительный быстродействие
К задаче о покрытии сводятся многие известные задачи дискретной оптимизации: задачи стандартизации, упаковки и разбиения множества, задачао наибольшей клике, задача минимизации полинома от булевых переменных и др. Известна также и обратная сводимость задачи о покрытии к этим задачам.
На практике задачи о покрытии возникают при размещении пунктов обслуживания, в системах информационного поиска, при назначении экипажей на транспорте, проектировании интегральных схем и конвейерных линий и т. д. Задача о вершинном покрытии может использоваться при разработке систем контроля и наблюдения, в построении помехоустойчивых алгоритмов передачи информации, при диагностике оборудования и в других областях.
Цели работы
1. Проанализировать задачу о покрытии, дать её формальную постановку;
2. Рассмотреть методы решения задачи и их применения на практике;
3. Для одного из методов — жадного алгоритма — привести анализ точности, быстродействия и программную реализацию;
4. Подтвердить полученные в предыдущем пункте теоретические данные экспериментально;
Постановка задачи
Комбинаторная постановка задачи о покрытии множества состоит в следующем. Пусть даны множество. Требуется найти покрытие минимального суммарного веса. Задача называется невзвешенной, если все подмножества имеют единичные веса.
В качестве простого примера предположим, что нам нужно собрать команду для работы над проектом; каждый человек из выборки обладает ограниченным набором навыков. Мы хотим подобрать наименьшую группу людей, обладающих в совокупности всеми нужными навыками.
Нужна помощь в написании курсовой?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
Значительное внимание уделяется задачам о покрытиях в графе, в частности задаче о вершинном покрытии, которая может быть сформулирована следующим образом. Пусть называется вершинным покрытием, если каждое ребро из . Требуется найти вершинное покрытие минимального веса.
1. Обзор алгоритмов решения задачи
1.1 Точные методы
Для решения общей задачи о покрытии предложено большое число точных алгоритмов, основанных на методах ветвей и границ, отсечения, перебора L-классов и др.Верхние оценки временной сложности точных методов сопоставимы сосложностью переборных алгоритмов. В данной работе не приводятся в виду большой сложности анализа их работы
1.2 Генетический алгоритм
Генетический алгоритм представляет собой эвристический метод случайного поиска, основанный на принципе имитации эволюции биологической популяции. Сначала выбирается семейство покрытий, называемые родителями, и из покрытия , выделяется покрытие J, называемое их потомком. Потомок подвергается мутации (случайному изменению), после чего он замещает в Pнаихудшую особь. Этот цикл — выбор родителей, создание потомка, его мутация и обновление популяции — повторяется заданное число раз . Результатом работы алгоритма является наилучшее из покрытий, возникших в ходе развития популяции.Обе существующие модификации генетического алгоритма намного превосходят жадный алгоритм по весовым показателям получившихся покрытий, но по параметру трудоемкости жадный алгоритмвыигрывает с огромным отрывом. Если важна скорость вычислений, то в задачах небольшой размерности можно использовать жадный алгоритм..
1.3 Жадный алгоритм
Для задач о покрытии разработано значительное число приближенных алгоритмов с априорными оценками точности получаемых решений. Одним из первых приближенных алгоритмов, предложенных для невзвешенной задачи о покрытии, является жадный алгоритм.
2. Жадный алгоритм
2.1 Описание алгоритма
Жадный метод работает путем выбора на каждом этапе множества S, покрывающего максимальное количество элементов, оставшихся непокрытыми.
Листинг 1 — Псевдокод жадного алгоритма
Опишем принцип действия алгоритма [листинг 1]. На каждом этапе его работы множество содержит оставшиеся непокрытыми элементы. Множество содержит покрытие, которое конструируется. Строка 4 — это этаппринятия решения в жадном методе. Выбирается подмножество , покрывающее максимально возможное количество еще непокрытых элементов (с произвольным разрывом связей). После выбора подмножества . Когда алгоритм завершает свою работу, множество . В примере, проиллюстрированном на рис1, алгоритм GREEDY_SET_COVERдобавляет в семейство в порядке перечисления.
Рисунок 1 — Пример работы процедуры GreedySetCover [1]
Нужна помощь в написании курсовой?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
2.2 Анализ точности приближения
В общем случае, если на каком-то шаге осталось непокрытых элементов исходного множества этих элементов, то оптимальное решение будет содержать как минимум множеств. При помощи этого наблюдения можно доказать, что жадный алгоритм имеет степень точности.
Присвоим каждому из выбранных алгоритмом множеств стоимость 1, распределим эту стоимость по всем элементам, покрытым за первый раз, а потом с помощьюэтих стоимостей получим нужное соотношение между размером оптимального покрытия множества , возвращенного алгоритмом. Обозначим через подмножество, выбранное алгоритмом GREEDY_SET_COVER; добавление подмножества приводит к увеличению стоимости на 1. Равномерно распределим стоимость, соответствующую выбору подмножества , между элементами, которые впервые покрываются этим подмножеством. Пусть число элементов, покрытых на том же шаге вместе с Стоимость выделяется каждому элементу только один раз, когда этот элемент покрывается впервые.На каждом шаге алгоритма присваивается единичная стоимость, поэтому
Теперь рассмотрим элементы . Каждое данное подмножество содержит не более чем и мы можем, используя оптимальное решение, покрыть все элементы, включая элементы , наименьшим возможным числом множеств. В этом случае
Откуда получаем
Число [1] [2] [3]
2.3 Анализ вычислительной сложности
Поскольку количество итераций цикла в строках 3-6 (рис. 1) ограничено сверху величиной а тело цикла можно реализовать таким образом, чтобы его выполнение завершалось за время . [1]
2.4 Программная реализация
Для реализации алгоритма был выбран язык Python (версия интерпретатора 3.6.1). Этот язык был выбран из-за наличия в нем максимально подходящих с точки зрения автора работы для данной задачи структур данных, позволяющих довольно просто воплотить в коде нужные математические объекты: множества и подмножества.
Набор подмножествS и набор соответствующих им весовw реализован структурой данных список (List). Исходное множество Uпредставлено структурой данных словарь (Dictionary, по принципу действия является ассоциативным массивом) и собирается путем объединения вводимых пользователем подмножеств и их весов. Фактически, Uпредставляет собой отображение элемента на индекс того подмножества из S, которому оно принадлежит[приложение 1].
Поиск наиболее дешевого множества на очередной итерации осуществляется при помощи очереди с приоритетом, реализация её методов представлена в приложении 2.
2.5 Экспериментальная проверка корректности и быстродействия
Для исследования работы алгоритма при помощи сторонних библиотек были созданы целочисленные множества вида 0. В целом, анализ показал, что оценка, полученная в главе 2.3, выполняется приблизительно, некоторая неточность вызвана операцией поиска самого дешевого множества, использующей приоритетную очередь. Основываясь на полученных данных, более точной оценкой можно было бы назвать .
Рисунок 3 — График для U = 1000
Нужна помощь в написании курсовой?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
Рисунок 4 — График для U = 10
Для проверки корректности алгоритма при помощи сторонних библиотек были сгенерированы целочисленные множества вида [1..n]. Результаты тестирования приведены в таблице 1.12
Таблица 1 — Примеры входных и выходных данных
Была рассмотрена задача о минимальном покрытии множества: постановка, практическая значимость,методы решения. Для жадного алгоритма получено теоретическое обоснование временной оценки и точности, его программная реализация. Кратко рассмотрены другие подходы к решению задачи.
Список использованных источников
1. А. Ахо, Дж. Хопкрофт, Дж. Ульман Построение и анализ вычислительных алгоритмов — М.: Мир, 1979, — 536 с.
2. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: Построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2013. — 1227 с.
3. А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 2. С.22-46.
4. Еремеев, А. В. Генетический алгоритм для задачи о покрытии / А. В. Еремеев // Дискретный анализ и исследование операций. — 2000. — Т. 7, № 1. — С. 47-60.
Жадный алгоритм
importpriorityqueue= 999999(S, w):= {}
selected = list()= []
for index, item in enumerate(S):.append(set(item))
for j in item:
if j not in udict:[j] = set()[j].add(index)= priorityqueue.PriorityQueue()
Нужна помощь в написании курсовой?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
cost = 0= 0
for index, item in enumerate(scopy):
if len(item) == 0:.addtask(index, MAXPRIORITY)
else:.addtask(index, float(w[index]) / len(item))
while coverednum<len(udict):
a = pq.poptask().append(a)
cost += w[a]+= len(scopy[a])m in scopy[a]:
for n in udict[m]:
if n != a:[n].discard(m)
if len(scopy[n]) == 0:.addtask(n, MAXPRIORITY)
else:.addtask(n, float(w[n]) / len(scopy[n]))[a].clear().addtask(a, MAXPRIORITY)
returnselected, cost
Приложение 2
Очередь с приоритетом
Нужна помощь в написании курсовой?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
importitertoolsheapq import *PriorityQueue:__init__(self):
self._pq = []
self._entry_map = {}._counter = itertools.count()(self, task, priority = 0):
if task in self._entry_map:.removetask(task)
count = next(self._counter)
entry = [priority, count, task]
self._entry_map[task] = entry(self._pq, entry)(self, task):
entry = self._entry_map.pop(task)
entry[-1] = ‘removed'(self):
while self._pq:
priority, count, task = heappop(self._pq)
if task is not ‘removed’:
del self._entry_map[task]
return task__len__(self):
return len(self._entry_map)