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