ВУЗ:
Составители:
Рубрика:
23
В общем случае весовая функция, или критерий качества пути, может
зависеть от параметров, учитывающих длину пути, число переходов со
слоя на слой, степень близости пути к другим и т.д., например в виде адди-
тивной функции P(k)=∑a(i)·p
i
(k), где a(i) – весовой коэффициент, учиты-
вающий важность i-го параметра; р
i
(k) – значение учитываемого парамет-
ра.
Однако усложнение функции веса увеличивает объем информации на
одну ячейку ДРП и время работы первой части алгоритма. Кроме того, не
представляется возможным строго обосновать выбор значений весовых
коэффициентов а(i).
При практической реализации волнового алгоритма важная проблема
– сокращение объема памяти, необходимой для запоминания веса ячеек.
При вычислении
веса ячеек по указанной выше формуле ячейка может
быть в таких состояниях: свободна, занята или имеет вес от единицы до L,
где L – максимально возможная длина пути, определяемая как количество
составляющих его ячеек ДРП. Необходимое для запоминания состояния
одной ячейки ДРП число разрядов памяти N = log2 (L + 2).
Наиболее эффективными способами кодирования состояния ячеек
ДРП являются метод путевых координат, кодирование по модулю 3 и ис-
пользование базовой последовательности, предложенной Акерсом.
При выборе последовательности ячеек на этапе построения пути
по
методу путевых координат для каждой ячейки, начиная с В
, в случае со-
седства по ребрам достаточно знать, от какой соседней ячейки в нее при-
шла волна: сверху, слева, снизу, справа (↑,←,↓,→). Таким образом, ячейка
может иметь признаки: свободна, занята или одну из путевых координат:
↑,←,→,↓. Следовательно, число разрядов на кодирование состояния ячеек
N = log2(6) = 3. Если
в данную ячейку волна приходит из нескольких со-
седних, то присвоение путевых координат выполняется по заранее задан-
ному правилу приоритетов. При проведении пути достаточно переходить
по путевым координатам из ячейки В в ячейку A.
Кодирование по модулю 3 базируется на основном требовании к весу:
Р(k-1) ≠ Р(k) ≠ Р(k+1). Ячейкам, включаемым в
последовательные фронты,
можно присваивать не сам вес, а его значение по модулю 3, т.е. 1,2,3, 1,2,3,
... Количество разрядов на кодирование состояния ячеек N = log2(5) = 3.
Проведение пути заключается в отслеживании отметок. Если ячейка имеет
несколько соседних с одинаковыми отметками, то используется правило
приоритетных направлений.
Для определения последовательности ячеек, составляющих путь, дос-
таточно, чтобы при распространении
волны ячейкам присваивались значе-
ния отметок из заданной последовательности, в которой каждый член име-
ет разных соседей слева и справа. В методе Акерса такой последователь-
ностью является 1,1,2,2,1,1,2,2, ... При построении пути находят ячейки,
входящие в заданную последовательность. В методе Акерса кoличество
Страницы
- « первая
- ‹ предыдущая
- …
- 21
- 22
- 23
- 24
- 25
- …
- следующая ›
- последняя »
