Том 21, номер 6, 2014 г., Стр. 35-50

УДК 519.8
Козин И. В., Полюга С. И.
Эволюционно-фрагментарная модель упаковки пентамино

Аннотация:
Рассматривается задача упаковки пентамино в плоские контейнеры произвольной формы. Введено понятие фрагментарной структуры. Показано, что задача упаковки пентамино может быть представлена как задача на фрагментарной структуре. Предложена эволюционная модель для отыскания оптимальных упаковок пентамино.
Ил. 4, табл. 1, библиогр. 16.

Ключевые слова: упаковка пентамино, фрагментарная структура, эволюционно-фрагментарная модель, эволюционный алгоритм.

Козин Игорь Викторович ¹
Полюга Светлана Игоревна ¹
1. Запорожский нац. университет,
ул. Жуковского, 66, 69063 Запорожье, Украина
е-mail: ains00@gmail.com, veta99@mail.ru

Статья поступила 16 января 2014 г.
Исправленный вариант — 26 июня 2014 г.

Литература

[1] Голомб С. В. Полимино. - М.: Мир, 1975. - 207 с.

[2] Гэри М. Р., Джонсон Д. С. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982. - 416 с.

[3] Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. - М.: Физматлит, 2003. - 432 с.

[4] Ильев В. П. Задачи на системах независимости, разрешимые жадным алгоритмом // Дискрет. математика. - 2009. - Т. 21, вып. 4. - С. 85–94.

[5] Козин И. В. Фрагментарные алгоритмы в системах поддержки принятия решений // Питання прикладної математики i математичного моделювання. - Днепропетровск, 2006. - С. 131–137.

[6] Козин И. В., Полюга С. И. О свойствах фрагментарных структур // Вiсник Запорiзького нацiонального унiверситету. Математичне моделювання i прикладна механiка. - 2012. - №1. - С. 99–106.

[7] Козин И. В., Полюга С. И. Использование ЭВФ-алгоритмов для задачи прямоугольного раскроя // Питання прикладної математики i математичного моделювання. - Днепропетровск, 2009. - С. 199–208.

[8] Мухачева А. С., Чиглинцев А. В. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя // Информ. технологии. Машиностроение. - 2001. - №3. - С. 27–32.

[9] Скопцов Ю. О. Основы эволюционных вычислений: Учеб. пособ. - Донецк: ДонНТУ, 2008. - 326 с.

[10] Стоян Ю. Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. - Киев: Наук. думка, 1986. - 266 с.

[11] Bjorner A., Ziegle G. M. Introduction to greedoids. - Cambridge: Cambridge Univ. Press, 1992. - 180 p.

[12] Chambers L. Practical handbook of genetic algorithms. - CRC Press, 2001. - Vol. 1. Applications. - 544 p.

[13] Holland J. H. Adaptation in natural and artificial systems. - Boston: MIT Press, 1992. - 217 p.

[14] Fletcher J. G. A program to solve the pentomino problem by the recursive use of macros // Commun. ACM. - 1965. Vol. 8, N10. - P. 621–623.

[15] White N. Theory of matroids. - Cambridge: Cambridge Univ. Press, 1986. - 153 p. (Encyclopedia of mathematics and its applications; Vol. 26.)

[16] Whitney H. On the abstract properties of linear dependence // Amer. J. Math. - 1935. - Vol. 57, N3. - P. 509–533.