книги / Математическая логика и теория алгоритмов. Анализ алгоритмов

6. На интервале (0; Vmax] выбрать несколько значений V1, V2, …, Vn. Для каждого значения Vi запустить серию тестов на автоматически сгенерированных входных данных объема Vi. В каждой серии тестов определять следующие характеристики:

а) для каждого алгоритма – среднее время работы (в мс); б) для каждого приближенного алгоритма – процент тес-

тов, в которых его решение совпало с точным решением; в) для каждого приближенного алгоритма – среднее отно-

сительное отклонение приближенного решения от точного, то

есть среднее значение выражения		f f *		, где f – характери-
		f *

стика приближенного решения, f* – точного.

7.Для нескольких значений Vi вручную или автоматизированно составить такие входные данные, которые соответствуют «худшему случаю» (когда количество выполняемых операций должно быть максимальным), а также входные данные, которые соответствуют «лучшему случаю» (когда количество операций должно быть минимальным). Провести тесты с полученными данными, определив время работы алгоритма.

8.Экспериментально определить приблизительное время выполнения одной элементарной условной операции (ЭУО) на используемом компьютере.

Примечание. Данный шаг можно выполнить после выполнения шага 9, сравнивая теоретическое значение функции сложности (в количестве ЭУО) с экспериментальными данными (в мс). Если на шаге 9 определен только порядок роста функции сложности, то данный шаг можно совместить с подбором констант, выполняемым в шаге 9.

Математическая часть

9.Для каждого из реализованных алгоритмов построить функцию сложности (при необходимости – максимальную, минимальную и среднюю оценки сложности). В случае затруднения с нахождением точных функций необходимо определить

141

порядок роста функции сложности, а затем, считая, что если f (x)~O(g(x)), то f (x) C g(x), экспериментальным путём

подобратьприближенноезначениесоответствующейконстантыC.

10.Для тех приближенных алгоритмов, которые имеют фиксированную погрешность, – проверить, во всех ли проведенных тестах показатель п. 6в не превышает её.

Теоретико-отчетная часть

11.Составитьотчет,содержащийследующуюинформацию: а) титульный лист с указанием имён и фамилий всех чле-

нов группы; б) название и описание решаемой задачи;

в) в случае если формат входных данных отличается от рекомендованного, – описание формата;

г)краткоеописаниефактическиреализованныхалгоритмов; д) ссылка на созданную программу (исходный код про-

граммы прикладывается к отчету в электронном виде); е) теоретические оценки сложности реализованных алго-

ритмов (результат выполнения пункта 9); ж) использованный язык программирования и среда раз-

работки; з) характеристики оборудования, использованного для

тестирования (процессор, тактовая частота, объем памяти); и) значение Vmax (пункт 5);

к) на основе значений, полученных в пунктах 6 и 7, а также оценок, полученных в пункте 9, построить графики зависимости времени работы программы от объема входных данных;

л) вывод о соответствии экспериментальных данных и теоретических оценок (на основе построенных графиков); в случае существенных отклонений или других аномальных результатов – возможные объяснения наблюдаемых эффектов;

м) на основе данных, полученных в пункте 6, построить таблицу: для каждой серии тестов указать количество тестов в серии, атакже для каждого алгоритма указать значения характеристик

пп. 6а–6в;

142

н) результат проверки на не превышение фиксированной погрешности (пункт 10);

о) заключение: вывод о проделанной работе, вывод о применимости реализованных алгоритмов.

Презентационная часть

12.Составить презентацию по материалам отчета, подготовить выступление на 10–15 минут.

13.Выступить с презентацией на паре.

Задача. Задача о вершинном покрытии минимальной мощности.

Имеется граф G. Требуется найти множество вершин U, образующих вершинное покрытие графа G, при этом количество вершин в U должно быть минимальным. Напомним, что подмножество U вершин графа называется вершинным покрытием, если каждое ребро графа инцидентно хотя бы одной из вершин, принадлежащих U.

На входе дано число вершин в графе (n) и сам граф в виде матрицы смежности.

На выходе необходимо получить количество вершин в найденном вершинном покрытии, а также сам список вершин.

Алгоритмы:

а) Точный переборный. Алгоритм заключается в переборе всех возможных 2n наборов вершин. Каждый набор проверяется, является ли он вершинным покрытием. Из тех наборов, которые являются вершинными покрытиями, выбирается тот, в котором меньше всего вершин;

б) Приближенный алгоритм с фиксированной погрешностью. Алгоритм состоит из следующих шагов:

1)Выбрать произвольное ребро (u, v).

2)Добавить вершины u и v в вершинное покрытие.

3)Удалитьизграфавсеребра,инцидентныевершинамu иv.

4)Если в графе еще остались ребра, перейти к шагу 1, иначе – завершить алгоритм;

143

в) «Жадный» алгоритм. Назовем ребро «покрытым», если хотя бы один из его концов принадлежит множеству U, и «непокрытым» в противном случае. Алгоритм состоит из следующих шагов:

1)Начнём с пустого множества U.

2)Выберем вершину, которой инцидентно наибольшее количество «непокрытых» ребер. Добавим выбранную вершину

вмножество U.

3)Если в графе остались «непокрытые» ребра, перейдем к шагу 2, иначе – алгоритм завершен, множество U является вершинным покрытием.

Решение.

Пример отчета, представляющего решение указанной задачи, представлен в приложении А.

Задачи для самостоятельной работы

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

9. Задача об оптимальной одномерной упаковке («об упаковке в контейнеры»).

Дано: число предметов (n), вместимость одного контейнера (M), а также n чисел – массы предметов (mi). Все числа положительные. Каждое mi M.

Получить: количество использованных контейнеров, а также распределение предметов по контейнерам (для каждого контейнеранужноперечислитьномерапредметов,сложенныхвнего).

Алгоритмы:

а) переборный (например, перебрать все возможные n! перестановок предметов, к каждой применяя алгоритм FF «первый подходящий»);

б) FFS (или любой другой приближенный с фиксированной погрешностью)

144

10. Задача «о рюкзаке».

Дано: в первой строке записано число предметов (n) и вместимость рюкзака (M), во второй записаны n чисел – массы предметов (mi), в третьей строке записаны n чисел – стоимости предметов (ci). Все числа положительные. Каждое mi M.

Получить: максимальную суммарную стоимость предметов, которые можно положить в рюкзак, а также список предметов в виде последовательности их номеров.

Алгоритмы:

а) итерационный полный перебор (перебрать все возможные 2n масок);

б) «жадный» (предметы сортируются по ценности (ci / mi), и на каждом шаге выбирается самый ценный из оставшихся, помещающийся по массе).

11. Задача о правильной раскраске графа в минимальное количество цветов.

Дано: число вершин в графе (n) и сам граф в виде матрицы смежности.

Получить: правильная раскраска графа с использованием минимального количества цветов (вывести количество использованных цветов, а также список пар «номер вершины – номер цвета»).

Алгоритмы:

а) полный перебор (перебрать все возможные способы раскраски);

б) приближенный «жадный» (отсортировать вершины по степени и красить по порядку в первый доступный цвет).

145

ОТВЕТЫИСОВЕТЫ

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 4 ПРАКТИЧЕСКАЯ РАБОТА ПО ИССЛЕДОВАНИЮ

ИСРАВНЕНИЮ СЛОЖНОСТИ АЛГОРИТМОВ

1.Теоретическая оценка сложности алгоритма заключается в построении функции сложности алгоритма на основе формального описания этого алгоритма. Под функцией сложности

понимается такая функция t (V), значение которой равно количеству элементарных операций, выполняемых алгоритмом при входных данных объемом V.

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

Одной теоретической оценки обычно недостаточно по следующим причинам:

1)теоретическая оценка не учитывает различное время выполнения различных элементарных операций, поэтому не позволяет определить абсолютное время выполнения алгоритма на конкретной архитектуре;

2)теоретическая оценка не учитывает различных «накладных расходов», поэтому даёт большую погрешность при сравнении алгоритмов на небольших объемах входных данных.

Одной экспериментальной оценки тоже, как правило, недостаточно по следующим причинам:

1)экспериментальные данные сложно (или даже невозможно) экстраполировать, поэтому на основе этих данных невозможно сравнить алгоритмы на тех входных данных, на которых они не тестировались (главным образом на входных данных большого объема);

146

2) экспериментальные данные зависят от реализации алгоритма, поэтому в случае ошибочной реализации могут дать искаженное представление о сложности собственно алгоритма.

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

2.Пусть в задаче рассматривается некоторое множество возможных решений, при этом существует целевая функция, которая каждому возможному решению ставит в соответствие вещественное число – характеристику этого решения. Тогда задача нахождения экстремума (минимума или максимума) такой функции является задачей оптимизации.

Известной NP-полной задачей оптимизации является, например, задача о гамильтоновом цикле кратчайшей длины («задача коммивояжера»). Дано: взвешенный граф G. Найти: гамильтонов цикл в графе G, длина которого минимальна. В данном случае возможными решениями являются различные гамильтоновы циклы в графе, а целевой функцией – функция вычисления длины цикла.

3.Одним из универсальных подходов является использование «жадной» стратегии (так называемые «жадные» алгоритмы). Её суть заключается в пошаговом решении задачи и выборе на каждом шаге локально-оптимального решения. Например, «жадный» алгоритм существует для указанной выше «задачи коммивояжера». Другим универсальным подходом является использование эвристических, в том числе генетических, алгоритмов. Такие алгоритмы основываются на использовании некоторых правил и закономерностей, истинность которых строго не доказана (а чаще всего даже, наоборот, нарушается на отдельных примерах), но хорошо зарекомендовавших себя на практике либо имеющих неформальные рациональные доводы в пользу своей корректности.

4.Задача об оптимальной одномерной упаковке («об упаковке в контейнеры») заключается в следующем. Имеется не-

147

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

Более формальная постановка задачи. Дано число предметов (n), грузоподъемность контейнеров (M), а также n чисел – массы предметов (mi). Все числа положительные. Каждое mi M, i = 1..n. Найти разбиение множества всех предметов (множе-

ства	V = {1, 2, …, n}) на подмножества: V V1 V2
Vk (Vi	Vj `,i j). При этом i		: mj M , k min.
		1,k
			j Vi

Для решения данной задачи существуют следующие алгоритмы:

а) Приближенный алгоритм FF (First Fit, первый подходящий). Суть алгоритма заключается в том, что все предметы просматриваются по порядку. Для каждого предмета контейнеры также просматриваются по порядку, начиная с первого, до тех пор, пока не будет найдет контейнер, куда этот предмет помещается.

б) Приближенный алгоритм FFS (First Fit with Sort, первый подходящий в отсортированном списке). Суть алгоритма заключается в том, что предметы вначале сортируются по убыванию массы, а затем к полученному отсортированному списку применяется алгоритм FF. Алгоритм FFS имеет фиксированную

погрешность. Доказано, что kFFS 119 k* 4, где kFFS – количест-

во контейнеров, которое получается в результате применения алгоритма FFS, а k* – оптимальное количество контейнеров.

в) Точный переборный. Алгоритм заключается в переборе всех возможных n! перестановок предметов, к каждой из которых применяется алгоритм FF «первый подходящий». Как ми-

148

нимум, одна из перестановок даст оптимальное количество контейнеров.

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

Более формальная постановка задачи. Дано число предметов (n), грузоподъемность рюкзака (M), а также 2n чисел – массы предметов (mi) и стоимости предметов (ci), i = 1..n. Найти во множестве всех предметов V = {1, 2, …, n} подмножество:

U V : mj M , cj max.

j U

j V

Для решения данной задачи существуют следующие алгоритмы.

а) Приближенный «жадный» алгоритм. Суть алгоритма заключается в том, что все предметы сортируются по убыванию удельной ценности (величины ci/mi), а затем просматриваются по порядку. Если очередной предмет «влазит» в рюкзак (не приводит к превышению грузоподъемности), то он складывается в рюкзак, иначе – пропускается.

б) Точный переборный. Алгоритм заключается в переборе всех возможных 2n наборов предметов. Каждый набор проверяется, не превышает ли суммарная масса предметов в этом наборе грузоподъемность рюкзака. Из тех наборов, которые удовлетворяют этому условию, выбирается тот, в котором суммарная стоимость предметов максимальна.

6. Задача о правильной раскраске графа в минимальное количество цветов заключается в следующем. Дан граф G. Необходимо «правильно раскрасить граф» (то есть для каждой вершины графа G найти число – «цвет вершины» так, чтобы «цвета» любых двух смежных вершин были различны), использовав при этом минимально возможное количество различных «цветов».

149

Более формальная постановка задачи. Даны число вершин вграфе (n), а также сам граф G, состоящий из множества вершин V и множества ребер E. Найти функцию :V {1..k} такую, что

(u,v) E : (u) (v), и при этом число k минимально.

Для решения данной задачи существуют следующие алгоритмы.

а) Полный перебор. Алгоритм заключается в переборе всех возможных вариантов «раскраски» графа. Вершине V1 сопоставим цвет 1 ( (V1) = 1). Для вершины V2 рассмотрим два варианта:(V2) = 1 и (V2) = 2, для вершины V3 – три варианта и так далее. Из тех функций, которые удовлетворяют условию «правильности раскраски», выбирается та, в которой использовано минимальное количество цветов.

б) Приближенный «жадный» алгоритм. Суть алгоритма заключается в следующем. Из еще неокрашенных вершин выберем вершину с максимальной степенью и сопоставим с ней минимально возможный цвет (с учетом того, чтобы выполнялось условие «правильности раскраски»). Данный шаг повторяется до тех пор, пока не будут окрашены все вершины.

7.f1(n) O(n4), f2(n) O(2n ) . Порядок роста выше у функ-

цииf2.

8.Наиболее эффективным является алгоритм 2, так как

порядок роста его функции сложности наименьший. Наименее эффективным является алгоритм 3. Нет, утверждать что алгоритм 2 всегда будет работать быстрее, чем алгоритм 3, нельзя. Порядок роста не показывает абсолютное значение функции сложности, поэтому на небольших значениях n алгоритм 3 может оказаться быстрее.

150