Материал: АиСД. Практикум (in dev)

Вариант 23. Путь из 1 в 9

5. Лабораторная работа -Эвристические алгоритмы

Цель работы: ознакомление с эвристическими алгоритмами и методикой оценки их эффективности .

Продолжительность работы: - 2 часа.

49. Теоретические сведения

Эвристический алгоритм – это алгоритм , в котором на определенном этапе используется интуиция разработчика . Если решение , принятое разработчиком , окажется неверным результат все равно будет получен , но за большее число шагов . Таким образом в эвристических алгоритмах можно увеличить скорость получения правильного результата

К эвристическим алгоритмам относятся : волновой , двухлучевой , четырехлучевой , маршрутный, алгоритмы составления расписания.

50. Волновой алгоритм

Волновой алгоритм или алгоритм Ли первоначально использовался для поиска пути в лабиринте или в игровых задачах. В настоящее время алгоритм Ли (волновой) является основным в микроэлектронике для трассировки (соединения) элементов интегральных схем. Особенность алгоритма состоит в следующем:

• В лабиринте( на подложке ) выбираются две точки А(начальная) и В(конечная). Из начальной точки в четырех направлениях выходит волна. Цифрами обозначается номер фронта волны или ее путевые координаты .

	1
1	А	1
	1

• Путевые координаты определяют шаг распространения волны. Каждый элемент первого фронта волны является источником вторичной волны.

Элементы второго фронта генерируют третий фронт и т.д. От запрещенных элементов волна не распространяется.

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

Вверх , Вниз , Влево , Вправо.

От того в каком порядке заданы приоритеты зависит скорость решения задачи.

При построении траектории используется два принципа:

1. Движение осуществляется строго по заданным приоритетам.

2. При построении трассы, т.е. траектории движения, значения путевых координат должны уменьшаться.

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

Найти путь между элементами А и В.

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

6		10	9	8		10
5				7		9	10
4			5	6		8	9	B
3	2		4	5		7	8		10
	1	2	3	4		6			9
1	А	1	2	3	4	5	6	7	8
2	1		3				7
3	2		4	5	6		8	9	10

51. Двухлучевой алгоритм.

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

Если же оба направления оказываются заблокированными запрещёнными элементами, либо достигнут край координатной сетки, то движение луча прекращается.

Выбор направления движения лучей происходит исходя из интуиции разработчика . Существуют варианты распространения лучей, которые выбираются из таблицы, после вычисления значений  и β.

где (X_A,Y_A) – координаты начального элемента,

(X_B,Y_B) – координаты конечного элемента.

Исходя из значений и выбирается вид распространения лучей:

Пример 2. Осуществить трассировку элементов а и в .