 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Общая характеристика алгоритмов компоновки конструктивных модулей
Все существующие алгоритмы компоновки конструктивных модулей можно разделить на два основных класса: точные и приближенные алгоритмы, которые, в свою очередь представлены несколькими подклассами (см. рис. 3.4).
Рис. 3.4 Классификация алгоритмов компоновки
Алгоритмы Лаурера основаны на сведении задачи компоновки к так называемой задаче покрытия, возникающей при минимизации булевых функций. Эти алгоритмы в качестве модели схемы используют гиперграф (матрицу H).
Существует несколько модификаций алгоритмов на основе метода ветвей и границ, в которых в качестве модели схемы используются ГГ или ВНГ. Они отличаются способом вычисления оценки.
При современном быстродействии ЭВМ точные алгоритмы позволяют решать задачи с числом переменных не более 20-ти. В связи с этим на практике широко применяются приближенные, эвристические алгоритмы, математически слабо обоснованные, но дающие неплохие результаты. Суть последовательных алгоритмов – последовательное заполнение блоков еще не распределенными в блоки элементами. В качестве очередного элемента выбирается элемент максимально связанный с элементами, уже включенными в формируемый блок. Процесс заполнения блока элементами продолжается до тех пор, пока не нарушаются ограничения на модульную (
) и контактную (
) емкости блока. Имеются различные модификации таких алгоритмов, отличающиеся выбором критерия для кандидата на включение и способом вычисления оценки.
Суть параллельно-последовательных алгоритмов: здесь сначала выделяются некоторые группы элементов, например, сильно связанные между собой, а затем эти группы параллельно распределяются по блокам с учетом контактных и модульных ограничений.
Итерационные алгоритмы служат для улучшения некоторого начального варианта компоновки, полученного либо вручную, либо с помощью последовательных алгоритмов, и состоят в обмене (перестановках) элементов, принадлежащих разным блокам. При этом осуществляются одинарные, двойные и, в общем случае, групповые перестановки элементов.
Поиск по сайту: