Разработка математического и программного обеспечений оптимизации проектных решений на основе раскраски вершин графа (мографа)

• Автор: Лащенков, Андрей Валерьевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Москва
• Количество страниц: 199 с.

Содержание

Введение
Глава I. Существующие методы группирования объектов на основе раскраски вершин графа
1.1. Точные методы раскраски 2 В
1.2. Приближенные методы раскраски
1.3. Характеризация раскраски вершин графа
1.4. Сравнительный анализ методов раскраски вершин графа
Выводы
Глава II. Разработка эффективных инвариантных средств группирования
объектов на основе раскраски графа (мографа)
11.1. Улучшенные критерии соцветности вершин
11.2. Совместное применение слабо-коррелированных приближенных алгоритмов раскраски
11.3. Декомпозиционный подход к раскраске вершин графа
11.4. Редукция и раскраска графов
11.5. Обобщение методов раскраски графа с целью учета отношений произвольного порядка при решении некоторых задач группирования
Выводы
Глава III. Описание пакета программ “Раскраска”
111.1. Назначение, характеристики и структура пакета программ “Раскраска” ..128 II 1.2. Описание библиотеки “ColorLib”, реализующей разработанные
методы раскраски
II 1.3. Форматы данных, используемых пакетом программ “Раскраска”
II 1.4. Руководство пользователя пакета программ “Раскраска”
Выводы
Глава IV. Использование пакета программ “Раскраска” при оптимизации проектов технологических процессов машиностроительного профиля
Выводы
Заключение
Список литературы

Введение.
Характерными чертами современного производства являются: постоянное усложнение конструкций выпускаемых изделий, увеличение их номенклатуры и необходимость частой смены объектов производства, причем сроки освоения и переподготовки производства наряду с объемом необходимых для этого материальных затрат являются важнейшими факторами, определяющими жизнеспособность предприятия.
При этом основной стратегией по совершенствованию технической и технологической базы и оптимизации организации производства является осуществление интегральной автоматизации цикла “исследования - проектирование - технологическая подготовка производства - производство”, использование промышленной робототехники и организация гибких производственных систем (ГПС).
Одной из актуальных проблем современности является ускорение процесса проектирования новых изделий и технологий их производства одновременно с повышением качества получаемых при этом проектных решений. В непростых современных условиях мировой и, особенно, российской экономики эта проблема приобретает особое значение.
Продолжающееся бурное развитие микроэлектронной технологии, являющееся одним из главных факторов, определяющих прогресс во всех сферах жизнедеятельности человечества, начиная со второй половины XX века, значительно расширяет горизонты возможностей человека. Но вместе с тем становится очевидным, что само по себе развитие аппаратных средств не способно полностью оправдать тех надежд, которые в современных условиях возлагаются на вычислительные системы как на ключевое звено современных

технологий, направленных на увеличение эффективности использования ресурсов (в том числе сырьевых, топливно-энергетических и интеллектуальных) и решение глобальных проблем, перед лицом которых человечество оказалось на пороге нового века.
Несмотря на то, что вычислительная мощность современных вычислительных систем достигла высот, еще сравнительно недавно казавшихся невероятными, вычислительная мощность, требуемая для получения точного решения некоторых из ставших сегодня актуальными задач с помощью известных методов, остается недосягаемой даже потенциально. Вот почему не менее важным, чем развитие аппаратных средств, является развитие методов решения сложных задач с применением вычислительной техники.
Многочисленные исследования в области создания алгоритмов решения оптимизационных задач на дискретных структурах позволили выделить множество задач дискретной математики, являющихся инвариантными в том смысле, что к ним могут сводиться многочисленные практические задачи из различных предметных областей. Отсюда следует, что прогресс в развитии методов решения одной из таких абстрактных задач позволит повысить эффективность решения широкого ряда практических оптимизационных задач.
Большинство задач такого рода могут быть эффективно решены в рамках теоретико-графового подхода.
В исследование проблем оптимизации проектных решений на основе теоретико-графового подхода внесли большой вклад российские и зарубежные ученые: В. А. Горбатов [15-23], Н. Г. Малышев [48], А. В. Суворов [48, 58], Л. С. Берштейн [8], О. С. Бартенев [5],
3. Б. Хадонов [63], В. М. Лохин [46], М. И. Смирнов [23, 56-57],

которые данный алгоритм находит оптимальную раскраску графа С=<¥,и>, в (| У / 2)! раз меньше, чем число шагов, необходимых алгоритму, изложенному в [39, 77], при этом во столько же раз уменьшается объем необходимой оперативной памяти. В случае применения поиска с приоритетом по глубине за счет увеличения необходимого объема вычислений объем необходимой оперативной памяти может быть дополнительно уменьшен в *(|Р|2 / 8) ч- (|Р| /2)! раз.
В целом алгоритм, предложенный в работе [92], более эффективен, чем алгоритм, предложенный в работах [39, 77], и сравним по эффективности с алгоритмом, основанном на покрытии графа пустыми подграфами (т.е., максимальными независимыми множествами).
Метод неявного перебора [39, 74, 75, 84].
Согласно [39, 75, 84], для получения точного решения задачи раскраски вершин графа с “поразительной эффективностью” может быть использован следующий простой метод неявного перебора.
Предположим, что вершины графа некоторым образом упорядочены, и V,; - /-я вершина в заданном упорядочении, причем нумерация вершин начинается с единицы. Тогда первоначальная допустимая раскраска может быть получена с помощью следующей процедуры:
1. Окрасить Тх в цвет 1.
2. Каждую из оставшихся вершин окрашивать последовательно в соответствии с заданным упорядочением: вершина V, окрашивается в “наименьший” возможный цвет, т.е., в первый в данном упорядочении цвет, не использованный для окраски какой-либо из вершин, смежных с V/.