МОДИФИКАЦИЯ ВЕНГЕРСКОГО АЛГОРИТМА ДЛЯ ПРИМЕНЕНИЯ ПРИ РАЗМЕЩЕНИИ РАСТЕНИЙ В ЛАНДШАФТНЫХ КОМПОЗИЦИЯХ

АННОТАЦИЯ

Статья описывает возможности применения и модификации венгерского алгоритма для размещения растений при формировании ландшафтных композиций.

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

Венгерский алгоритм изначально был разработан для решения задачи назначения, где нужно сопоставить объекты из двух множеств (например, работников и задачи) с минимальными затратами. Однако в задаче размещения растений в зонах имеются дополнительные особенности, требующие модификации алгоритма. Эти изменения направлены на учет специфики характеристики зон и растений, а также обеспечение гибкости под задачи ландшафтного проектирования.

У каждой зоны и растения есть M характеристик (например, потребность в освещении, тип почвы, влажность). В отличие от классической задачи назначения, стоимость не фиксирована, а должна вычисляться на основе нескольких параметров. Таким образом, венгерский алгоритм нуждается в модификации в виде добавления вычисления матрицы стоимости.

Алгоритм состоит из нескольких этапов, которые обеспечивают оптимальное распределение растений по зонам с учётом характеристик.

1. Подготовка данных

На этапе подготовки данных матрицы Z (характеристики зон) и P (характеристики растений) передаются в виде строковых массивов. Данные преобразуются в числовой формат для упрощения вычислений, т.к. строковые данные удобно задавать в пользовательском интерфейсе, но для математических операций необходим числовой формат.

2. Вычисление матрицы стоимости

На данном этапе создаётся матрица стоимости, где каждый элемент представляет суммарное отличие характеристик растения i от зоны j. Для каждого сочетания "растение-зона" рассчитывается сумма абсолютных разностей характеристик. Матрица стоимости отражает степень соответствия между растением и зоной. Чем меньше значение, тем лучше растение подходит для данной зоны. Для каждой пары "растение-зона" перебираются все их характеристики.

3. Инициализация венгерского алгоритма

Алгоритм начинается с преобразования матрицы стоимости для упрощения поиска минимального покрытия. Из каждой строки вычитается минимальный элемент строки, из каждого столбца вычитается минимальный элемент столбца.

4. Покрытие нулями и распределение

Алгоритм определяет минимальное количество линий (строк или столбцов), необходимых для покрытия всех нулей в матрице: если количество линий меньше n (число зон), то матрица модифицируется, иначе начинается распределение.

5. Назначение растений зонам

Распределение выполняется, выбирая нули по одному и исключая соответствующие строки и столбцы.

6. Вывод результата

После выполнения всех назначений программа, реализующая алгоритм, возвращает массив, где каждому растению соответствует номер зоны. Каждое растение назначено на свою зону с минимальной стоимостью.

Рисунок 1. Общая блок-схема алгоритма

Модифицированный венгерский алгоритм проходит несколько этапов: преобразование данных, расчет матрицы стоимости, минимизация, покрытие нулями и окончательное распределение.

Таким образом, венгерский алгоритм, изначально созданный для решения задачи сопоставления объектов из двух множеств, был модифицирован для формирования ландшафтных композиций. Эти изменения направлены на учет специфики характеристики зон и растений, а также обеспечение гибкости под задачи ландшафтного проектирования. Данный подход позволяет автоматизировать решение задачи оптимального размещения растений при формировании ландшафтных композиций, которую решают ландшафтные архитекторы.

Список литературы:

1. Асанов М.О, Расин В.В. Комбинаторные алгоритмы. Учебное пособие. - 1-е изд. – Екатеринбург: Уральский университет, 2008. – 151 с.
2. Бебишев М.А., Корчевская О.В. Модифицированный венгерский метод // Хвойные бореальной зоны. – 2012. – №5 - 6. – С. 97-102.