Greedoid

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

• 1 Определения
• 2 Классы
• 3 Примеры
• 4 Жадный алгоритм
• 5 См. Также
• 6 Ссылки
• 7 Внешние ссылки

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

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

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

• для всех X, Y ∈ F с | X |>| Y |, существует некоторый x ∈ X \ Y такой, что Y∪ {x} ∈ F

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

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

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

• субмодуль : $r\; (X)\; \le \; |\; X\; |\; \{\backslash \; displaystyle\; r\; (X)\; \backslash \; leq\; |\; X\; |\}$;
• монотонность : $r\; (X)\; \le \; r\; (Y)\; \{\backslash \; displaystyle\; r\; (X)\; \backslash \; leq\; r\; (Y)\}$всякий раз, когда $Икс\; \subseteq \; Y\; \subseteq \; E\; \{\backslash \; displaystyle\; X\; \backslash \; substeq\; Y\; \backslash \; substeq\; E\}$; и
• локальная полумодулярность : $r\; (X)\; =\; r\; (X\; \cup \; \{e,\; f\})\; \{\backslash \; displaystyle\; r\; (X)\; =\; r\; (X\; \backslash \; cup\; \backslash \; \{e,\; f\; \backslash \})\}$всякий раз, когда $r\; (X)\; =\; r\; (X\; \cup \; \{e\})\; =\; r\; (X\; \cup \; \{f\})\; \{\backslash \; displaystyle\; r\; (X)\; =\; r\; (X\; \backslash \; cup\; \backslash \; \{e\; \backslash \})\; =\; r\; (X\; \backslash \; cup\; \backslash \; \{f\; \backslash \})\}$.

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

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

• если A, B, C ∈ F с A ⊆ B ⊆ C, то для все x ∈ E \ C, (A∪ {x} ∈ F и C∪ {x} ∈ F) влечет B∪ {x} ∈ F

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

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

• , если A, B ∈ F с A ⊆ B, то для всех x ∈ E \ B из A∪ {x} ∈ F следует B∪ {x} ∈ F

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

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

• если B, C ∈ F с B ⊆ C, то для всех x ∈ E \ C, C∪ {x} ∈ F влечет B∪ {x} ∈ F

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

• Рассмотрим неориентированный граф G. Пусть базовым набором будут ребра G, а допустимые множества - набором ребер каждого леса (т. Е. Подграфа, не содержащего цикла) G. Эта система множеств называется матроидом цикла . Система множеств называется графическим матроидом, если это матроид цикла некоторого графа. (Первоначально матроид цикла был определен на схемах или минимальных зависимых наборах. Отсюда и название цикла.)
• Рассмотрим конечный неориентированный граф G с корнем в вершине r. Пусть базовое множество - это вершины графа G, а допустимые множества - это подмножества вершин, содержащие r, которые индуцируют связные подграфы графа G. Это называется гридоидом поиска вершин и является своего рода антиматроидом.
• Рассмотрим конечный ориентированный граф D с корнем в r. Пусть основной набор будет (направленными) ребрами D, а допустимые наборы - наборами ребер каждого направленного поддерева с корнем r, причем все ребра направлены от r. Это называется гридоидом поиска по строке или гридоидом направленного ветвления . Это интервальный гридоид, но не антиматроид и не матроид.
• Рассмотрим матрицу m × n M. Пусть базовое множество E будет индексами столбцов от 1 до n, а допустимые множества будут F = {X ⊆ E: подматрица M {1,..., | X |}, X - обратимая матрица }. Это называется гридоидом исключения Гаусса, поскольку эта структура лежит в основе алгоритма исключения Гаусса. Это жадный алгоритм, но не интервальный гридоид.

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

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

Функция w: E → ℝ является R-совместимой, если {x ∈ E: w (x) ≥ c} является допустимым рангом для всех действительных чисел c.

Целевая функция f: 2 → ℝ является линейной над множеством S, если для всех X ⊆ S выполняется f (X) = Σ x ∈ X w (x) для некоторой весовой функции w: S → ℜ.

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

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

• Matroid
• Polymatroid

• Бьёрнер, Андерс ; Циглер, Гюнтер М. (1992), «8. Введение в гридоиды», в Уайт, Нил (ред.), Приложения Matroid, Энциклопедия математики и ее приложений, 40, Кембридж: Cambridge University Press, стр. 284–357, doi : 10.1017 / CBO9780511662041.009, ISBN 0-521-38165-7, MR 1165537, Zbl 0772.05026 CS1 maint: ref = harv (ссылка )
• Эдмондс, Джек (1971), «Матроиды и жадный алгоритм», Математическое программирование, 1 : 127–136, doi : 10.1007 / BF01584082, Zbl 0253.90027.
• Helman, Paul; Moret, Bernard ME; Shapiro, Henry D. (1993), «Точная характеристика жадных структур», Журнал SIAM по дискретной математике, 6(2): 274–283, CiteSeerX 10.1.1.37.1825, doi : 10.1137 / 0406021, Zbl 0798.68061.
• Корте, Бернхард ; Ловас, Ласло (1981), «Математические структуры, лежащие в основе жадных алгоритмов», в Gecseg, Ferenc (ред.), Основы теории вычислений: материалы Международной конференции FCT 1981 г., Сегед, Венгрия, 24–28 августа 1981 г., Lecture Notes in Computer Science, 117, Berlin: Springer -Verlag, стр. 205–209, doi : 10.1007 / 3-540-10854-8_22, Zbl 0473.68019.
• Корте, Бернхард; Ловас, Ласло ; Schrader, Rainer (1991), Greedoids, Algorithms and Combinatorics, 4, New York, Berlin: Springer-Verlag, ISBN 3-540- 18190-3, Zbl 0733.05023.
• Оксли, Джеймс Г. (1992), теория матроидов, Oxford Science Publications, Oxford: Oxford University Press, ISBN 0-19-853563-5, Zbl 0784.05002.
• Уитни, Хасслер (1935), «О абстрактные свойства линейной независимости », American Journal of Mathematics, 57(3): 509–533, doi : 10.2307 / 2371182, hdl : 10338.dmlcz / 100694, JSTOR 2371182, Zbl 0012.00404.

• Введение в Greedoids
• Теория жадных алгоритмов
• Субмодульные функции и оптимизация
• Сопоставления, матроиды и субмодульные функции