Тема: Программная реализация алгоритма решения задачи о раскраске
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
📋 Содержание
Постановка задачи 3
Глава 1. Используемые термины 4
Глава 2. Условные обозначения 4
Глава 3. Вспомогательные алгоритмы и структуры данных 5
3.1. Битовые множества 5
3.2. Алгоритм Брона-Кербоша 6
Глава 4. Алгоритм Олемского 8
4.1. Описание множеств и переменных 8
4.2. Описание проверок 10
4.3. Описание алгоритма 11
4.4. Псевдокод алгоритма 15
Глава 5. Алгоритмы перебора независимых множеств 20
5.1. Перебор всех возможных вариантов 20
5.2. Оптимизированный перебор 21
5.3. Перебор в матричном виде 23
Глава 6. Измерение быстродействия алгоритмов 26
6.1. Алгоритм Олемского И.В 26
6.2. Алгоритм перебора независимых множеств 29
6.3. Оптимизированный перебор 32
6.4. Перебор в матричном виде 34
Глава 7. Сравнение быстродействия алгоритмов 36
Глава 8. Заключение 40
Список литературы 41
📖 Введение
Данная задача постоянно исследуется по двум основным причинам:
1. Она находит применение в реальных задачах, например в составлении расписаний[1], распределение регистров в микропроцессорах^], распараллеливание численных методов[3].
2. На данный момент не найдено точного и эффективного алгоритма её решения, т.к. доказано что задача о раскраске является NP-полной.
Точные алгоритмы в основном используют полный перебор возможных вариантов раскраски. Таким образом, основным отличием таких алгоритмов является порядок перебора и используемые отсечения.
Например, в данной работе рассматривается алгоритм основанный на переборе максимальных независимых множеств, описанный в книге Новикова Ф.А.[4] и две его модификации.
Главным объектом исследования является разработанный Олемким И.В. алгоритм, и его сравнение с другими существующими алгоритмами.
✅ Заключение
Для всех реализованных алгоритмов было измерено время работы на графах с различным число вершин и плотностью. Результаты были представлены в виде трёхмерного графика зависимости времени от числа вершин и плотности. По полученным результатам было решено провести прямое сравнение алгоритма Олемского И.В. и двух модификаций алгоритма Новикова Ф.А.
Сравнение показало, что алгоритм Олемского И.В. работает дольше на графах малой размерности. Однако имеет более низкую скорость прироста требуемого на раскраску времени. Поэтому при раскраске небольших графов с числом вершин менее 12 применение модифицированных алгоритмов Новикова Ф.А. предпочтительнее, но с ростом числа вершин алгоритм Олемского И.В. становится более рациональным выбором.
📕 Список литературы
🖼 Скриншоты
