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

52. Четырехлучевой алгоритм

Из начальной и конечной точек выходят одновременно по четыре луча. Лучи движутся строго по заданным направлениям и “затухают”, если достигли края координатной сетки, либо встретили запрещенный элемент.

Пример 3.

53. Маршрутный алгоритм.

Маршрутный алгоритм получил свое название, потому что осуществляет одновременно и формирование фронта и прокладывание трассы. Источником волны на каждом шаге является конечный элемент участка трассы проложенной на предыдущих шагах.

В маршрутном алгоритме рассматриваются восьмиэлементная окрестность исходного элемента.

От каждого элемента окружения оценивается расстояние d до конечного элемента B.

d = или d =

Таким образом определяются восемь значений расстояний, из которых выбирается минимальное. Элемент для которого d оказалось минимальным считаем элементом трассы. Процесс повторятся до тех пор пока расстояние не будет равным нулю (d=0) т.е. пока не будет достигнут конечный элемент. Обход запрещенных элементов осуществляется исходя из интуиции разработчика.

Пример:

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

54. Геометрическая модель задачи о лабиринте

  В лабиринте с произвольными препятствиями найти кратчайший путь между

заданными точками.

   Решение: Так как препятствия на местности образуют многоугольники, или какие либо другие геометрические фигуры (которые с некоторыми погрешностями тоже можно изобразить в виде многоугольников), то кратчайшая трасса будет являться ломанной с узлами в вершинах этих многоугольников. Звено ломаной – это либо сторона многоугольника, либо прямолинейный отрезок, проходящий вне многоугольников и соединяющий две вершины одного и того же или разных многоугольников. Для решения этой задачи нужно построить сеть (ломаную), а так же соединить точки s и t с простреливаемыми из них вершинами, если эти точки не являются вершинами многоугольников.

   Формирование сети, т. е. матрицы расстояний С размером nxn (n – общее число вершин всех многоугольников плюс два для учета старта и финиша) представляет собой тройной цикл. Внешний – по i – перебор вершин, откуда стреляют; средний – по j (j от i+1 до n, чтобы не повторяться) – это перебор вершин, куда стреляют; и внутренний – по k – это проверка, не пересекает ли k-я сторона какого-либо многоугольника отрезок соединения.

   Последнее условие, в случае, как на рис. 8,проверяется по стандартным формулам аналитической геометрии: выписывается уравнение прямой, проходящей через i, j, выписывается уравнение прямой проходящей через концы отрезка k, решением системы из этих двух уравнений находится точка пересечения и устанавливается, лежит ли точка пересечения внутри рассматриваемых отрезков. Если да, то d_ij=, конец цикла по k, если нет пересечения по окончанию цикла по k, то вычисляется Евклидово расстояние d_ij.

   В случае на рис. 9, ситуация сложнее: между вершинами i и j не проходит ни какой стены, а j из i не простреливается. Чтобы преодолеть эту трудность, нужно ввести характеристику i угла препятствия: g_i присвоив g_i =0, если (“вогнутый” угол), или gi =1, если (“выпуклый” угол). Так, для угла с вершиной i на рис. 9 g_i =1, а для угла с вершиной j g_i =0.     Если крайние вершины x_i и x_i+3 (x_i, x_i+1, x_i+2, x_i+3 – последовательные вершины многоугольника) лежат по одну сторону от прямой, проходящей через соседние вершины x_i+1, x_i+2, то g_i+1= g_i+2 ,иначе g_i+1<> g_i+2.

(х- xi+1)( уi+2-уi+1)-( xi+2-xi+1)(у- уi+1)=0

    Если при подстановке в это уравнение точек (xi, уi) и (xi+3, уi+3) в левой части получаются числа с одинаковым знаком, то g_i+1= g_i+2, иначе g_i+1<> g_i+2. После этого цикла будут известны все g_i точно или с точностью до наоборот. Остается абсолютно установить g_i хотя бы для одной вершины. Это легко сделать, потому что экстремальная вершина имеет g₀ =1.     Теперь можно справиться с трудностью, показанной на рис. 9. Из вершины i не простреливается никакая вершина j, защищенная углом с вершиной i. Чтобы исключить из рассмотрения загороженные вершины, нужно отступить от вершины i по сторонам угла на величину заведомо меньшую, чем длина стороны, построив таким образом точки и . После чего нужно ввести бинарную величину В, В=1, если отрезки и ij пересекаются; и В=0, если отрезки и ij не пересекаются. Как например на рис. 10