Труды КНЦ (Технические науки вып.3/2025(16))

ограничений, введя достаточное количество вспомогательных переменных. Примером ограничения высшего порядка является ограничение alldiff [13], которое требует, чтобы все переменные задачи принимали различные значения. Процесс поиска решения состоит из двух чередующихся этапов: 1) распространение — общее название методов вывода на ограничениях, сводящихся к пошаговому удалению из доменов заведомо недопустимых значений. Изменения в доменах одних переменных по принципу «цепной реакции» приводит к усечению доменов других переменных. Когда пространство задачи больше нельзя сократить за счет распространения, используется ветвление; 2) ветвление. Суть процедуры ветвления заключается в разделении пространства задачи на подпространства меньшей размерности, соответствующие подзадачам. Одним из способов ветвления является присваивание рассматриваемой переменной выбранного значения и дальнейшее распространение для корректировки доменов остальных переменных. Путем чередования шагов ветвления и распространения каждой переменной задачи присваивается значение, которое является одним из решений задачи. В случае, когда в процессе поиска возникает противоречие (домен одной из переменных становится пустым), используется алгоритм поиска с возвратом, при котором осуществляется возврат из текущего состояния задачи до предыдущего непротиворечивого, и исследуется другая ветвь дерева поиска. Правило, устанавливающее, какую переменную и значение выбирать при ветвлении, называется эвристикой. Удачный выбор эвристики позволяет значительно сократить дерево поиска. Представление задачи генеративного дизайна как задачи удовлетворения ограничений В настоящей работе предлагается задачу генеративного дизайна представлять и решать в виде задачи удовлетворения ограничений. В качестве примера задачи генеративного дизайна здесь и далее рассматривается задача проектирования двумерной среды с учетом разнородных требований к взаимному расположению объектов среды. Для представления данной задачи в рамках задачи удовлетворения ограничений необходимо задать сеть ограничений. В качестве переменных в задаче выступают объекты, которые необходимо расположить в двумерном пространстве. В работе двумерное пространство представлено в виде прямоугольной сетки, разделенной на пронумерованные клетки (ячейки) одинакового размера. Объект описывается в виде набора клеток пространства, а также параметров длины и ширины. Каждое значение домена переменной — это номер клетки, в которой может размещаться верхняя левая клетка объекта. Ниже приведено графическое представление пространства, объекта и его домена (рис. 1). Труды Кольского научного центра РАН. Серия: Технические науки. 2025. Т. 16, № 3. С. 117-130. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2025. Vol. 16, No. 3. P. 117-130. Недоступная клетка пространства 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 Клетка домена переменной соответствующего объекта Рис. 1. Графическое представление двумерной сцены, объекта и его домена Серым на рис. 1 отмечены клетки, которые нельзя занимать, в данном случае это только границы пространства, но незанимаемые клетки могут располагаться и внутри пространства. Белым отмечены свободные клетки, в которых можно расположить клетки объектов. Синим отмечены клетки объекта, а темно-синим — клетка, относительно которой объект ставится в пространстве. Зеленым отмечены клетки, в которые можно поставить показанный на рис. 1 объект верхней левой клеткой. © Таран П. В., Зуенко А. А., 2025 119