Информационные технологии проектирования электронных средств

- 69 - Перед началом работы алгоритма ячейка-источник А вводится в списки L 1 и (или) L 2 ; индекс длины P , а также индексы переходов ν 1 и ν 2 полагаются равными нулю. Списки М 1 и М 2 – пусты. Будем считать, что цена одного пере- хода равна единице длины. Образование очередного фронта складывается из следующих операций: 1. Увеличить индекс P на единицу. 2. Исследовать в ДРП 1 окреcтность очередной ячейки списка L 1 , выбрать свободные и неотмеченные ячейки и записать их в список М 1 . 3. Каждую из этих ячеек отметить в ДРП 1 индексом P и индексом ν , рав- ным соответствующему индексу очередной ячейки из L 1 . 4. Повторить пункты 2 и 3 для всех ячеек списка L . 5. Очистить список L 1 и передать в него содержимое списка М 1 ; очистить список М 1 . 6. Добавить в список L 1 те ячейки из списка L 2 , в которых возможен пере- ход из слоя 2 в слой 1 и которые не были отмечены в ДРП 1 , увеличив значение ν 1 на единицу. 7. Отметить в ДРП 1 эти ячейки индексом P и индексом ν 1 . 8. Выполнить пункты 2, …, 7 для слоя 2, используя соответствующие спис- ки. 9. Если ячейка-цель B не обнаружена в списке L 1 или L 2 и оба списка L 1 и L 2 одновременно не пусты, повторить операции пунктов 1 – 8. Если же списки L 1 и L 2 пусты, искомого пути не существует. Если ячейка B обнаружена, перейти к построению пути. На рис. 39 показан процесс распространения волны из ячейки А, отмечен- ной как источник на обоих слоях. Для наглядности сохранены абсолютные значения индекса P. Ячейка В обнаружена на 15-м шаге в слое 1. Для построения пути необходимо, начиная с ячейки B , двигаться в направлении уменьшения индекса P вплоть до достижения ячейки А .