Алгоритм построения базы в объединении матроидов — различия между версиями
Vsklamm (обсуждение | вклад) (Метки: правка с мобильного устройства, правка из мобильной версии) |
м (rollbackEdits.php mass rollback) |
||
(не показано 29 промежуточных версий 6 участников) | |||
Строка 14: | Строка 14: | ||
Пусть <tex>I_i \in \mathcal{I}_i</tex>, для <tex>i = 1\ldots k</tex> с <tex>I_i \cap I_j = \emptyset</tex>, если <tex>i \neq j</tex>. Определим [[Граф замен|граф замен]]: для каждого <tex>M_i</tex> построим [[Основные определения теории графов#defBiparateGraph|двудольный ориентированный граф]] <tex>D_{M_i}(I_i)</tex> так, что в левой доле находятся вершины из <tex>I_i</tex>, а в правой — вершины из <tex>S \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S \setminus I_i</tex>, при условии, что <tex>(I_i \setminus y) \cup x \in \mathcal{I}_i</tex>. | Пусть <tex>I_i \in \mathcal{I}_i</tex>, для <tex>i = 1\ldots k</tex> с <tex>I_i \cap I_j = \emptyset</tex>, если <tex>i \neq j</tex>. Определим [[Граф замен|граф замен]]: для каждого <tex>M_i</tex> построим [[Основные определения теории графов#defBiparateGraph|двудольный ориентированный граф]] <tex>D_{M_i}(I_i)</tex> так, что в левой доле находятся вершины из <tex>I_i</tex>, а в правой — вершины из <tex>S \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S \setminus I_i</tex>, при условии, что <tex>(I_i \setminus y) \cup x \in \mathcal{I}_i</tex>. | ||
− | Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов. Пусть для каждого <tex>i:</tex> <tex>F_i</tex> {{---}} множество элементов <tex>s \notin I_i</tex> с <tex>I_i \cup {s} \in \mathcal{I}_i</tex>. Определим <tex>I = I_1 \cup \ldots \cup I_k</tex> | + | Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов. Пусть для каждого <tex>i:</tex> <tex>F_i</tex> {{---}} множество элементов <tex>s \notin I_i</tex> с <tex>I_i \cup {s} \in \mathcal{I}_i</tex>. Определим <tex>I = I_1 \cup \ldots \cup I_k</tex>, <tex>F = F_1 \cup \ldots \cup F_k</tex> и <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex>. |
− | |||
− | |||
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. На каждом шаге мы выбираем элемент не из текущего множества в новом графе замен <tex>D_{M_i}(I_i)</tex> ([[Алгоритм построения базы в объединении матроидов#th_1|следующая теорема]] отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как <tex>I</tex>. | Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. На каждом шаге мы выбираем элемент не из текущего множества в новом графе замен <tex>D_{M_i}(I_i)</tex> ([[Алгоритм построения базы в объединении матроидов#th_1|следующая теорема]] отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как <tex>I</tex>. | ||
− | Тогда нужно найти такой элемент <tex>s \in S \setminus I</tex>, что <tex>I | + | Тогда нужно найти такой элемент <tex>s \in S \setminus I</tex>, что <tex>I \cup s</tex> — снова независимо. |
Все наши кандидаты находятся в <tex>S \setminus I</tex> . Если мы найдем путь из <tex>F</tex> в <tex>S \setminus I</tex>, то элемент <tex>s</tex>, которым путь закончился, можно будет добавить в <tex>I</tex>. | Все наши кандидаты находятся в <tex>S \setminus I</tex> . Если мы найдем путь из <tex>F</tex> в <tex>S \setminus I</tex>, то элемент <tex>s</tex>, которым путь закончился, можно будет добавить в <tex>I</tex>. | ||
То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути. | То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути. | ||
− | + | '''Псевдокод''' | |
<tex>J</tex> = <tex>\emptyset</tex> | <tex>J</tex> = <tex>\emptyset</tex> | ||
'''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>n - 1</tex> | '''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>n - 1</tex> | ||
Строка 29: | Строка 27: | ||
'''if''' <tex>I_i + s \in \mathcal{I}_i</tex> | '''if''' <tex>I_i + s \in \mathcal{I}_i</tex> | ||
<tex>J \leftarrow I_i + s</tex> | <tex>J \leftarrow I_i + s</tex> | ||
+ | |||
+ | '''Время работы''' | ||
+ | |||
+ | Это подразумевает, что максимальное независимое множество в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex> мы можем найти за полиномиальное время (жадно наращивать независимое множество в <tex>M = M_1 \cup \ldots \cup M_k</tex>). Cunningham<ref>Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, стр.732</ref> разработал алгоритм, которым за <tex>O((n^{(3/2)} + k)mQ + n^{(1/2)}km)</tex> можно найти максимальное независимое множество в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex>, где <tex>n</tex> максимальный размер множества в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex>, <tex>m</tex> размер подмножества и <tex>Q</tex> время, необходимое, чтобы определить принадлежит ли множество <tex> \mathcal{I}_j</tex> для каждого <tex>j</tex>. Более детальное объяснение алгоритма (но не время работы) можно найти у C. Greene и T.L. Magnanti<ref>C. Greene, T.L. Magnanti, Some abstract pivot algorithms, SIAM Journal on Applied Mathematics, p.530-539</ref>. | ||
Строка 34: | Строка 36: | ||
|id=th_1 | |id=th_1 | ||
|statement= | |statement= | ||
− | Для любого <tex>s \in S \setminus I</tex> имеем <tex>I | + | Для любого <tex>s \in S \setminus I</tex> имеем <tex>I \cup s \in \mathcal{I} \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам графа <tex>D</tex>. |
|proof= | |proof= | ||
<tex>\Leftarrow</tex> | <tex>\Leftarrow</tex> | ||
Строка 57: | Строка 59: | ||
* [[Пересечение матроидов, определение, примеры]] | * [[Пересечение матроидов, определение, примеры]] | ||
* [[Алгоритм построения базы в пересечении матроидов]] | * [[Алгоритм построения базы в пересечении матроидов]] | ||
+ | |||
+ | == Примечания == | ||
+ | <references/> | ||
== Источники информации == | == Источники информации == | ||
[https://math.mit.edu/~goemans/18438F09/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13] | [https://math.mit.edu/~goemans/18438F09/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13] | ||
+ | |||
+ | Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, {{---}} Springer, 2004, {{---}} стр.732 | ||
+ | |||
+ | [http://booksc.org/book/18618751/0b4420 C. Greene, T.L. Magnanti, Some abstract pivot algorithms, SIAM Journal on Applied Mathematics 29 (1975) 530-539] | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Матроиды]] | [[Категория:Матроиды]] | ||
[[Категория:Объединение матроидов]] | [[Категория:Объединение матроидов]] |
Текущая версия на 19:30, 4 сентября 2022
Задача: |
Даны матроиды . Необходимо найти максимальное по мощности независимое множество в объединении . |
Определение: |
Объединение матроидов (англ. matroid union) | , где
Алгоритм
Эта задача сводится к пересечению матроидов, однако есть другой способ её решить. Пусть , для с , если . Определим граф замен: для каждого построим двудольный ориентированный граф так, что в левой доле находятся вершины из , а в правой — вершины из . Построим ориентированные ребра из в , при условии, что .
Объединим все
в один граф , который будет суперпозицией ребер из этих графов. Пусть для каждого — множество элементов с . Определим , и .Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. На каждом шаге мы выбираем элемент не из текущего множества в новом графе замен следующая теорема отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как . Тогда нужно найти такой элемент , что — снова независимо. Все наши кандидаты находятся в . Если мы найдем путь из в , то элемент , которым путь закончился, можно будет добавить в . То есть шаг жадного алгоритма заключается в создании нового и поиске такого пути.
(Псевдокод
граф замен if= for to построить
Время работы
Это подразумевает, что максимальное независимое множество в [1] разработал алгоритм, которым за можно найти максимальное независимое множество в , где максимальный размер множества в , размер подмножества и время, необходимое, чтобы определить принадлежит ли множество для каждого . Более детальное объяснение алгоритма (но не время работы) можно найти у C. Greene и T.L. Magnanti[2].
мы можем найти за полиномиальное время (жадно наращивать независимое множество в ). Cunningham
Теорема: |
Для любого имеем существует ориентированный путь из в по ребрам графа . |
Доказательство: |
Пусть существует путь из в и — самый короткий такой путь. Запишем его вершины как { }. , так что не умаляя общности можно сказать, что . Для каждого определим множество вершин { }, где пробегает от до . Положим, что , для всех положим . Ясно, что . Для того, чтобы показать независимость в объединении матроидов нужно показать, что для всех . Заметим, что так как мы выбирали путь таким, что он будет наименьшим, для каждого существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать . Так как паросочетание единственно, . Аналогично , значит . Следовательно независимо в объединении матроидов.
Пусть нет пути из в по ребрам . Тогда пусть существует множество , состоящее из вершин , из которого мы можем достичь : по допущению . Утверждается, что для всех (что означает, что — максимальное подмножество , независимое в ).Предположим, что это не так. ранга объединения матроидов имеем : , это возможно только если . Значит существует такой , для которого . Но (по предположению вначале доказательства), значит . Из этого следует, что содержит единственный цикл. Значит существует , такой что . Получается, что — ребро в и оно содержит этот , что противоречит тому как был выбран . Следовательно для всех нам известно : . У нас есть и . Из определния функции
и значит — противоречие. |
См. также
Примечания
Источники информации
Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13
Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, — Springer, 2004, — стр.732