Описание волнового алгоритма

Рассматривается алгоритм построения ортогонального пути. Алгоритм состоит из двух частей. В первой от источника к приемнику распространяется волна. Во второй выполняется обратный ход, в процессе которого из ячеек волны формируется путь.

Волна, идущая от источника к приемнику, на каждом шаге первой части алгоритма пополняется свободными ячейками ДРП, которые, во-первых, еще не принадлежат волне, и, во-вторых, являются 4-соседями ячеек, попавших в волну на предыдущем шаге.

Процесс распространения волны иллюстрируют рис. 9.3-9.6.

Рис. 9.3. Первый шаг распространения волны

Рис. 4. Второй шаг распространения волны

Рис. 9.5. Третий шаг распространения волны

Рис. 9.6. Последний шаг распространения волны

В примере волна достигла ячейку-приемник за 23 шага.

При обратном ходе в путь включается по одной ячейке каждого шага распространения волны. При выборе из двух ячеек приоритет имеет ячейка, обеспечивающая горизонтальное продвижение, что приводит к пути, показанному на рис. 9.7.

Рис. 7. Обратный ход: формирование пути

Волновой алгоритм либо находит кратчайший путь от источника к приемнику, либо информирует о неудаче, если путь к приемнику блокируется препятствиями.

Оглавление

Лекция 9. 1

Трассировка соединений. 1

Алгоритмы трассировки соединений. 5

Алгоритмы трассировки проводных соединений. 8

Алгоритм Прима. 10

Пример. 13

Алгоритм разводки проводных соединений с заданными начальной и конечной вершинами 16

Построение печатных соединений. 21

Пример волнового алгоритма. 25

Описание волнового алгоритма. 26