12. Алгоритмы нахождения кратчайших деревьев в графе.

Пусть имеется связный неориентированный граф G(V,E), в котором V – множество контактов, а E – множество их возможных попарных соединений. Для каждого ребра графа (u,v) задан неотрицательный вес w(u,v). Задача состоит в нахождении подмножества T E , связывающего все вершины, для которого суммарный вес минимален.

Общая схема алгоритмов такова. Искомое дерево строится постепенно: к изначально пустому множеству A на каждом шаге добавляется одно ребро.

Множество A всегда является подмножеством некоторого минимального дерева. Ребро (u,v), добавляемое на очередном шаге, выбирается так, чтобы не нарушить этого свойства.

Алгоритм Краскала: Рисуем граф, добавляем вес, на каждом этапе выбираем ребро с минимальным весом, так, чтобы не было циклов.

Алгоритм Прима: Формируем дерево из произвольной вершины. Далее выбираем ребро, не относящееся к этому дереву, с минимальным весом.

12. Алгоритм Дейкстры (нахождение кратчайшего пути в графе)

Алгоритм Дейкстры всякий раз выбирает для обработки вершины с наименьшей оценкой кратчайшего пути.

На каждой итерации выбирается вершина u, имеющая минимальное значение d (выделена серым цветом). (б-е) Вершина и с наименьшим значением d[u] изымается из очереди Q = V \ S и добавляется к множеству S (в первый раз имеем и = s), при этом могут измениться оценки d[v] вершин, смежных с u .

12. Алгоритм а* (нахождение кратчайшего пути в графе).

Итак, пусть g(v) – стоимость пути от источника до вершины v;

h(v) – нижняя оценка стоимости пути от вершины v до приемника (в качестве h(v) для данной задачи примем расстояние от вершины v до приемника);

f(v) = g(v) + h(v) - нижняя оценка стоимости пути от источника до приемника, проходящего через вершину v.

1) Среди вершин графа, граничащих с приемником, найти вершину v, имеющую наименьшую оценку f(v);

2) Если вершина v не граничит с источником определить среди вершин, достижимых из v, вершину v1 с наименьшей оценкой f1(v);

3) Если вершина v граничит с источником, она является единственной вершиной графа между источником и приемником;

4) Поиск прекращается, когда найдена вершина vn, граничащая с источником.

12. Алгоритм Ли (нахождение кратчайшего пути в решетчатом графе).

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

Пусть требуется найти путь в лабиринте от точки A до точки B. Запишем единицу в каждую пустую ячейку, являющуюся непосредственным соседом ячейки A (рис.2.6.b).

Затем во все пустые ячейки, которые соседствуют с ячейками, содержащими единицы, вписываются двойки. Затем за цифрами 2 записываются цифры 3 и т.д. Процесс продолжается до тех пор, пока не произойдет одно из двух событий:

• все пути окажутся заблокированными, т.е. на k-м шаге не останется пустых ячеек, соседствующих с ячейками, содержащими число (k – 1);

• будет достигнута ячейка, содержащая B. В последнем случае запускается «обратная волна» и легко определяется кратчайший путь (или пути) между точками A и B.