Решение задач полного покрытия ираскроя на примере задачи пентамино с различными опциями с помощью алгоритма “Dancing Links”, а также его модификации. Программные решения задачи пентамино с ограниченными настройками. Разработка модификации алгоритма.
Аннотация к работе
ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «ВЫСШАЯ ШКОЛА ЭКОНОМИКИ» УТВЕРЖДАЮ Академический руководитель образовательной программы «Программная инженерия», профессор департамента программной инженерии, канд. техн. наук ПРОГРАММА СОСТАВЛЕНИЯ ФИГУР ИЗ ПЕНТАМИНО по направлению подготовки 09.03.04 «Программная инженерия» Доцент департамента программной инженерии, к.т.н., доцент Выполнил студент группы БПИ122 4 курса бакалавриата образовательной программы «Программная инженерия»Входные данные для задачи пентамино с формами, которые заведомо не могут быть заполнены................................................................................................................ Входные данные для задачи пентамино с неограниченным количеством различных объектов полимино......................................................................................... Модификация алгоритма “Dancing Links” для задачи раскроя .........................27 Входные данные для нестандартной задачи пентамино.................................... Модификация алгоритма “Dancing Links”....................................................................................................................................................................................... 45
5У этой задачи существует множество вариаций, например: ? форма для заполнения: стандартная прямоугольная или произвольная нестандартная; ? набор объектов для заполнения: заранее заданный или определяемый в ходе решения, только объекты пентамино или различные объекты полимино, используются ли повороты и зеркальные отражения объектов для заполнения, может ли один и тот же объект присутствовать в решении несколько раз; Самым быстрым вариантом решения этой задачи является алгоритм “Dancing Links”, в работе используется именно этот алгоритм. Решение задачи пентамино с различными вариациями может быть использовано для создания игры пентамино (рис. При анализе предметной области были найдены решения этой задачи и использование их в различных играх, но у всех существует ряд ограничений: ? невозможность использования произвольной формы для заполнения;В главе приводится описание основных задач и проблем, появившихся при реализации решения стандартной задачи пентамино, и подходы к решению.Задача полного покрытия (exact cover problem) - задача, при которой по заданному набору подмножеств множества Хнеобходимо определить те подмножества из этого набора, которые будут давать ровно по одному элементу из множества X. Часто данную задачу представляют в виде матрицы из нулей и единиц, где строка обозначает одно подмножество, а единица в n-ом столбце этой строки обозначает присутствие n-ого элемента из множества Хв этом подмножестве (рис. Тогда задача сводится к нахождению набора строк, которые будут давать ровно по одной единице в каждом столбце (рис. Решение задачи полного покрытия Для решения задачи полного покрытия используются следующие алгоритмы: Алгоритмы полного перебора - алгоритмы, проходящие по всем возможным решениям и определяющие те, которые подходят под условия задачи.Задача раскроя - задача, при которой из заранее заданного полотна нужны вырезать объекты заранее заданной формы так, чтобы минимизировать расходы. Задача пентамино с неограниченным набором различных объектов полимино на произвольной форме может являться одним из типов задачи раскроя, так как решает ту же задачу, только со специфическими условиями. Решение задачи раскроя с помощью алгоритма “Dancing Links” дало бы ускорение по сравнению с алгоритмами перебора, так как алгоритм “Dancing Links” использует собственную структуру данных, позволяющую ускорить работу алгоритма. Модификацией в алгоритме Dancing Links по сравнению с Algorithm Хявляется то, что до начала его работы должна создаваться новая структура данных по входной матрице нулей и единиц. Это изменение позволяет уменьшить количество шагов алгоритма, которые тратились на прохождение всех ячеек в исходной матрице и проверку значения в ячейке (нуль это или единица), так как алгоритм работает только с ячейками, в которых находится единица.Структура данных состоит из элементов Head и Node. При входных данных, состоящих из матрицы из 0 и 1: элементы Head находятся в дополнительной строке и отображают некое множество, которое необходимо покрыть. Каждая строка отображает некое подмножество, где 1 в i-том столбце означает, что в данном подмножестве есть элемент i. На местах 1 в строках создаются элементы Node. Данные элементы имеют следующие поля: Элементы NodeЭтот этап является стандартным и имеет небольшие различия, к примеру: различие по выводу найденного решения, различие по выбору столбца для начала работы алгоритма.Элемент в строке = Элемент в строке.Right Добавить строку в результат(Выбранный элемент.ROWNUMBER) Удалить строку из результата(Выбранный элемент.ROWNUMBER) Элемент в строке = Выбранный элемент.