Разработка интернет-приложения для автоматизации построения принципиальных электрических схем

Дипломная работа - Компьютеры, программирование

Другие дипломы по предмету Компьютеры, программирование



?лощадью поля, допустимой плотностью расположения выводов элементов и проводников. Выбранная система ячеек определяет среду, в которой осуществляется построение соединений. В простейшем случае ячейка представляет собой квадрат со стороной h, равной расстоянию между соседними линиями двух соседних проводников.

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

2.2 Анализ существующих алгоритмов решения задачи

Существуют две группы алгоритмов решения задачи трассировки: последовательные и параллельные. Более подробная классификация приведена на рисунке 2.1.

Рисунок 2.1 - Классификация алгоритмов трассировки

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

К волновым относятся алгоритмы, основанные на идеях динамического программирования на дискретном рабочем поле (ДРП). В настоящее время разработано огромное число модификаций волнового алгоритма, предложенного Ли еще в 1961г.; однако все они сохраняют его основной недостаток: большие вычислительные затраты и большие затраты памяти ЭВМ. Временная сложность волнового алгоритма составляет (M*N), где N - число клеток ДРП, M - число точек, подлежащих соединению. Эффективное использование волновых алгоритмов возможно лишь для ДРП с числом ячеек не более 105, при этом время трассировки составляет несколько часов работы ЭВМ. Число неразведенных трасс обычно не превышает 10%.

Основная идея лабиринтных алгоритмов состоит в отыскании пути между двумя ячейками ДРП посредством последовательного обхода преград в лабиринте, образованном занятыми и свободными ячейками. В отличие от волнового алгоритма поиск носит направленный характер, поэтому время поиска сокращается. Алгоритм обычно обеспечивает разводку около 80% соединений.

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

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

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

В алгоритмах гибкой трассировки на первом этапе строятся модели топологии для трасiепей на дискретном топологическом рабочем поле (ДТРП) (без жесткой фиксации), а на втором этапе - модели геометрии, которые метрически точно определяют конфигурацию и месторасположение каждой трассы на КП.

В графотеоретических методах используют графовые модели элементов и компонентов схем, на основе которых синтезируется топологический эскиз проектируемого устройства. На следующем этапе решается задача метризации топологического эскиза.

Выбор алгоритма трассировки осуществлялся по следующим критериям:

). Эффективность.

). Простота реализации.

). Доступность реализованных примеров.

На основе вышеупомянутого, при разработке интернет-приложения было принято решение использовать для задачи трассировки волновой алгоритм. Так как число ячеек на дискретном рабочем поле не будет слишком велико и с реализацией алгоритма не возникнет трудностей.

2.3 Волновой алгоритм

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

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

Исходные данные, цели и задачи, которые требуются для работы волнового алгоритма можно кратко сформулировать следующим образом:

Волновой алгоритм решает задачу нахождения (поиска) пути на плоской двумерной кле