Введение

Система множеств, используемая в жадной оптимизации

В комбинаторике гредиоид — это тип системы множеств. Он берет начало в понятии матроида, который был первоначально введен Уитни в 1935 году для изучения планарных графов и позднее использован Эдмондсом для характеристики класса задач оптимизации, решаемых жадными алгоритмами. Около 1980 года Корте и Ловас ввели гредиоид для дальнейшей обобщенной характеристики жадных алгоритмов, отсюда и название «гредиоид». Помимо математической оптимизации, гредиоиды также связаны с теорией графов, теорией языков, теорией порядка и другими областями математики.

Примеры

Рассмотрим ненаправленный граф G. Пусть базовым множеством будут ребра G, а допустимыми множествами – множества ребер каждого леса (то есть подграфа, не содержащего циклов) графа G. Эта система множеств называется циклическим матроидом. Система множеств называется графическим матроидом, если она является циклическим матроидом некоторого графа. (Первоначально циклический матроид был определен на циклах, или минимально зависимых множествах. Отсюда и название «циклический»). Рассмотрим конечный ненаправленный граф G, укорененный в вершине r. Пусть базовым множеством будут вершины G, а допустимыми множествами – подмножества вершин, содержащие r, которые индуцируют связные подграфы G. Это называется жадностью поиска вершин и является разновидностью антиматроида. Рассмотрим конечный ориентированный граф D, укорененный в r. Пусть базовым множеством будут (ориентированные) ребра D, а допустимыми множествами – множества ребер каждого ориентированного поддерева, укорененного в r, со всеми ребрами, направленными от r. Это называется жадностью поиска по линиям, или ориентированным ветвящимся жадностью. Это интервальная жадность, но не антиматроид и не матроид. Рассмотрим матрицу m × n M. Пусть базовым множеством E будут индексы столбцов от 1 до n, а допустимыми множествами – Это называется жадностью гауссова исключения, поскольку эта структура лежит в основе алгоритма гауссова исключения. Это жадность, но не интервальная жадность.

Алгоритм жадности

В общем, жадный алгоритм – это просто итеративный процесс, в котором на каждом шаге выбирается локально лучший выбор, обычно элемент с максимальным весом, до тех пор, пока не будут исчерпаны все доступные варианты. Чтобы описать условие, основанное на жадности, при котором жадный алгоритм является оптимальным (то есть, находит базис максимального значения), нам потребуется некоторая дополнительная общепринятая терминология из теории жадности. Без ограничения общности, рассмотрим жадность 1=G = (F, E) с конечным E. Подмножество X из E называется рангово допустимым, если наибольшее пересечение X с любым допустимым множеством имеет размер, равный рангу X. В матроиде каждое подмножество E рангово допустимо. Однако это равенство не выполняется для жадностей в общем случае. Функция R-совместима, если она рангово допустима для всех действительных чисел c. Объективная функция линейна над множеством, если для всех выполняется равенство для некоторой весовой функции. Жадный алгоритм оптимален для каждой R-совместимой линейной объективной функции над жадностью. Интуиция, лежащая в основе этого утверждения, заключается в том, что в процессе итераций каждый оптимальный обмен минимального веса становится возможным благодаря свойству обмена, и оптимальные результаты могут быть получены из допустимых множеств в базовой жадности. Этот результат гарантирует оптимальность многих известных алгоритмов. Например, минимальное остовное дерево взвешенного графа может быть получено с помощью алгоритма Крускала, который является жадным алгоритмом для циклического матроида. Алгоритм Прима можно объяснить, используя вместо него жадность линейного поиска.