200
правок
Изменения
→Алгоритм
То есть шаг жадного алгоритма заключается в создании нового <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>.
* [[Пересечение матроидов, определение, примеры]]
* [[Алгоритм построения базы в пересечении матроидов]]
== Примечания ==
<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]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Объединение матроидов]]
