Содержание к диссертации
Введение
1. Анализ методов и алгоритмов решения задачи трассировки 13
1.1. Постановка задачи трассировки электрических соединений 13
1.1.1. Глобальная трассировка 25
1.1.2. Детальная трассировка 27
1.2. Построение минимальных связывающих деревьев в процессе трассировки электрических соединений 30
1.3. Анализ алгоритмов построения деревьев Штейнера в ортогональной метрике 34
1.4. Топологическая трассировка и гибкая прокладка соединений 39
1.5. Анализ топологических методов трассировки 44
1.6. Выводы 48
2. Разработка математического обеспечения для решения задач трассировки 52
2.1. Разработка архитектуры процесса трассировки 52
2.2. Геометрия гибкой трассировки 54
2.3. Постановка Евклидовой задачи Штейнера 61
2.4. Построение кратчайшего соединения трёх точек в Евклидовом пространстве 65
2.5. Вычисление координат точки Штейнера 67
2.6. Определение координат точки Штейнера при построении обходов 72
2.7. Кратчайшее соединение четырёх точек в Евклидовом пространстве 73
2.8. Кратчайшее соединение произвольного количества точек в Евклидовом пространстве 81
2.9. Примеры решения Евклидовой задачи Штейнера для произвольного количества точек 81
2.10. Выводы 86
3. Решение Евклидовой задачи Штейнера для неоднородных соединений 87
3.1. Постановка Евклидовой задачи Штейнера для неоднородных соединений 87
3.2. Оптимальное соединение 3-х точек в Евклидовом пространстве при условии неоднородности соединений 88
3.3. Решение задачи соединения источника электрических сигналов с приёмниками .99
3.4. Алгоритм решения Евклидовой задачи Штейнера для неоднородных соединений 102
3.5. Выводы 107
4. Экспериментальные исследования и анализ разработанных алгоритмов и программ „108
4.1. Цель экспериментальных исследований 108
4.2. Этапы экспериментальных исследований 108
4.3. Результаты вычислительных экспериментов и сравнение результатов работы алгоритма... 109
4.4. Краткое описание программной и аппаратной среды ПО
4.5. Выводы 125
Заключение 126
Литература
- Построение минимальных связывающих деревьев в процессе трассировки электрических соединений
- Постановка Евклидовой задачи Штейнера
- Оптимальное соединение 3-х точек в Евклидовом пространстве при условии неоднородности соединений
- Результаты вычислительных экспериментов и сравнение результатов работы алгоритма...
Введение к работе
В настоящее время во многих отраслях таких, например, как электронная промышленность, приборо- и машиностроение широко применяются интегральные микросхемы (ИС) большой (БИС) и сверхбольшой (СБИС) степени интеграции. Это повышает надежность электронно-вычислительной аппаратуры (ЭВА), снижает ее габариты, потребляемую мощность, улучшая, таким образом, технико-экономические характеристики выпускаемых изделий.
Под «интегральной микросхемой (ИС)» понимается микроэлектронное изделие окончательной или промежуточной формы, предназначенное для выполнения функций электронной схемы, элементы и связи которого нераздельно сформированы в объеме и(или) на поверхности материала, на основе которого изготовлено изделие [1]. Согласно [2, 3] большой интегральной микросхемой (БИС) называется интегральная микросхема содержащая 500 и более элементов, изготовленных по биполярной технологии, либо 1000 и более элементов, изготовленных по МДП-технологии, причем под элементом интегральной микросхемы понимается часть ИС, не выделенная в самостоятельное изделие, но реализующая функцию какого-либо элемента схемы, например, транзистора.
Степень интеграции постоянно возрастает с момента изобретения ИС. В 1965 году сопрезидент фирмы Intel Гордон Мур, предсказал, что число элементов на кристалле ИС должно удваиваться каждый год на протяжении последующих 10 лет. Это предсказание впоследствии было названо законом Мура [4]. Последующие 25 лет позволили уточнить закон Мура: число элементов на кристалле удваивается в среднем каждые 1,5 года. Применение на этапе проектирования САПР разного уровня способствует повышению степени интеграции СБИС на уровне узлов, блоков и всей системы в целом [5-21].
Неуклонное повышение степени интеграции СБИС привело к тому, что в них более 60% общей временной задержки сигнала приходится на задержки в межсоединениях. Рост размера области, отводимой для межсоединений, опережает рост размера области, предназначенной для активных элементов. В чипе, содержащем 10 миллионов транзисторов и использующем 4 слоя металлизации, около 40% площади отводится под межсоединения. Кроме того, рост числа транзисторов на кристалле, увеличивает также и средние размеры кристаллов. Подсчитано, что площади кристаллов самых больших ИС возрастают примерно на 13% в год и эта тенденция, согласно прогнозу, сохранится, по крайней мере, на ближайших полтора - два десятилетия.
Быстрая эволюция в производстве ИС стала бы невозможной без использования автоматизации выполнения различных этапов проектирования [5-9]. Сейчас, на всех стадиях проектирования топологии СБИС интенсивно используют средства автоматизации проектирования (САПР) и многие фазы могут быть полностью или частично автоматизированы.
Проектирование и изготовление современных СБИС невозможно без использования ЭВМ, являющихся незаменимым инструментом для расчета, изготовления, испытания, внедрения СБИС и устройств, созданных на их основе. Однако использование ЭВМ для этих целей малоэффективно без наличия мощного специального математического обеспечения, являющегося основой для создания автоматизированных систем проектирования (САПР). САПР, в общем случае, должны решать три категории задач: функциональное, техническое и технологическое проектирование.
С точки зрения реализации устройств на СБИС оптимальным является выполнение их на одном типе ячеек с одинаковой конфигурацией соединений между ячейками. Вычислительные структуры, реализованные на базе СБИС, позволяют решить такие важные вопросы создания дискретных устройств, как высокая универсальность, технологичность изготовления, гибкость, надежность, эффективность функционирования.
Современная САПР СБИС должна учитывать ряд критериев: увеличение производительности при возрастающих ограничениях при разработке и производства СБИС, время разработки СБИС, стоимость разработки. Такая система обеспечивает разработку мелкосерийных, «заказных» СБИС. Полученная интегральная схема может использовать биполярную технологию (более 500 элементов) или МДП-технологию (более 1000 элементов).
Большой вклад в развитие моделей, методов, стратегий, алгоритмов автоматизированного проектирования СБИС внесли российские и зарубежные учёные такие, как: Бершадский A.M., Казенное Г.Г., Курейчик В.М., Тетельбаум А.Я., Норенков И.П., Селютин В.А., Базилевич Р.П., Берштейн Л.С., Карелин В.П., Шервани Н. и др [5-21]. В основном известные алгоритмы, программы и пакеты в САПР предназначены для оптимальной компоновки, размещения разногабаритных объектов (формирования базового плана кристалла) и трассировки электрических соединений по критерию минимизации занимаемой площади и длины связей. В связи с увеличением сложности и размерности задач конструкторского проектирования, а также с возникновением новых тенденций в технологии изготовления СБИС, появляется необходимость в разработке новых направлений, методик, алгоритмов для решения данного класса задач.
С точки зрения повышения эффективности САПР, представляет интерес разработка нового математического обеспечения, алгоритмов и методов проектирования, для так решения называемых NP-полных задач, т.е. задач, в которых нахождение оптимального решения возможно только полным перебором. К числу таких методов можно отнести методы поисковые методы, методы динамического программирования, метод моделирования отжига, методы эволюционного моделирования [22-31]. В настоящее время широкое распространение получили метод моделирования отжига и эволюционные методы, поскольку такие алгоритмы позволяют обрабатывать множество решений при учёте множества критериев [32-39]. К ним относятся и генетические алгоритмы (ГА) - поисковые алгоритмы, основанные на механизмах натуральной селекции и генетики, работающие с популяциями решений методом эволюционного поиска. Уже имеются примеры успешного применения ГА для решения самых различных задач, в том числе и задач автоматизированного проектирования СБИС.
Проблема автоматизированного проектирования эскиза топологии СБИС охватывает широкий спектр вопросов, включающих представление исходной электрической схемы в виде математических или матричных моделей, размещение типовых фрагментов топологии на рабочем поле кристалла, проектирование коммутационных связей между отдельными элементами, распределение фрагментов трасс в проводящих слоях кристалла, контроль топологии, компоновку узлов и т.д. Очевидно, что решение этих задач с большими затратами трудовых и временных ресурсов. Кроме того, существует большая вероятность внесения ошибок. Преодоление указанных трудностей возможно лишь с использованием ЭВМ, функции которой обусловлены режимом диалога с разработчиком в процессе вычислений.
Значительный интерес, проявляемый к проблеме машинного проектирования эскиза топологии соединений, во многом объясняется большой трудоемкостью этого этапа и невозможностью создания универсальных алгоритмов трассировки, одинаково эффективных для различных конструкций СБИС. Известно большое число алгоритмов трассировки, основанных на различных методах построения, как отдельных трасс, так и цепей в целом [40-44]. Важным вопросом при трассировке является построение кратчайших связывающих деревьев цепей электрических схем. Решение задачи построения минимальных связывающих деревьев используется на начальном этапе трассировки для определения возможной конфигурации соединений [45 - 50].
Различают два принципа построения минимальных связывающих деревьев. Первый состоит в том, что не допускается вводить дополнительные вершины. Такая задача называется построением минимального связывающего дерева (МСД). Существуют эффективные алгоритмы Крускала, Прима и другие, предназначенные для построения МСД. Второй случай состоит в том, что разрешается вводить произвольное количество дополнительных вершин и соединяющих их ребер. Такая задача называется задачей Штейнера [51-62]. Ее решение приводит к построению дерева Штейнера (ДШ), а дополнительные вершины называются точками Штейнера (ТШ).
Еще одной важной задачей при трассировке электрических соединений является задача доразводки ^протрассированных соединений и улучшения конфигурации существующих соединений путем построения кратчайших обходов элементов СБИС. Разработка математического обеспечения и алгоритмов, позволяющих эффективно решать эти задачи, дало бы возможность повысить плотность и качество результатов трассировки.
В этой связи, тема работы, связанная с разработкой нового математического обеспечения для построения кратчайших связывающих деревьев и построения обходов элементов, а также методов и алгоритмов доразводки электрических соединений в процессе трассировки СБИС является АКТУАЛЬНОЙ.
ЦЕЛЬЮ диссертационной работы является разработка математического обеспечения, методов, моделей и алгоритмов нахождения минимальных связывающих деревьев Штейнера, построения обходов элементов и решения задачи доразводки на этапе трассировки цепей схем при проектировании СБИС и печатных плат. Критерием оптимизации является суммарная длина связей, что позволяет минимизировать длину цепей, а также площадь коммутационного пространства занимаемого проводниками и повысить качество решений для задач большой размерности.
Для достижения поставленной цели были поставлены и решены следующие задачи:
Проведен анализ существующих подходов к решению основных задач конструкторского этапа проектирования СБИС и, прежде всего различных этапов решения задачи трассировки электрических соединений. Проанализированы новые подходы к трассировке электрических соединений, такие как гибкая трассировка, топологическая трассировка. Проведен комплексный анализ существующих методов оптимизации и алгоритмов трассировки СБИС.
Выполнен анализ существующих методов и алгоритмов решения задачи построения минимальных связывающих деревьев и задачи Штейнера.
Предложен математический аппарат, позволяющий выполнять построение минимальных связывающих деревьев Штейнера.
Разработана математическая модель и алгоритм построения минимального связывающего дерева (дерева Штейнера) на основе решения Евклидовой задачи Штейнера.
Разработана математическая модель и алгоритм построения Евклидовых деревьев Штейнера с учетом различной толщины соединений и наличия направленности соединений.
Разработана математическая модель и методика сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений.
Проведены вычислительные эксперименты и выполнено сравнение разработанных моделей, методов и алгоритмов с уже результатами других существующими алгоритмов, на основе решения стандартных тестовых задач (бенчмарок).
Для решения поставленных задач использовались следующие МЕТОДЫ ИССЛЕДОВАНИЙ: элементы теории множеств, элементы теории графов и гиперграфов, элементы теории алгоритмов, элементы теории генетического поиска.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:
1. Разработке математического аппарата и моделей для построения дерева Штейнера на основе решения Евклидовой задачи.
Разработке алгоритма построения минимального связывающего дерева (дерева Штейнера), позволяющего сократить длину соединений.
Разработке алгоритма построения минимального связывающего дерева (дерева Штейнера) с учетом различной толщины соединений и наличия направленности соединений.
Разработке метода сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:
Математическая модель построения минимального связывающего дерева на основе решения Евклидовой задачи Штейнера.
Алгоритм и программное обеспечение для решения задачи построения дерева Штейнера на этапе глобальной трассировки СБИС, позволяющие уменьшить длину соединений при проектировании СБИС.
Алгоритм и программное обеспечение построения минимального связывающего дерева с учетом различной толщины соединений и наличия направленности соединений.
Метод сопряжения построений Евклидовых деревьев Штейнера с построением обходов для гибкой прокладки соединений.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.
Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной НИР «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений», а также х/д НИР по теме «Исследование алгоритмов решения Евклидовой задачи Штейнера для трассировки электрических соединений».
Материалы диссертации были использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».
АПРОБАЦИЯ основных теоретических и практических результатов работы проходила на Международных научно-технических конференциях «Интеллектуальные САПР» и «Искусственные интеллектуальные системы» (г. Геленджик, 2004 - 2005 гг.), на Всероссийской научной конференции «Управление и информационные технологии» (г. Пятигорск, 2004 г.), на Всероссийской научной конференции аспирантов и студентов (г. Таганрог , 2004 - 2005 гг.) и Всероссийской конференции молодых ученых и аспирантов «Новые информационные технологии» (г. Таганрог, 2004 - 2005 гг.).
ПУБЛИКАЦИИ. По теме диссертации опубликовано 9 печатных работ.
СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ
Диссертационная работа состоит из введения, четырёх глав, заключения, и списка использованных источников. Работа содержит 140 стр., включая 59 рис., 3 табл., список использованных источников из 120 наименований, 3 стр. приложений и актов об использовании и регистра .
СОДЕРЖАНИЕ РАБОТЫ.
Во ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, сформулированы цели, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ сформулирована постановка задачи трассировки электрических соединений, а также двух ее основных подзадач - глобальной и детальной трассировки. Приведена классификация и рассмотрены существующие методы и алгоритмы решения задачи построения минимальных связывающих деревьев. Сформулирована постановка задачи гибкой трассировки электрических соединений СБИС. Выполнен анализ основных преимуществ и недостатков топологических методов трассировки. Показана необходимость разработки новых методов и алгоритмов, а также математического обеспечения и моделей, позволяющих сочетать достоинства традиционных и топологических методов трассировки электрических соединений СБИС, и за счет этого повысить качество трассировки.
Во ВТОРОЙ ГЛАВЕ предложена модифицированная архитектура процесса трассировки электрических соединений. Предложено новое математическое обеспечение для решения задач построения обходов и разрешения конфликтов в процессе трассировки. Приведена математическая постановка Евклидовой задачи Штейнера. Разработана новая методика и приведены примеры ее успешного применения для решения задач построения кратчайших связывающих деревьев Штейнера в произвольной метрике.
В ТРЕТЬЕЙ ГЛАВЕ описано решение задачи построения дерева Штейнера как части задачи глобальной трассировки схем при проектировании СБИС при помощи алгоритма построения минимального связывающего дерева на основе решения Евклидовой задачи Штейнера. Приведена структурная схема разработанного алгоритма. Описан алгоритм построения минимального связывающего дерева с учетом различной толщины соединений и наличия направленности соединений. Определены теоретические оценки временной и пространственной сложности разработанного алгоритма.
В ЧЕТВЕРТОЙ ГЛАВЕ дано описание проведенных вычислительных экспериментов разработанного генетического алгоритма. Выполнена статистическая обработка полученных экспериментальных данных. Проделанные расчёты позволили подтвердить полученные ранее теоретические оценки временной и пространственной сложности разработанного алгоритма. Выполнено сравнение результатов работы разработанного метода с известными аналогами на основе наборов стандартных тестовых задач. Представлено описание программного обеспечения для построения минимального связывающего дерева Штейнера для задачи трассировки схем при проектировании СБИС.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.
В приложениях приведены копии актов о внедрении и использовании разработанных алгоритмов и программ.
Построение минимальных связывающих деревьев в процессе трассировки электрических соединений
Как уже отмечалось выше, задача трассировки состоит в том, чтобы по заданной схеме соединений проложить необходимые проводники на плоскости (плате, кристалле и т.п.), с учетом имеющихся ограничений.
На этапе глобальной трассировки выполняется оптимальное планирование соединений с целью уменьшения размера чипа, уменьшения длины соединений (и соответственно задержек), улучшение трассируемости и баланс интенсивности расположения соединений.
Для решения этого вопроса используют алгоритмы построения минимальных связывающих деревьев.
На языке теории графов, задача построения минимальных покрывающих деревьев формулируется следующим образом. Имеем несколько вершин (точек), их необходимо соединить некоторой системой ребер (линий) таким образом, чтобы любые две вершины были соединены либо одним ребром, либо цепью вершин и ребер. При этом суммарная длина всех ребер должна быть минимальной. Упрощая ситуацию, можно сформулировать задачу так. Пусть имеется связный неориентированный граф G = (X, U), в котором X - множество контактов, a U - множество их возможных попарных соединений. Для каждого ребра графа G задан неотрицательный вес w(xb Х2) (длина провода необходимого для соединения и и v). Задача состоит в нахождении подмножества Т с U, связывающего все вершины, для которого суммарный вес w(T)= w( p 2) минимален. Такое (ил-)еГ подмножество Т можно считать деревом (в любом цикле один из проводов можно удалить, не нарушая связности). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом этого графа.
Различают два случая. Первый состоит в том, что не допускается вводить дополнительные вершины. Такая задача называется построением минимального покрывающего дерева (МПД). Существуют эффективные алгоритмы Крускала, Прима и другие [5 -9, 63 - 68], предназначенные для построения МПД.
Во втором случае разрешается вводить дополнительные вершины и соединяющие их ребер. Такая задача называется задачей Штейнера. Ее решение приводит к построению дерева Штейнера, а дополнительные вершины называются точками Штейнера. Проведенный анализ, связанный с теорией NP-полноты показал, что построение дерева Штейнера является NP-трудной задачей. В общем виде данная задача формируется так: для заданных xi, х2,..., хп точек плоскости построить минимальное покрывающее дерево с п п вершинами. Известно, что для п 5 существует решение, в общем же случае известны условия, которым должны удовлетворять деревья Штейнера и эвристические алгоритмы.
В зависимости от метрики пространства, в котором рассматривается задача, выделяют несколько частных случаев задачи Штейнера [7, 9, 69 - 71]. Пусть ребром связана вершина 1 с координатами (xiyi) и 2 с координатами (х2,Уг)- Если расстояние между вершинами 1 и 2 (длина дуги (1,2)) определяется, как dl2 = (xi-x2)2+(yl-y1f , то задача называется Евклидовой.
Если расстояние определяется, как d\t2 = \х\ - х2\ + \у\ - уг\, то задача называется линейной. С линейной метрикой имеют дело при работе с печатными платами, где связь возможна только в решетке по взаимно перпендикулярным направлениям.
Для Евклидова пространства установлено: вершины Штеинера имеют степень три и располагаются таким образом, что углы между ребрами равны 120. Если пространство линейное, то в качестве мест для расположения точек Штеинера достаточно рассмотреть точки пересечения горизонтальных и вертикальных линий, проходящих через вершины графа.
Рассмотрим на примере заказной СБИС применение задачи Штеинера в ортогональной метрике для этапа глобальной трассировки. На рис. 1.10 а) представлен пример логической схемы для последующей трассировки с применением алгоритма дерева Штеинера. На рис. 1.10 б) представлен пример размещения и глобальной трассировки одной из цепей указанной схемы на топологии. Допустим на первом этапе глобальной трассировки необходимо соединить блоки И, 12, 13, 14, 10, 6, и С. Тогда указанные блоки являются вершинами графа G и задача глобальной трассировки сводится построению ортогонального дерева Штеинера. На рис. 1.10 в) показан результат глобальной трассировки на топологии заказной СБИС рассматриваемой схемы.
Здесь для решения задачи распределения соединений по областям используется графовая модель. Вершины графа соответствуют областям. Если две области aj и aj имеют общие соединения, то между ними существует ребро. Для каждого ребра, связывающего вершины V; и Vj, задается вес, равный пропускной способности общей границы между соответствующими областями. Координаты вершины принимаются равными координатам центра соответствующей области. Если области имеют один и тот же размер, то граф G представляет собой ортогональную решетку.
Постановка Евклидовой задачи Штейнера
1) Если все внутренние угаы, построенные по трем точкам А, В, и С, меньше 120, то искомой точкой является точка пересечения прямых Симпсона или точка пересечения окружностей Торричелли. Эта точка носит название точки Штейнера. Из точки Штейнера все стороны треугольника видны под одним и тем же углом 120 (Рис. 2.10. а). Это свойство называется «угловым условием».
2) Если один из внутренних углов, построенных по трем точкам А, В, и С больше, чем 120, тогда искомая точка, совпадает с той вершиной, которая больше 120 (Рис. 2.10. б).
Необходимо отметить, что оба вышеописанных метода решают задачу построения дерева Штейнера только для трёх точек и не дают ответа на вопрос: «Каким образом можно определить взаимное расположение смежных точек Штейнера для построения дерева с большим, чем три, количеством вершин?».
Задача построения дерева Штейнера и ее различные приложения получила большое распространение. Прокладка водопроводов, нефте- и газопроводов, автомобильных и железных дорог, электрических соединений печатных плат и интегральных схем и определение других минимальных сетей - вот некоторые из многочисленных примеров Евклидовой задача дерева Штейнера.
Математически задачу построения дерева Штейнера можно сформулировать следующим образом.
Пусть задан неориентированный граф G = (X, U) с неотрицательным диапазоном стоимостей. Множество вершин графа G разделено на два подмножества. Подмножество Х\ составляют вершины исходного графа, а подмножество Хг включает в себя вершины Штейнера. Требуется построить дерево минимальной стоимости, включающее в себя все вершины графа G и произвольное число вершин Штейнера.
В отличие от задачи построения дерева Штейнера в графе, Евклидова задача Штейнера не учитывает вершины Штейнера как точки входа. Задача состоит в том, чтобы соединить вершин (или точки) на плоскости, используя при этом вспомогательные точки (точки Штейнера), таким образом, чтобы длины соединенных отрезков была минимальной. Оценкой качества получаемого решения является суммарная длина всех фрагментов полученного соединения:
Задача оптимального соединения точек в Евклидовом пространстве при условии, что толщина соединяющих линий одинакова, может быть сведена к задаче построения наикратчайшего соединения трех точек.
Так как величина вписанного угла равна угловой величине дуги, на которую он опирается, для любой пары точек PI, Р2, все точки Штейнера (ТШ) располагаются на короткой дуге, описывающей окружности радиуса: где Dist - расстояние между этими точками.
Центр окружности при этом удалён от середины отрезка Р1 - Р2 на расстояние: Н:= 0.5R. В дальнейшем будем обозначать: окружность точки Штейнера - ОТШ, дуга точки Штейнера - ДТШ.
Тогда кратчайшее соединение точек Р1 и Р2 (Рис. 2.11) с любой точкой Pi, будет определяться в зависимости от положения точки Pi следующим образом: При нахождении точки Рі в области пересечения окружностей 01 и 02, кратчайшее соединение осуществляется через эту точку: Р1 - Pi - Р2; При нахождении точки Рі в области левее пунктирных линий, проходящих через Р1, кратчайшее соединение осуществляется через PI: Pi -Р1- Р2; При нахождении точки Рі в области правее пунктирных линий, проходящих через Р2, кратчайшее соединение осуществляется через Р2: Р1 «- Р2 - Pi; При нахождении точки Рі в оставшихся верхней и нижней областях, кратчайшее соединение осуществляется через точки Штейнера, лежащие на соответствующих ДТШ: Р1 -» Pf, Р2 -» Pf, Pi -» Pf.
Искомая ТШ находится на пересечении соответствующих ДТШ для Р1 - Р2, Р1 «- РЗ или Р2 - РЗ. После этого используется метод пересечения дуг (метод Торричелли) (Рис. 2.12).
Существует другой метод построения ТШ. Назовем его условно методом стремления. В этом случае искомая ТШ находится на пересечении ДТШ с прямой, проходящей через присоединяемую точку (РЗ) и точку «стремления» (ТС), которая является пересечением дальней, относительно присоединяемой точки, дугой ОТШ с серединным перпендикуляром к отрезку Р1 - Р2.
Геометрическое решение задачи в этом случае показано на рис. 2.13. Ниже приведем математическое вычисление координат, для чего был использован программный пакет MathCad.
Оптимальное соединение 3-х точек в Евклидовом пространстве при условии неоднородности соединений
1) Если все внутренние угаы, построенные по трем точкам А, В, и С, меньше 120, то искомой точкой является точка пересечения прямых Симпсона или точка пересечения окружностей Торричелли. Эта точка носит название точки Штейнера. Из точки Штейнера все стороны треугольника видны под одним и тем же углом 120 (Рис. 2.10. а). Это свойство называется «угловым условием».
2) Если один из внутренних углов, построенных по трем точкам А, В, и С больше, чем 120, тогда искомая точка, совпадает с той вершиной, которая больше 120 (Рис. 2.10. б).
Необходимо отметить, что оба вышеописанных метода решают задачу построения дерева Штейнера только для трёх точек и не дают ответа на вопрос: «Каким образом можно определить взаимное расположение смежных точек Штейнера для построения дерева с большим, чем три, количеством вершин?».
Задача построения дерева Штейнера и ее различные приложения получила большое распространение. Прокладка водопроводов, нефте- и газопроводов, автомобильных и железных дорог, электрических соединений печатных плат и интегральных схем и определение других минимальных сетей - вот некоторые из многочисленных примеров Евклидовой задача дерева Штейнера.
Математически задачу построения дерева Штейнера можно сформулировать следующим образом.
Пусть задан неориентированный граф G = (X, U) с неотрицательным диапазоном стоимостей. Множество вершин графа G разделено на два подмножества. Подмножество Х\ составляют вершины исходного графа, а подмножество Хг включает в себя вершины Штейнера. Требуется построить дерево минимальной стоимости, включающее в себя все вершины графа G и произвольное число вершин Штейнера.
В отличие от задачи построения дерева Штейнера в графе, Евклидова задача Штейнера не учитывает вершины Штейнера как точки входа. Задача состоит в том, чтобы соединить вершин (или точки) на плоскости, используя при этом вспомогательные точки (точки Штейнера), таким образом, чтобы длины соединенных отрезков была минимальной. Оценкой качества получаемого решения является суммарная длина всех фрагментов полученного соединения:
Задача оптимального соединения точек в Евклидовом пространстве при условии, что толщина соединяющих линий одинакова, может быть сведена к задаче построения наикратчайшего соединения трех точек.
Так как величина вписанного угла равна угловой величине дуги, на которую он опирается, для любой пары точек PI, Р2, все точки Штейнера (ТШ) располагаются на короткой дуге, описывающей окружности радиуса: где Dist - расстояние между этими точками.
Центр окружности при этом удалён от середины отрезка Р1 - Р2 на расстояние: Н:= 0.5R. В дальнейшем будем обозначать: окружность точки Штейнера - ОТШ, дуга точки Штейнера - ДТШ.
Тогда кратчайшее соединение точек Р1 и Р2 (Рис. 2.11) с любой точкой Pi, будет определяться в зависимости от положения точки Pi следующим образом: При нахождении точки Рі в области пересечения окружностей 01 и 02, кратчайшее соединение осуществляется через эту точку: Р1 - Pi - Р2; При нахождении точки Рі в области левее пунктирных линий, проходящих через Р1, кратчайшее соединение осуществляется через PI: Pi -Р1- Р2; При нахождении точки Рі в области правее пунктирных линий, проходящих через Р2, кратчайшее соединение осуществляется через Р2: Р1 «- Р2 - Pi; При нахождении точки Рі в оставшихся верхней и нижней областях, кратчайшее соединение осуществляется через точки Штейнера, лежащие на соответствующих ДТШ: Р1 -» Pf, Р2 -» Pf, Pi -» Pf.
Искомая ТШ находится на пересечении соответствующих ДТШ для Р1 - Р2, Р1 «- РЗ или Р2 - РЗ. После этого используется метод пересечения дуг (метод Торричелли) (Рис. 2.12).
Существует другой метод построения ТШ. Назовем его условно методом стремления. В этом случае искомая ТШ находится на пересечении ДТШ с прямой, проходящей через присоединяемую точку (РЗ) и точку «стремления» (ТС), которая является пересечением дальней, относительно присоединяемой точки, дугой ОТШ с серединным перпендикуляром к отрезку Р1 - Р2.
Геометрическое решение задачи в этом случае показано на рис. 2.13. Ниже приведем математическое вычисление координат, для чего был использован программный пакет MathCad.
Результаты вычислительных экспериментов и сравнение результатов работы алгоритма...
Целью исследования разработанного алгоритма является определение оптимальных параметров, при которых алгоритм находит наилучшие решения за минимальное время работы по сравнению с существующими алгоритмами, а также доказательство его эффективности (оптимальности), по сравнению с другими аналогичными алгоритмами. Эффективность (оптимальность) алгоритмов может быть доказана в результате [108-116]: Теоретических исследований, т.е. путем сравнения оценок временной сложности алгоритмов (ВСА). Экспериментальных исследований, т.е. в ходе проведения вычислительных экспериментов І и сравнения полученных экспериментальных данных. ;
В настоящей работе в результате проведения серий экспериментов были собраны экспериментальные данные и проведена их статистическая обработка.
Объектом исследований в данной работе являются разработанные алгоритмы и модели решения Евклидовой задачи Штейнера и построения кратчайшего связывающего дерева Штейнера.
Исследование разработанных алгоритмов должно быть объективным. Для обеспечения объективности необходимо проведение серии экспериментов с использованием различных тестовых функций. Количество экспериментов (объем выборки) должно быть достаточным для того, чтобы обеспечить необходимую достоверность сделанных по результатам экспериментальных исследований выводов.
Тогда можно принять следующий! план проведения вычислительных экспериментов: 1. Проведение серии экспериментов для фиксированных значений общих параметров и изменяемых дополнительных для каждого алгоритма. 2. Снятие экспериментальных данных и получения среднего значения целевой функции, являющейся результатом решения задачи при использовании конкретного алгоритма. 3. Определение параметров алгоритмов, при которых решение задачи наиболее оптимально и возможно.
На этапе теоретических исследований и подтверждения полученных экспериментальным путем оценок временной и пространственной сложности алгоритма необходимо исследовать: 1. Зависимость быстродействия алгоритма и требуемой памяти от размера исходного множества вершин для решения задачи построения дерева Штейнера. 2. Зависимость быстродействия алгоритма и требуемой памяти от значения общих параметров алгоритма.
В результате проведения вычислительных экспериментов были получены наборы данных, позволяющие экспериментально оценить эффективность и временную сложность разработанных алгоритмов. В процессе анализа полученных данных проводилось их сравнение с известными результатами аналогичных алгоритмов. Оценка эффективности работы алгоритма проводилась на стандартных тестовых примерах (бенчмарках), что обеспечивает объективность проведенного сравнения [117 -120].
Основные результаты, полученные в ходе проведения вычислительных экспериментов, сведены в таблицу 4.1. В данной таблице также приведены лучшие результаты работы алгоритма "GeoSteiner", что позволяет провести сравнение этих алгоритмов. Выбор алгоритма "GeoSteiner" является не случайным, так как данный алгоритм! позволяет на сегодняшний день получать наиболее качественные результаты построения Евклидовых деревьев Штейнера.
В последнем столбце таблицы для і наглядности сравнения алгоритмов приведены данные в процентах, показывающие эффективность разработанного алгоритма по отношению к алгоритму "GeoSteiner".
Экспериментальные исследования подтвердили теоретическую оценку временной сложности. На самом деле ВСА близка к 0(п2).
На рис. 4.1. приведена сравнительная диаграмма, позволяющая оценить качество решений, получаемых Nick_CAD и сравнить их с результатами алгоритма "GeoSteiner". За 100% - взято качество решения алгоритма "GeoSteiner".
Тестирование и экспериментальные исследования проводились с помощью специализированного программного обеспечения (ПО) изготовленного на объектно-ориентированном языке программирования C++ в среде разработки Borland C++ Builder Enterprise Suite Version 5.0. Ha рисунке 4.2 представлено диалоговое окно разработанного программного обеспечения, используемое для получения статистических данных и демонстрации результатов работы алгоритмов.
