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

Cтраница 1

Волновой алгоритм включает в себя два этапа. [1]

Волновой алгоритм связан со значительными затратами машинного времени, причем 90 % времени затрачивается на распространение волны и лишь 10 % на проведение трассы. [2]

Пример соединения элементов а и b с помощью волнового алгоритма. [3]

Волновые алгоритмы широко применяют в различных областях техники, в частности при разработке сетей связи и сетей ЭВМ. [4]

Сущность волнового алгоритма заключается в моделировании волны, распространяющейся прямолинейно от источника. Фронт волны распространяется по определенным правилам, в которые заложены условия выполнения межэлементных соединений в виде разрешенных и запрещенных возможных путей. Процесс проектирования соединений с использованием волнового алгоритма включает в себя моделирование распространения волны с фиксацией координат возможного пути и построение трассы между элементами по установленным координатам. [5]

Для реализации волновых алгоритмов монтажное поле разбивается на прямоугольные площадки исходя из допустимых размеров проводников и расстояний между ними, Решение задачи трассировки сводится к определению последовательности прохождения прямоугольных площадок. [6]

Основные принципы волнового алгоритма Ли заключаются в следующем. Плоскость трассировки разбивают на прямоугольные площадки - дискреты заданного размера. Размер дискретной площадки определяется допустимыми размерами проводников и расстояниями между ними. Задача проведения трасс сводится к получению последовательности дискретов, соединяющих элементы а и Ь, соответствующие началу и концу проводимой трассы. [7]

Рассмотренные модификации волнового алгоритма Ли [193] обеспечивают построение пути минимальной длины между точками на плоскости, если между ними существуют препятствия для проведения соединений. [8]

Алгоритм носит название волнового алгоритма. [9]

Следует заметить, что волновой алгоритм связан со значительными временными затратами на решение задач и для сложных схем нереализуем даже на современных ЦВМ. [10]

Точное описание процесса трассировки волновым алгоритмом имеет дело с большими массивами, представляющими среду, в которой проводятся соединения. Хранение этих массивов требует больших затрат памяти, а их обработка - машинного времени. Введение неопределенности в форме О-описаний позволяет разделить решение задачи на этапы ( ниже рассматривается двухэтапное решение), уменьшив ее размерность на каждом этапе. Первый этап заключается в получении О-описания строящейся трассы. [11]

Построить в массиве V, пользуясь волновым алгоритмом, кратчайшее дерево, связывающее элементы, помеченные 1, выбирая для его построения в соответствующем направлении лишь те элементы, которые не отмечены - 1 в массиве V, и для которых в массивах VI и V2 значения соответствующих элементов меньше заданного максимально возможного. [12]

Модифицированная схема волнового алгоритма. [13]

Большой объем памяти, требуемый для реализации волнового алгоритма, может быть сокращен за счет использования модифицированного метода продвижения фронта волны, в котором для вычислений требуется только пять символов. Процедура вычислений иллюстрируется рис. 8.26, а, б, в, где две ячейки А и В, отмеченные звездочкой, требуется соединить линией минимальной длины. [14]

Трассировка соединений волновым алгоритмом при наличии препятствий. [15]

Страницы: 1 2 3