Реферат: Алгоритмы трассировки

--PAGE_BREAK--
Наименование  направлений  приведено  на  рисунке  1.



3

2

1

4

A



5

6

7

Рисунок  1.  Наименование  направлений  вектора  перемещения Zk.
После  каждого  шага  построения  пути  необходимо  по  вектору  перехода  Zk  определить  состояние  очередного  элемента  dk  (свободный  или  занятый)  булево  матрицы.  Рассмотрим  построение  Н-пути.

Для  описания  дискретного  пространства,  в  котором  строим  путь,  используем  булеву  матрицу  С  размером  m´n.  Кроме  того,  для  сокращения  вычислений  введем  усеченную  матрицу  А  размером  m´l.  Число  строк  в  матрице  А  определяется  шириной  прокладываемого  проводника  в  дискретах.  При  прокладке  проводников  шириной  в  один  дискрет   матрица  А  будет  матрицой-строкой,  только  один  элемент  которой  принимает  единичное  значение.  Номер  этого  элемента  определяется  координатой  xk  анализируемого  элемента  dk. 

Состояние  элементов  описывается  через  булеву  функцию

<img width=«91» height=«45» src=«ref-1_434553539-326.coolpic» v:shapes="_x0000_i1025">,

где  ci,j– элемент  матрицы  С;  ai  — элемент  матрицы-сторки  А.

Здесь  через  индекс  j  обозначается  номер  строки  матрицы  С,  который  определяется  координатой  yk  элемента  dk.

Если  V=1,  то  элемент dkзанят,  и  построение  пути  прекращается.  Дальнейшее  построение  осуществляется  путем  обхода  препятствий,  начиная  с  элемента dk-1,  который  будем называть  элементом  встречи  с  препятствием.

При  построении  Р-пути  распознавание  состояния  элемента  выполняется  в  два  этапа.  На  первом  этапе  определяем,  принадлежит  ли  элемент dkкакому-либо  объекту,  записанному  в  матрице  С.  Если  элемент dkне  принадлежит  никакому  объекту,  то  переходим  к  выполнению  второго  этапа,  суть  которого  сводится  к  следующему:  определяем  состояние  элементов,  которые  принадлежат  одновременно  Н-окрестностям  элементов dk, dk-1.  Таких  элементов  может  быть  только  два,  причем  они  расположены  диагонально.  Если  оба  элемента  заняты,  то  построение  пути  из  элемента dk-1в dkзапрещено.

При  построении  пути  в  диагональных  направлениях  состояния  элементов  описывается  булевой  функцией

<img width=«132» height=«24» src=«ref-1_434553865-346.coolpic» v:shapes="_x0000_i1026">,  i=1,  3,  5,  7.      (1)

Булевы  функции  Vi,  Vi-1,  Vi+1  определяются  при  просмотре 
Р-окрестности  элемента dk.  Если  функция  (1)  равна  нулю,  то  выбранный  элемент  свободный;  в  противном  случае – занятый.

Если  очередной  элемент dkбулевой  матрицы  С,  через  который  должен  пройти  путь  занят,  то  из  элемента dk-1,  который  назовем  элементом  встречи  с  препятствием  (на  рисунке  2  это  элемент  1),  начинается  обход  препятствия.

Этап  2.  Переход  от  элемента  встречи  с  препятствием  к  следующему  свободному  элементу  пути  выполняются  согласно  правилу  первого  шага.

Правило  первого  шага.  Этап  обхода  препятствия  начинается  с  элемента  dk  встречи  с  препятствием  в  направлении  Zk,  двоичный  код  которого  определяется  путем  сложения  кода  предшествующего  направления  (Z’)k-1   с  кодом  001  по  модулю  8  при  отрицательном  направлении  обхода  препятствий,  а  при  положительном  обходе – с  кодом  111.

Если  выбранное  направление  запрещено,  то  принимаем  первое  возможное  направление.

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

При  построении  Н-пути  для  обхода  препятствий  используется  алгоритм  Н-слежения,  а  при  построении  Р-пути – Р-слежение.

При  отрицательном  направлении  Р-слежения  двоичный  код  приоритетного  направления  опреднляется  соотношением

<img width=«189» height=«24» src=«ref-1_434554211-385.coolpic» v:shapes="_x0000_i1027">,
а  при  положительном

<img width=«191» height=«24» src=«ref-1_434554596-391.coolpic» v:shapes="_x0000_i1028">.

Если  направление  с  высшим  приоритетом  запрещено,  то  выбирается  первое  возможное  направление  с  низшим  приоритетом.  Определяемое  соотношением

<img width=«175» height=«24» src=«ref-1_434554987-389.coolpic» v:shapes="_x0000_i1029">,

где  n– двоичный  код  чисел  из  последовательности  1,  2,  …,8.

Суммирование  по  модулю  8  выполняется  при  отрицательном  направлении  слежения,  вычитание – при  положительном.

Важным  моментом  является  определение  элемента,  в  котором  заканчивается  обход  препятствий  и  начинается  построение  пути  в  оптимальном  направлении  (по  прямой  к  элементу  db). Если  в  нужный  момент  не  прекратить  обход  препятствий,  то  неизбежно  зацикливание  пути  вокруг  препятствий.  Элемент  пути,  в  котором  прекращается  обход  препятствий,  назовем  элементом  спуска.  На  рисунке  2  элементом  спуска  является  элемент  19.  Здесь  приведен  путь  в  лабиринте,  построенный  согласно  этой  методике  от  элемента  da  к  элементу   db. От  элемента  da  до  элемента  1,  который  является  элементом  встречи,  выполняется  построение  пути  согласно  этапу  1.  Обход  препятствий  начинается  от  элемента  встречи  1  в  отрицательном  направлении  (этап  2)  и  заканчивается  элементом  спуска  19.  От  элемента  спуска  19  до  конечного  элемента  пути  выполняется 
этап  1.

Для  определения  элемента  спуска  пути  предлагается  следующий  алгоритм:

a)      определяем  двоичный  код  угла  поворота  вектора  перехода  относительно  вектора  Z’  из  соотношения

<img width=«225» height=«25» src=«ref-1_434555376-437.coolpic» v:shapes="_x0000_i1030">;

причем  суммирование  выполняется  при  отрицательном  направлении  обхода  препятствий,  вычитание – при  положительном.

b)      В  каждом  элементе  излома  проверяем  значение  двоичного  кода  ak  и  направление  построения  пути  в  наилучшем  направлении.  Если ak³0  и  направление  обхода  препятствий  совпадает  с  наилучшим  направлением  построения  пути,  то  элемент  dk  будет  элементом  спуска.  В  противном  случае  dk  не  является  элементом  спуска.

Этап  3.  Минимизация  длинны  пути  сводится  к  построению  выпуклого  контура,  описанного  вокруг  первоначального  пути.  Если  нет  возможности  получить  выпуклый  контур  из-за  наличия  препятствий,  то  строится  сглаженный  контур,  т.е.  контур,  имеющий  меньшую  длину,  чем  первоначальный.

Находим  все  элементы  спуска  первоначального  пути  и  разбиваем  его  на  отдельные  участки,  разграниченные  элементами  спуска.  Последовательно  минимизируем  все  участки  пути.

1)      Находим  все  элементы  излома  соответствующего  участка  пути,  и  если  имеется  не  более  одного  излома,  то  он  не  подлежит  минимизации  если  элементов  излома  два  и  более,  то  минимизация  заключается  в  том,  что  строится  новый  путь  Lн(da, dj)  пути L(da, dj),  где   dj  — элемент  излома  пути,  самый  близкий  к  конечному  элементу.

2)      Построенный  вновь  подпуть Lн(da, dj)  сравнивается  по  длине  с  путем L(da, dj),  и  если  новый  путь  меньше,  то L(da, dj)  заменяется  на Lн(da, dj).

3)      Минимизация  повторяется  для  следующего  элемента  излома,  самого  близкого  к  dj,  и  до  тех  пор,  пока  на  Lн(da, dj)  или L(da, dj)  останется  один  элемент  излома.

Осуществляется  минимизация  обоих  первоначально  построенных  путей,  полученных  при  положительном  (левом)  и  отрицательном  (правом)  обходе  группы  препятствий,  из  которых  выбирается  минимальный 
(рисунок 3).
    продолжение
--PAGE_BREAK--