Гридоид

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

Определения

Система множеств ( F , E ) представляет собой совокупность F подмножеств F основного множества E (т. е. является подмножеством степенного множества E ) . При рассмотрении гридоида член F называется допустимым множеством . При рассмотрении матроида допустимый набор также известен как независимый набор .

Доступная система множеств ( F , E ) — это система множеств, в которой каждое непустое допустимое множество X содержит элемент x такой, что $X\setminus \{x\}$ осуществимо. Это означает, что любая непустая, конечная , доступная система множеств обязательно содержит пустое множество ∅.

Гридоид свойству ( F , E ) — это доступная система множеств, которая удовлетворяет обмена :

• для всех $X,Y\in F$ с $|X|>|Y|,$ есть некоторые $x\in X\setminus Y$ такой, что $Y\cup \{x\}\in F.$

(Примечание: некоторые люди резервируют термин « свойство обмена» для состояния на основе гридоида и предпочитают называть приведенное выше условие «свойством увеличения».)

Базисом . гридоида является максимально допустимое множество, то есть это допустимое множество, но не содержащееся ни в каком другом Базис подмножества X в E — это максимально допустимое множество, содержащееся X. в

Ранг . гридоида равен размеру базиса По свойству обмена все базы имеют одинаковый размер.Таким образом, функция ранга определена корректно . Ранг подмножества X множества E это размер базиса X. — Как и матроиды, гридоиды обладают криптоморфизмом в терминах ранговых функций. Функция $r:2^{E}\to \mathbb {Z}$ является ранговой функцией гридоида на основном множестве E тогда и только тогда, когда r субкардинально , , монотонно и локально полумодулярно то есть для любого $X,Y\subseteq E$ и любой $e,f\in E$ у нас есть:

• субкардинальность : $r(X)\leq |X|$
• монотонность : $r(X)\leq r(Y)$ в любое время $X\subseteq Y\subseteq E$
• локальная полумодульность : $r(X)=r(X\cup \{e,f\})$ в любое время $r(X)=r(X\cup \{e\})=r(X\cup \{f\})$

Классы

Большинство классов гридоидов имеют множество эквивалентных определений в терминах системы множеств, языка, частичного множества, симплициального комплекса и т. д. Следующее описание идет по традиционному пути, перечисляя лишь пару наиболее известных характеристик.

Интервальный гридоид ( F , E ) — это гридоид, который удовлетворяет свойству интервала :

• если $A,B,C\in F$ с $A\subseteq B\subseteq C,$ тогда для всех $x\in E\setminus C:$

$${\begin{matrix}A\cup \{x\}\in F\\C\cup \{x\}\in F\end{matrix}}\implies B\cup \{x\}\in F.$$

Эквивалентно, интервальный гридоид — это такой гридоид, что объединение любых двух допустимых множеств возможно, если оно содержится в другом допустимом множестве.

Антиматроид свойству ( F , E ) — это гридоид, который удовлетворяет интервала без верхних границ :

• если ⁠ $A,B\in F$⁠ с ⁠ $A\subseteq B,$⁠ тогда для всех ⁠ $x\in E\setminus B,$⁠ ⁠ $A\cup \{x\}\in F$⁠ подразумевает ⁠ $B\cup \{x\}\in F.$⁠

Аналогично, антиматроид — это (i) гридоид с уникальной основой; или (ii) система доступных множеств, замкнутая при объединении. Легко видеть, что антиматроид также является интервальным гридоидом.

Матроид свойству ( F , E ) — это непустой гридоид, который удовлетворяет интервала без нижних границ :

• если ⁠ $B,C\in F$⁠ с ⁠ $B\subseteq C,$⁠ тогда для всех ⁠ $x\in E\setminus C,$⁠ ⁠ $C\cup \{x\}\in F$⁠ подразумевает ⁠ $B\cup \{x\}\in F.$⁠

Легко видеть, что матроид также является интервальным гридоидом.

Примеры

• неориентированный граф G. Рассмотрим Пусть основной набор — это ребра G , а допустимые множества — это набор ребер каждого леса (т. е. подграфа, не содержащего цикла) G . Эта система множеств называется цикловым матроидом . Система множеств называется графическим матроидом, если она является матроидом цикла некоторого графа. (Первоначально матроид цикла определялся на схемах или минимальных зависимых множествах . Отсюда и название цикла.)
• Рассмотрим конечный неориентированный граф G с корнем в вершине r . Пусть основным множеством будут вершины G , а допустимыми множествами будут подмножества вершин, содержащие r , которые индуцируют связные подграфы G . Это называется гридоидом поиска вершин и является разновидностью антиматроида.
• Рассмотрим конечный ориентированный граф D с корнем в точке r . Пусть основной набор — это (направленные) ребра D, а допустимые множества — это наборы ребер каждого направленного поддерева с корнем в r , причем все ребра направлены в сторону от r . Это называется гридоидом линейного поиска или направленным ветвящимся гридоидом . Это интервальный гридоид, но не антиматроид и не матроид.
• Рассмотрим M × n матрицу ​ . Пусть основным множеством E будут индексы столбцов от 1 до n , а допустимыми множествами будут $$F=\{X\subseteq E:{\text{ submatrix }}M_{\{1,\ldots ,|X|\},X}{\text{ is an invertible matrix}}\}.$$ Это называется гридоидом исключения Гаусса , поскольку эта структура лежит в основе алгоритма исключения Гаусса . Это гридоид, но не интервальный гридоид.

Жадный алгоритм

В общем, жадный алгоритм — это просто итерационный процесс, в котором лучший локально выбор , обычно вход максимального веса, выбирается каждый раунд, пока все доступные варианты не будут исчерпаны.Чтобы описать состояние, основанное на гридоидах, при котором жадный алгоритм является оптимальным (т. е. получает базис максимального значения), нам нужны некоторые более общие термины в теории гридоидов. Без ограничения общности рассмотрим гридоид G = ( F , E ) с E. конечным

Подмножество X из E является допустимым по рангу, наибольшее пересечение X с любым допустимым множеством имеет размер, равный рангу X. если В матроиде каждое подмножество E является допустимым по рангу.Но равенство не справедливо для гридоидов в целом.

Функция $w:E\to \mathbb {R}$ является R -совместимым, если $\{x\in E:w(x)\geq c\}$ является ли ранг допустимым для всех действительных чисел c .

Целевая функция $f:2^{S}\to \mathbb {R}$ линейна на множестве $S$ если для всех $X\subseteq S,$ у нас есть $f(X)=\sum _{x\in X}w(x)$ для некоторой весовой функции $w:S\to \Re .$

Предложение. Жадный алгоритм оптимален для каждой R -совместимой линейной целевой функции над гридоидом.

Интуиция, лежащая в основе этого предложения, заключается в том, что во время итерационного процесса каждый оптимальный обмен минимального веса становится возможным благодаря свойству обмена, а оптимальные результаты могут быть получены из допустимых множеств в базовом гридоиде. Этот результат гарантирует оптимальность многих известных алгоритмов. Например, минимальное остовное дерево можно взвешенного графа получить с помощью алгоритма Краскала , который является жадным алгоритмом для циклового матроида. Алгоритм Прима можно объяснить, взяв вместо него гридоид поиска строки.

См. также

• Матроид
• Полиматроид

Ссылки

• Бьёрнер, Андерс ; Циглер, Гюнтер М. (1992), «8. Введение в гридоиды» , в книге Уайт, Нил (ред.), Приложения Maroid , Энциклопедия математики и ее приложений, том. 40, Кембридж: Издательство Кембриджского университета, стр. 284–357 , номер документа : 10.1017/CBO9780511662041.009 , ISBN.  0-521-38165-7 , МР   1165537 , Збл   0772.05026
• Эдмондс, Джек (1971), «Матроиды и жадный алгоритм», Mathematical Programming , 1 : 127–136, doi : 10.1007/BF01584082 , S2CID   5599224 , Zbl   0253.90027 .
• Хелман, Пол; Море, Бернар М.Э.; Шапиро, Генри Д. (1993), «Точная характеристика жадных структур», SIAM Journal on Discrete Mathematics , 6 (2): 274–283, CiteSeerX   10.1.1.37.1825 , doi : 10.1137/0406021 , Zbl   0798.68061 .
• Корте, Бернхард ; Ловас, Ласло (1981), «Математические структуры, лежащие в основе жадных алгоритмов», в Гечеге, Ференц (редактор), «Основы теории вычислений: материалы Международной конференции FCT 1981 года», Сегед, Венгрия, 24–28 августа 1981 г. , лекция Заметки по информатике, том. 117, Берлин: Springer-Verlag , стр. 205–209, doi : 10.1007/3-540-10854-8_22 , Zbl   0473.68019 .
• Корте, Бернхард; Ловас, Ласло ; Шредер, Райнер (1991), Гридоиды , алгоритмы и комбинаторика, том. 4, Нью-Йорк, Берлин: Springer-Verlag , ISBN  3-540-18190-3 , Збл   0733.05023 .
• Оксли, Джеймс Г. (1992), Теория матроидов , Oxford Science Publications, Оксфорд: Oxford University Press , ISBN  0-19-853563-5 , Збл   0784.05002 .
• Уитни, Хасслер (1935), «Об абстрактных свойствах линейной независимости», American Journal of Mathematics , 57 (3): 509–533, doi : 10.2307/2371182 , hdl : 10338.dmlcz/100694 , JSTOR   2371182 , Zbl   0012.00404 .

Внешние ссылки

• Введение в Гридоиды
• Теория жадных алгоритмов. Архивировано 4 марта 2016 г. в Wayback Machine.
• Субмодулярные функции и оптимизация
• Сочетания, матроиды и субмодулярные функции