Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Гриди-алгоритмы
В гриди-алгоритмах (англ. 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 в качестве первой внутренней вершины.
Так что мы получаем длину кратчайшего пути как минимум из длин кратчайшего пути, который не содержит w, и кратчайшего пути, который содержит w в качестве первой внутренней вершины.
Заметим, однако, что гриди-принцип не всегда применим, поскольку локальная оптимизация не всегда приводит к глобальной оптимизации. Пример тому мы получим, если попытаемся идею алгоритма Дейкстры перенести на целочисленно размеченные графы. Здесь могут существовать пути с отрицательными значениями, так что обход через далеко удаленные вершины может, тем не менее, вести к более короткому пути.
Работа с задачами большой сложности требует глубокого анализа постановки задачи. Путем упрощения постановки задачи, например через ограничения на область значений параметров, в некоторых случаях можно сделать применимыми менее сложные алгоритмы. Важно также, сколь многочисленны на самом деле входные данные для рассматриваемой задачи. При небольшой размерности могут непосредственно решаться (англ. brute force) даже NP-полные проблемы.
