Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Гриди-алгоритмы


В гриди-алгоритмах (англ. greedy - «жадный») пытаются решить задачу глобальной оптимизации с помощью локальных критериев оптимизации. Типичным примером является следующий алгоритм , по  которому находится длина кратчайшего пути в графе. В этом алгоритме , исходя из начальной вершины, строится путь таким образом, что по мере надобности выбираются вершины с минимальным рассеянием от её вершины Т.

Пример (алгоритм Дейкстры для вычисления кратчайшего пути в графе с нагруженными ребрами). Пусть дано множество вершин

V={l,...,n} и расстояния между ними d:VxV®Nu{¥}.

Предположим, что d есть всюду определенная функция.  Если не существует ребра от вершины Х к вершине У, то это выражается через:

d(x,y) = ¥

Для вычисления длины кратчайшего пути служит следующее предписание (тип enat содержит натуральные числа и ¥)

fct dijkstra = (set node m, node x, node y) enat

   if m = 0

   then d(x, y)

   else node w == some node z: z Î m Ù " node b: b Î m Þ d(x, z) £ d(x,b); min(diJkstra(m\{w}, x, y), d(x, w)+dijkstra(m\{w},w,y )      

Используется следующий инициализирующий вызов: dijkstra(V, x, у).

Корректность этого предписания можно показать следующим образом : для любого множества S с V вызов

dijkstra (S, х, у)

дает длинукратчаишего пути от х к у - с внутренними вершинами только из множества S. Это утверждение доказывается индукцией по n=|S|

Для n = О утверждение очевидно. Пусть утвержедние справедливо для п; для любого множества S с |s|= n+1 пусть w есть вершина из S с наименьшим удалением от х: V be S: d(x, w) £ d(x, b). Пусть x® pi...® pk® y есть путь кратчайшей длины от х к у с внутренними вершинами pi Î S для всех i, 1 £

i £ k. Или справедливо w  Ï {pi, ..., pk}, или справедливо pi = we I <, i ^ k. Но тогда должно быть i = 1, так как в противном случае путь х ® pi ®... ® pk ® У был бы короче. Итак, справедливо: кратчайший путь не содержит вершины w, или он содержит w в качестве первой внутренней вершины.


Начало  Назад  Вперед



Книжный магазин