Разработка интернет-приложения для автоматизации построения принципиальных электрических схем
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?лощадью поля, допустимой плотностью расположения выводов элементов и проводников. Выбранная система ячеек определяет среду, в которой осуществляется построение соединений. В простейшем случае ячейка представляет собой квадрат со стороной h, равной расстоянию между соседними линиями двух соседних проводников.
Задача трассировки заключается в построении трассы от начальной ячейки до конечной таким образом, чтобы она не включала запрещенные ячейки и имела минимальную длину в ортогональной метрике.
2.2 Анализ существующих алгоритмов решения задачи
Существуют две группы алгоритмов решения задачи трассировки: последовательные и параллельные. Более подробная классификация приведена на рисунке 2.1.
Рисунок 2.1 - Классификация алгоритмов трассировки
В последовательных методах трассировки проводят одну за другой последовательно, при этом проведение какой-либо трассы a на (i-1)-ом шаге может затруднить проведение трассы b на i-ом шаге, так как является препятствием для проведения трассы b. Следовательно, особенно актуальным для последовательных алгоритмов является предварительное ранжирование (упорядочивание) соединений до трассировки. Существуют различные стратегии упорядочивания, основанные, в частности, на длине соединений, степени охвата соединением других соединений и др. Однако объективных оценок эффективности таких методик в настоящее время нет, поэтому наиболее разумными представляются использование нескольких вариантов очередности и выбор из них наилучшего.
К волновым относятся алгоритмы, основанные на идеях динамического программирования на дискретном рабочем поле (ДРП). В настоящее время разработано огромное число модификаций волнового алгоритма, предложенного Ли еще в 1961г.; однако все они сохраняют его основной недостаток: большие вычислительные затраты и большие затраты памяти ЭВМ. Временная сложность волнового алгоритма составляет (M*N), где N - число клеток ДРП, M - число точек, подлежащих соединению. Эффективное использование волновых алгоритмов возможно лишь для ДРП с числом ячеек не более 105, при этом время трассировки составляет несколько часов работы ЭВМ. Число неразведенных трасс обычно не превышает 10%.
Основная идея лабиринтных алгоритмов состоит в отыскании пути между двумя ячейками ДРП посредством последовательного обхода преград в лабиринте, образованном занятыми и свободными ячейками. В отличие от волнового алгоритма поиск носит направленный характер, поэтому время поиска сокращается. Алгоритм обычно обеспечивает разводку около 80% соединений.
Эвристические алгоритмы трассировки эффективны, как правило, только на начальных стадиях трассировки, когда на плоскости мало преград. Основная идея состоит в генерации самых длинных незанятых отрезков в направлении цели с эвристическими приемами обхода препятствий.
В параллельных алгоритмах трассировки вначале определяется допустимое взаимное расположение трасс, которое оптимизируется по выбранному критерию, и лишь потом трассы фиксируются на коммутационном поле.
Перспективными в настоящее время являются канальные алгоритмы, основанные на возможности в некоторых случаях регулярного разбиения коммутационного поля (КП) на каналы и трассировки внутри каналов вертикальными и горизонтальными отрезками. Алгоритмы работают быстро, однако для них актуальна проблема качества получаемых решений. Канальным алгоритмам свойственен иерархический подход к трассировке, когда исходная задача декомпозируется на несколько подзадач. При этом на каждом иерархическом уровне, в зависимости от его специфики, целесообразно применение различных методов трассировки.
В алгоритмах гибкой трассировки на первом этапе строятся модели топологии для трасiепей на дискретном топологическом рабочем поле (ДТРП) (без жесткой фиксации), а на втором этапе - модели геометрии, которые метрически точно определяют конфигурацию и месторасположение каждой трассы на КП.
В графотеоретических методах используют графовые модели элементов и компонентов схем, на основе которых синтезируется топологический эскиз проектируемого устройства. На следующем этапе решается задача метризации топологического эскиза.
Выбор алгоритма трассировки осуществлялся по следующим критериям:
). Эффективность.
). Простота реализации.
). Доступность реализованных примеров.
На основе вышеупомянутого, при разработке интернет-приложения было принято решение использовать для задачи трассировки волновой алгоритм. Так как число ячеек на дискретном рабочем поле не будет слишком велико и с реализацией алгоритма не возникнет трудностей.
2.3 Волновой алгоритм
Волновой алгоритм - это алгоритм, который позволяет найти минимальный путь в графе. Алгоритм поиска в ширину лежит в основе этого метода. В основном волновой алгоритм применяется для нахождения самого кратчайшего пути в графе, в общем случае находит лишь его длину.
Волновой алгоритм можно назвать одним из самых уникальных алгоритмов трассировки. Волновой алгоритм позволяет сформировать путь (трассу) между двумя ключевыми точками (элементами) в любом лабиринте, здесь необходимо отметить тот факт, что задача является разрешимой.
Исходные данные, цели и задачи, которые требуются для работы волнового алгоритма можно кратко сформулировать следующим образом:
Волновой алгоритм решает задачу нахождения (поиска) пути на плоской двумерной кле