Составление простейших алгоритмов и их трассировка доклад
Обновлено: 02.07.2024
Трассировка – это метод пошаговой фиксации динамического состояния алгоритма на некотором тесте . Часто осуществляется с помощью трассировочных таблиц, в которых каждая строка соответствует определённому состоянию алгоритма, а столбец – определённому состоянию параметров алгоритма (входных, выходных и промежуточных). Трассировка облегчает отладку и понимание алгоритма.
Процесс поиска и исправления (явных или неявных) ошибок в алгоритме называется отладкой алгоритма.
Некоторые (скрытые, труднообнаруживаемые) ошибки в сложных программных комплексах могут выявиться только в процессе их эксплуатации, на последнем этапе поиска и исправления ошибок – этапе сопровождения. На этом этапе также уточняют и улучшают документацию, обучают персонал использованию алгоритма (программы).
Пример. Определим функцию фрагмента алгоритма вида на тесте n=2; x[1]=4; x[2]=9 :
Если выписать трассировочную таблицу вида
В заключение данного раздела приведем общую структуру алгоритмического обеспечения. Критерии, по которым алгоритмы могут быть классифицированы, бывают разными, поэтому предлагаемая ниже схема отражает основные элементы структуры и в некоторых случаях является условной, в том смысле, что блоки приведенной на рис. 9.1 структуры могут "перекрываться".
Основные формы использования алгоритмов – автономное, библиотечное, пакетное.
Автономный алгоритм определяется решаемой задачей, структурой используемых данных, структурой логических связей частей (модулей) алгоритма и языком псевдокодов, на котором представлен, описан алгоритм .
Библиотека алгоритмов определяется множеством задач, решаемых с помощью библиотеки, множеством алгоритмов для решения типовых задач некоторой предметной области и структурой используемых данных.
Пакет алгоритмов, как и библиотека, определяется множеством задач, решаемых с помощью пакета, множеством алгоритмов для решения типовых задач или их составных частей из некоторой предметной области , структурой используемых данных и обменов данными между задачами (модулями), специальным языком, на котором формулируется задание (последовательность этапов решаемой задачи, последовательность задач задания).
Трассировка соединений как одна из наиболее трудноразрешимых задач в общей проблеме автоматизации проектирования электронных устройств. Характеристика алгоритма для поиска пути между двумя ячейками – источником и приемником дискретного рабочего поля.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 12.06.2016 |
| Размер файла | 252,5 K |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
1. Трассировка соединений
Проектирование схем соединений, иначе трассировка соединений, является одной из наиболее трудных задач в общей проблеме автоматизации проектирования электронных устройств. Прежде всего, это связано с многообразием способов конструктивно-технологической реализации соединений, каждый из которых обусловливает использование специфических критериев оптимизации и ограничений при алгоритмическом решении задачи трассировки.
Исходной информацией для решения задач трассировки соединений являются:
- параметры конструкции элементов и коммутационного поля;
- данные по размещению элементов.
В алгоритмическом плане задача трассировки состоит в построении для всех цепей схемы оптимальных монтажных соединений. Задача трассировки имеет метрический и топологический аспекты. Метрический аспект предполагает учет конструктивных размеров элементов, соединений и коммутационного поля (КП). Топологический аспект связан с выбором допустимого пространственного расположения отдельных монтажных соединений на КП при ограничениях на число пересечений соединений, число слоев коммутационной схемы и т.п.
Алгоритмические методы трассировки проводных и печатных соединений существенно различаются.
Для проводного монтажа трассировка осуществляется с помощью алгоритмов построения минимальных деревьев соединений. Полная монтажная схема (таблица проводов) получается при последовательном применении указанных алгоритмов для отдельных цепей схемы. Далее, на основании анализа паразитных связей в полученной монтажной схеме трассы отдельных соединений могут быть скорректированы.
Алгоритмические методы трассировки печатных соединений существенно зависят от конструкции коммутационного поля и могут быть разделены на две основные группы.
К первой группе относятся так называемые топографические методы, в которых приоритет отдается метрическому аспекту задачи. Вторая группа основана на графотеоретическом подходе к решению задачи трассировки. В нашем курсе рассматриваются методы первой группы.
Топографический метод трассировки в общем случае содержит следующие основные этапы:
получение списка соединений;
распределение соединений по слоям;
определение порядка прокладки соединений;
собственно трассировка отдельных соединений.
Методы данной группы наиболее эффективны для трассировки двухсторонних и многослойных печатных плат.
Поскольку список цепей определяет лишь группы эквипотенциальных выводов, основной задачей первого этапа является предварительное определение порядка соединений выводов внутри отдельных цепей. Такое упорядочение, как и при проектировании монтажных схем проводных соединений, осуществляется с помощью алгоритмов построения минимальных деревьев.
На втором и третьем этапах решаются вопросы, на каком из слоев будет осуществляться трассировка соединений и в каком порядке. Большинство методов расслоения соединений основано на анализе взаимного расположения всей совокупности соединений на одной плоскости с целью распределения конфликтующих между собой соединений по отдельным слоям. Так как подавляющее большинство алгоритмов трассировки принадлежит к алгоритмам последовательного типа, порядок прокладки соединений должен быть определен заранее.
Для трассировки соединений предложено много алгоритмов, отличающихся скоростью и требуемым объемом памяти при реализации на компьютере, а также качеством результата: волновой алгоритм и его модификации, алгоритмы трассировки по магистралям и каналам и ряд комбинированных алгоритмов.
2. Алгоритмы трассировки соединений
В алгоритмическом плане задача трассировки состоит в построении для всех цепей оптимальных монтажных соединений.
Постановка задачи заключается в следующем. Дана принципиальная электрическая схема, на которой определены цепи и связанные с ними контакты элементов. Дано размещение элементов на плоскости. Требуется построить монтажные соединения. Например (см. рис. 1):
Рис. 1. а) принципиальная электрическая схема; б), в) схемы электрических соединений
На рис. 2-4 даны примеры конфигурации разводки электрических цепей автономных объектов.
3. Алгоритмы трассировки проводных соединений
Пусть задана электрическая цепь (рис. 4) и соединенные ею элементы.
Они могут быть представлены полным графом (рис. 5).
Из этого графа надо выделить суграф заданной конфигурации, представляющий схему электрических соединений.
Рассмотрим типовые конфигурации. Если не заданы жесткие требования надежности, то это может быть разомкнутая конфигурация, т.е. из графа надо выделить дерево. При этом могут быть заданы ограничения на степень вершин, а могут и не задаваться (рис. 6).
Для внутреннего монтажа коробок используются и замкнутые цепочки, и особенно сложная конфигурация имеет место при наличии клеммных колодок. Они неизбежны, если клеммы некоторых элементов допускают подключение только одного провода.
Наиболее эффективным из известных алгоритмов является алгоритм Прима:
1. для произвольного вывода цепи найти ближайший вывод и провести соединение;
2. на последующем шаге i = 2,3,…,n-1 из множества неподсоединненых выводов выбрать тот, который находится ближе остальных к группе yже связанных выводов и подсоединить его к этой группе по кратчайшему пути.
Построенное таким образом дерево будет иметь минимальную суммарную длину соединений.
При разработке монтажных соединений часто вводится ограничение на максимальное число соединений л к клемме элемента, т.е. на степень вершины. Если л
Алгоритм - это некоторая конечная последовательность точных элементарных предписаний (команд, инструкций, правил), однозначно определяющих процесс преобразования исходных данных и промежуточных результатов в результат решения задачи (иначе: это план к решению задачи). Здесь подразумевается, что алгоритм удовлетворяет свойствам: дискретности (это конечный набор отдельных шагов), определенности (восприятие и исполнение нужных пунктов вполне однозначно), результативности (всегда найдется путь от начала к концу решения, может быть и с отсутствием конкретных выходных результатов), массовости (работает на конкретный тип задачи при различных наборах исходных данных, которые могут меняться в определенных пределах), понятности (создается в расчете на определенного исполнителя, способного выполнить каждый шаг предписания).
Формы записи алгоритмов
1. Словесная, или текстовая, форма – это пронумерованная последовательность предложений на естественном языке (разговорном языке пользователя) с применением математических обозначений и формул (то есть каждое предложение - это очередное предписание алгоритма). Такое представление весьма слабо формализовано, а поэтому под сомнением свойство определенности алгоритма. Зато для записи в этой форме не нужны никакие специальные знания кроме знаний собственно самого плана решения задачи.
2. Графическая, или схемная, форма (иначе – блок-схема) - это пронумерованная последовательность блоков различной конфигурации в зависимости от типа выполняемого предписания (т.е. каждая фигура – это очередное предписание алгоритма). Блоки соединены линиями связи в соответствии с порядком исполнения. Внутри блоков допустимы только математические записи. Конфигураций основных блоков столько, сколько выделено основных предписаний для построения вычислительных алгоритмов (они указаны выше). Несмотря на некоторые трудности, а может быть благодаря им, такое представление алгоритмов очень формализовано. И еще одно преимущество – наглядность алгоритма в смысле его структуры и характера исполнения.
3. Алгоритм, представленный на языке программирования, – это последовательность (не всегда пронумерованная) "предложений" на выбранном алгоритмическом языке с использованием математической символики в алфавите этого языка. Как было сказано ранее, каждое "предложение" (очередное предписание алгоритма) называется оператором, а весь алгоритм, записанный в виде последовательности операторов, называется программой. Такое представление формализовано, используется обычно для ввода алгоритма в ЭВМ, а получается в результате "перевода" разработанного алгоритма в любой из перечисленных выше форм на алгоритмический язык: переводится (заменяется) последовательно каждое предписание "своим" оператором. Для простых задач и при хорошем знании языка программирования возможно написание программы сразу, без промежуточных форм.
Таблица 1. Элементы блок-схемы
| Тип | Текстовая форма | Графическая форма | Пояснения |
| Ввести (значения для): | Блок-ввода . . | После ключевого слова или внутри блока указывается список имен входных переменных через запятую, но не сами числа | |
| вычислить: = | Блок-процесс . . | После ключевого слова или внутри блока записывается имя вычисляемой переменной, знак = (присваивания) и формула, содержащая переменные, числа, арифметические операции, элементарные функции | |
| Сравнить: если , то п. К иначе п. М | Блок-принятие решения . | Условие - это логическое выражение (например, сравнения чего-то с чем-то). При выполнении условия (истина) - переход к одному пункту (например, к п. К), при невыполнении (ложь) - переход к другому (например, к п. М) | |
| Вывести (напечатать): | Блок-документ . . | После ключевого слова или внутри блока указывается список имен выходных переменных через запятую, но не сами числа. | |
| Начало решения . . Остановка (конец решения) | Блоки пуск/остановка . . | Если в начале алгоритма, то допустимы слова: вкл., вход, пуск, готов, начало или оставить пусто. Конец решения помечают обязательно, допустимы слова: конец, останов., выкл., выход, стоп или оставить блок пустым. |
Основные типы простейших алгоритмических структур.
1.Линейный тип алгоритма - это такая вычислительная структура, при которой все предписания выполняются в строго линейной последовательности друг за другом, как записаны; сам порядок исполнения называется естественным. В чистом виде линейные алгоритмы встречаются редко, они чрезвычайно просты. Но как фрагменты присутствуют почти во всех вычислительных схемах, так как именно на этих участках вводятся исходные данные, формируются и выходят на пользователя новые результаты (блок-ввода, блок-процесс, блок-печати). Примеры будут рассмотрены ниже.
2. Разветвляющийся тип алгоритма - эта такая вычислительная схема, которая содержит не одну, а несколько возможных ветвей решения по ММ; т.е. в структуре алгоритма есть хотя бы одна операция сравнения, порождающая 2 ветви последующего решения. Заранее нельзя сказать, какая ветвь алгоритма будет выполняться, все зависит от конкретных данных. Выбирается она автоматически, только в процессе исполнения алгоритма (остальные ветви для этого варианта данных останутся невостребованными). Тем труднее пользователю заранее (на этапе разработки) предусмотреть все возможные ветви решения и изобразить их, ничего не упустив. Примеры также будут рассматриваться ниже.
3.Циклический тип алгоритма - эта такая схема разветвленной структуры, в которой одна ветвь операции сравнения является обратной связью (ОС) на предыдущую часть алгоритма (т.е. идет назад). Таким образом, некоторая последовательность операций алгоритма будет выполняться многократно (т.е. в цикле), образуя тело цикла (тц). В крайнем случае, тело цикла может состоять всего из одной операции. Для того чтобы результаты всякий раз получались новые, необходимо алгоритмически предусмотреть три момента:
А)надо организовать данные для первого прохождения тела цикла;
Б)после каждого выполнения тела цикла надо обновлять данные для очередного прохождения цикла;
В)надо управлять циклом, организовать условие выхода из цикла или его продолжения (ОС не должна охватывать указанные в пункте а операции!).
Задача 1. Варианты задания.
Составить линейный алгоритм для вычисления
1) длины окружности и площади круга радиуса R;
2) длины медианы на сторону а в треугольнике со сторонами а, b, с;
5) длины биссектрисы на сторону а в треугольнике со сторонами a,b,c
8) площади треугольника со сторонами а, b, с;
9) площади квадрата с диагоналями d;
10) площади ромба с диагоналями d1 и d2;
11) площади трапеции с высотой h и основаниями а и b;
12) площади вписанного четырехугольника со сторонами а, b, с, d (через полупериметры);
Вы можете заказать написание любой учебной работы на любую тему.
* Данная работа не является научным трудом, не является выпускной квалификационной работой и представляет собой результат обработки, структурирования и форматирования собранной информации, предназначенной для использования в качестве источника материала при самостоятельной подготовки учебных работ.
В ведение В настоящее время используются различные варианты волнового алгоритма, в частности, лучевой и маршрутные. Простейшим видом волнового алгоритма является волновой алг оритм нахождения кратчайшего пут и без пересечения множества занятых и запрещенных элементов (участко в печатной платы). Его целесообразно использовать при трассировке сое динений в одной плоскости, когда недопустимо выходить из пределов это й плоскости. Определяются начальная и конечная точки и моделируется распространение волны от конечной точки к начальной в направлении во лны. Недостатком этого алгоритма является то, что он мало пригоден для трассировки многослойных печатных плат, проводники прокладываются п о краям платы, значительное число длинных параллельных проводников я вляются причиной большой взаимоиндуктивности. Более совершенным волновым алгоритмом является волновой алго ритм прокладки пути с минимальным числом пересечения. В этом случае ч исло пересечений ранее проложенных трасс должно быть минимальным. Дл я преодоления недостатка этого алгоритма, при котором трассы стремят ся к одной из границ платы и прижимаются друг к другу, был предложен ал горитм для проведения пути, минимально приближающихся к другим трасс ам. Основой алгоритма является условие, при котором элементы данного соединения должны иметь минимум соседних элементов, принадлежащих ра нее проложенным трассам. Если одним из условий является требование регулярности соед инений (один слой горизонтальные, другой – вертикальные и т.п.), то удоб нее использовать волновой алгоритм прокладки пути с минимальным чис лом изменений направления, который позволяет минимизировать количес тво межслойных соединений. В отличие от волновых и лучевых алгоритмов, в которых на начальной ста дии перебираются все возможные варианты трассы, в маршрутных алгорит мах прокладка трассы ведется сразу и по кратчайшему маршруту. 1. Маршрутный алгоритм трассировки Каждый слой платы представлен в памяти ЭВМ булевой матрицей , элементы которой имеют значение 0, если соответствующий элемент своб оден для прокладки пути, и имеют значение 1, если соответствующий элеме нт занят. Все элементы матрицы, которые принадлежат исходным препятст виям, задаются единичным значением. Алгоритм реализует следующие последовательно выполняемые этапы: 1) построение пути до вст речи с препятствием; 2) обход препятствий; 3) минимизация построенн ого пути. Этап 1. Пусть требуется проложить путь между элементами d a , булевой матрицы, описывающей модель платы. При отсутствии пр епятствий между элементами можно проложить конечное множество путей , имеющих минимальную длину в выбранной геометрии. Процесс построения Р-пути (Н-пути) сводится к тому, чтобы определить такую последовательно сть элементов L = , что любой эле мент d k принадлежит Р-ок рестности (Н-окрестности) элемента d k -1 . Если будем рассматривать Н-окрестность, то вектор пер ехода Z k от элемента d k к элемент у d к+1 возможен только в направлениях, параллельных координ атным осям. Для случая Р-окрестности вектор перехода может иметь диаг ональные направления. На каждом шаге построения пути направление вектора перехода Z k от элемента d k к элементу d к+1 определяе тся функциями sgn ( x b - x k ), sgn ( y b - y k ), где x b , y b - координаты элемента d b пути, x k , y k - координаты э лемента d k . Правило выбора направления построения пути до встречи с препятствие м в наилучшем направлении приведено в таблице 1. Таблица 1. Фун кция Z k 0 1 2 3 4 5 6 7 sgn(x b -x k ) 1 1 0 -1 -1 -1 0 1 sgn(y b -y k ) 0 1 1 1 1 -1 -1 -1 Наим енование направлений приведено на рисунке 1. 3 2 1 4 A 0 5 6 7 Рису нок 1. Наименование направлений вектора перемещения Z k . После каждого шага построения пути необходимо по вектору перехода Z k оп ределить состояние очередного элемента d k (свободный или занятый) булево м атрицы. Рассмотрим построение Н-пути. Для описания дискретного пространства, в котором строим путь, использ уем булеву матрицу С размером m n . Кроме того, для сокращения вычислений введ ем усеченную матрицу А размером m l . Число строк в матрице А определяется ширин ой прокладываемого проводника в дискретах. При прокладке проводников шириной в один дискрет матрица А будет матрицой-строкой, только один элемент которой принимает единичное значение. Номер этого элемента о пределяется координатой x k анализируемого э лемента d k . Состояние элементов описывается через булеву функцию , где c i , j – элемент мат рицы С; a i - элемент матрицы-сторки А. Здесь через индекс j обозначается номер строки матрицы С, котор ый определяется координатой y k элемента d k . Если V =1 , то элемент d k занят, и построение пути прекращается . Дальнейшее построение осуществляется путем обхода препятствий, нач иная с элемента d k -1 , который будем называть элементом в стречи с препятствием. При построении Р-пути распознавание состояния элемента выполняется в два этапа. На первом этапе определяем, принадлежит ли элемент d k какому-либ о объекту, записанному в матрице С. Если элемент d k не принадлеж ит никакому объекту, то переходим к выполнению второго этапа, суть кот орого сводится к следующему: определяем состояние элементов, которые принадлежат одновременно Н-окрестностям элементов d k , d k -1 . Таких элементов может быть только два, причем они расположе ны диагонально. Если оба элемента заняты, то построение пути из элемен та d k -1 в d k запрещено. При построении пути в диагональных направлениях состояния элементов описывается булевой функцией , i = 1, 3, 5, 7. (1) Булевы функции V i , V i -1 , V i +1 определяются при просмотре Р-окрестности элемента d k . Если функция (1) равна нулю, то выбранный элемент свободный; в противном случае – зан ятый. Если очередной элемент d k булевой матрицы С, через который долже н пройти путь занят, то из элемента d k -1 , который назове м элементом встречи с препятствием (на рисунке 2 это элемент 1), начинает ся обход препятствия. Этап 2. Переход от элемента встречи с препятствием к следующему свободному элементу пути выполняются согл асно правилу первого шага. Правило первого шага. Этап обхода пр епятствия начинается с элемента d k встречи с препятствием в направлении Z k , двоичный код которого определяется путем сложения кода пред шествующего направления ( Z ’ ) k -1 с кодом 001 по модулю 8 при отрицательном н аправлении обхода препятствий, а при положительном обходе – с кодом 111. Если выбранное направление запрещено, то принимаем первое возможное направление. При построении пути выполняется отрицательный (правый) и положительн ый (левый) обход всей группы препятствий, лежащих между конечными элем ентами пути. В этом случае у первого элемента встречи с препятствием п уть разветвляется на два. По одному пути осуществляется обход препятс твий справа, а по другому – слева. При построении Н-пути для обхода препятствий используется алгоритм Н- слежения, а при построении Р-пути – Р-слежение. При отрицательном направлении Р-слежения двоичный код приоритетного направления опреднляется соотношением , а при положительном . Если направление с высшим приоритетом запрещено, то выбираетс я первое возможное направление с низшим приоритетом. Определяемое со отношением , где n – двоичный код чи сел из последовательности 1, 2, …,8. Суммирование по модулю 8 выполняется при отрицательном направлении с лежения, вычитание – при положительном. Важным моментом является определение элемента, в котором заканчивает ся обход препятствий и начинается построение пути в оптимальном напр авлении (по прямой к элементу d b ). Если в нужный мом ент не прекратить обход препятствий, то неизбежно зацикливание пути в округ препятствий. Элемент пути, в котором прекращается обход препятс твий, назовем элементом спуска. На рисунке 2 элементом спуска является элемент 19. Здесь приведен путь в лабиринте, построенный согласно этой методике от элемента d a к элементу d b . От элемента d a до элемента 1, который является элементом встречи, выполн яется построение пути согласно этапу 1. Обход препятствий начинается от элемента встречи 1 в отрицательном направлении (этап 2) и заканчивае тся элементом спуска 19. От элемента спуска 19 до конечного элемента пути выполняется этап 1. Для определения элемента спуска пути предлагается следующий алгорит м: a) определяем двоичный к од угла поворота вектора перехода относительно вектора Z ’ из соотношения ; причем суммирование выполняется при отри цательном направлении обхода препятствий, вычитание – при положител ьном. b) В каждом элементе излома проверяем значение двоичного кода a k и направление построения пути в наилучшем направлени и. Если a k 0 и направление обхода препятствий совпадает с наилучшим направ лением построения пути, то элемент d k будет элементом спуска. В противном случае d k не является элементом спуска. Этап 3. Минимизация длинны пути сводится к постро ению выпуклого контура, описанного вокруг первоначального пути. Если нет возможности получить выпуклый контур из-за наличия препятствий, т о строится сглаженный контур, т.е. контур, имеющий меньшую длину, чем пе рвоначальный. Находим все элементы спуска первоначального пути и разбиваем его на отдельные участки, разграниченные элементами спуска. Последовательн о минимизируем все участки пути. 1) Находим все элементы и злома соответствующего участка пути, и если имеется не более одного и злома, то он не подлежит минимизации если элементов излома два и более , то минимизация заключается в том, что строится новый путь L н ( d a , d j ) пути L ( d a , d j ), где d j - элемент излома пути, самый близкий к конечному элементу. 2) Построенный вновь подп уть L н ( d a , d j ) сравнивается по длине с путем L ( d a , d j ) , и если новый путь меньше, то L ( d a , d j ) заменяется на L н ( d a , d j ) . 3) Минимизация повторяет ся для следующего элемента излома, самого близкого к d j , и до тех пор, пока на L н ( d a , d j ) или L ( d a , d j ) останется один элемент излома. Осуществляется минимизация обоих первоначально построенных путей, полученных при положительном (левом) и отрицательном (правом) об ходе группы препятствий, из которых выбирается минимальный (рисунок 3). 2. Волновой алгоритм трассировки. Дискретное поле платы разбивают на три множества, описываемых с помощью булевых матриц: С – множество элементов поля, требующих соединения между собой (на ри сунке 4 множество , где i = 0, 1, 2, 3); Р – множество элементов поля, запрещенных для трассировки (на рисунке 4,а(б) это множество закрашено черным); S – множество своб одных элементов поля платы. Требуется, используя элементы множества S , соединить элементы множества С в одну цепь, не пересекающую Р. Процесс нахождения минимального пути состоит из двух этапов: - Распространение волны от источника до встречи с одним из приемников; - Определение пути от источ ника к приемнику. В качестве источника в ыбирается один из элементов множества С, все остальные элементы являю тся приемниками. Обозначим через R k множество элементов вол ны на шаге k и назовем его k - фронтом волны, тогда R k +1 принадлежит Н-окрестности R k . На каждом шаге расширения делается проверка пересечения фонта волны с приемником. Как только какой-либо элемент приемника буд ет включен в волну, процесс распространения волны завершается, и от бл ижайшего к источнику элемента приемника начинается построение пути. Для построения волны используются матрицы распространения волн в го ризонтальном ( R k ’ ) , и вертикальном ( R k ) направлении и матрицы точек поворота с вертикального направления на горизонтальное ( M k ) и с горизонтального направления на вертикальное ( M k ’ ), где ; ; . На рисунке 5, а - г приведе ны соответственно матрицы R k , R k ’ , M k , M k ’ , построенные для k =12 . Источником является фрагмент С 0 . Для нагля дности в клетках, занятых волной, указывается номер шага, на котором до стигнута эта точка. На этапе построения пути определяется, каким фронтом достигнут прием ник: горизонтальным или вертикальным. От элемента пересечения волны с приемником в направлении, соответствующему последнему фронту волны, определяем элементы, не принадлежащие множеству Р. При встрече с перв ым же элементом множества точек поворота рассмотренного направления движение прекращается. Все пройденные элементы включаются в искомый путь. Элемент встречи принимается за исходный для движения по другому фронту волны. Направление чередуется таким образом до тех пор, пока не будет достиг нут элемент источника. На рисунке 5, д показан пример построения пути от приемника С 1 к источнику С 0 . Стрелкам и показано направление движения. В дальнейшем процесс распространени я волны повторяется с учетом построенного пути. Такой выбор источника обеспечивает ветвление цепи в любой ее точке. Процесс заканчивается, когда все элементы С будут связаны в единую це пь (рисунок 5, е), либо когда оставшиеся элементы этого множества уже не могут быть присоединены к источнику.
Читайте также: