1632
правки
Изменения
м
=== '''Псевдокод ==='''
rollbackEdits.php mass rollback
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. На каждом шаге мы выбираем элемент не из текущего множества в новом графе замен <tex>D_{M_i}(I_i)</tex> ([[Алгоритм построения базы в объединении матроидов#th_1|следующая теорема]] отвечает на вопрос, как представить это в графе). Здесь мы обозначим текущее множество как <tex>I</tex>.
Тогда нужно найти такой элемент <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>D</tex> и поиске такого пути.
<tex>J</tex> = <tex>\emptyset</tex>
'''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>n - 1</tex>
'''if''' <tex>I_i + s \in \mathcal{I}_i</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>.
|id=th_1
|statement=
Для любого <tex>s \in S \setminus I</tex> имеем <tex>I \cup s \in J \mathcal{I} \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам графа <tex>D</tex>.
|proof=
<tex>\Leftarrow</tex>
* [[Пересечение матроидов, определение, примеры]]
* [[Алгоритм построения базы в пересечении матроидов]]
== Примечания ==
<references/>
== Источники информации ==
[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]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Объединение матроидов]]
