Реализация алгоритма поиска локального в задаче размещения многоугольников

( 0 Votes ) 
Категория: ИКТМ 2013 Просмотров: 404

УДК 004.21: 519.8: 519.67


Реализация алгоритма поиска локального в задаче размещения многоугольников
К. С. Шамушкина, студент 355м группы
Национальный аэрокосмический университет им. Н.Е.Жуковского «ХАИ»


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


Задача, рассматриваемая в работе, принадлежит к классу задач нерегулярного размещения. Их общая задача состоит в поиске такого варианта расположения объектов, при котором заданный критерий качества размещения, например метрические характеристики области, достигает оптимума, а для размещаемых объектов выполняются ограничения на взаимное размещение (условие взаимных непересечений и ограничения на положение объекта в области размещения.
Интерес к множеству задач размещения вызван, с одной стороны, их сложностью и нетривиальностью математических моделей, необходимых для адекватного описания, а с другой стороны - широким спектром практических приложений.
Методами исследования были выбраны теория оптимизации и теория геометрического проектирования. Было выполнено построение и анализ математической модели исследуемой задачи. В результате была поставлена оптимизационная задача размещения объектов, на которые были наложены условия не пересечения и попадания в полосу. В рамках поставленной задачи были проведены исследования относительно реализации алгоритма разбиения невыпуклого многоугольника на его выпуклые части без добавления дополнительных вершин, а также относительно использования метода проекции градиента при решении поставленной задачи. Была выполнена оценка сложности алгоритма, а так же произведён численный эксперимент.
*Научный руководитель к.ф-м.н., доцент каф. 304 А.В. Карташов