Изменения
Нет описания правки
{{ОпределениеЗадача
|definition=
}}
== Алгоритм == Определим объединение матроидов как <tex>M</tex> = <tex>\langle S,J \rangle</tex> = <tex>\bigcup\limits_{i=1}^{Определениеn}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S_i,J_i \rangle</tex>|definition=
Для каждого <tex>M_i</tex> построим двудольный ориентированный граф <tex>D_{M_i}(I_i)</tex>, где <tex>I_i \in J_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 J_i</tex>.
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов.
<tex>F_i = \{ x \in S_i \setminus I_i : I_i + x \in J_i \}</tex>. <tex>F</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>F_i</tex>
}}
Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым.
То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути.
{{Теорема
|statement=
Для любого <tex>s \in S \setminus I</tex> имеем выполняется: <tex>I + s \in J \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
|proof=
<tex>\Leftarrow</tex>
}}
== Источник Псевдокод==*<tex>S</tex> — принимаемое множество носитилей матроидов*<tex>J</tex> — принимаемое множество баз матроидов*<tex>I</tex> — возвращаемая база в объединении матроидов. <tex>I_1, I_2 \dots I_n</tex> содержат элементы, содержащиеся в полученной базе. '''int'''[][] union('''int''' <tex>S[n]</tex>, '''int''' <tex>J[n]</tex>): '''int'''[] <tex>I[n]</tex> <font color="darkgreen">//На каждом шаге алгоритма заполняем очередным элементом </font> '''bool''' reached = '''false''' '''while''' '''not''' reached: reached = '''true''' '''int''' <tex>F[n]</tex> '''Graph''' <tex>D[n]</tex> '''for''' <tex>i</tex> = 1 '''to''' <tex>n</tex> <tex>D[i]</tex> = build_bipartite_graph<tex>(I[i] ,S[i] \setminus I[i])</tex> <font color="darkgreen">// Строим двудольный граф D[i] </font> <tex>F[i]</tex> =<tex> \{ x \in S[i] \setminus I[i] : I[i] + x \in J[i] \}</tex> '''for''' <tex>s \in S\setminus I</tex>: '''int[]''' <tex>p</tex> = find_shortest_path(<tex>F</tex>, <tex>s</tex>) '''if''' find_shortest_path(<tex>F</tex>, <tex>s</tex>) <tex>\neq \varnothing </tex>: reached = '''false''' '''int''' <tex>pos</tex> = get_f(<tex>p[1]</tex>) <font color="darkgreen">// Находим <tex>F_i</tex>, которому принадлежит стартовая вершина в пути</font> '''int''' <tex>v[n]</tex> '''for''' <tex> j</tex> = 1 '''to''' <tex>P.len - 1</tex>: '''int''' <tex>vertex\_num</tex> = get_D_by_edge<tex>(p[j],p[j+1])</tex> <font color="darkgreen">// Находим номер графа, соответствующего ребру <tex>(p[j],p[j+1])</tex></font> <tex>v[vertex\_num].add(j)</tex> <tex>v[vertex\_num].add(j + 1)</tex> '''for''' <tex>j</tex> = 1 '''to''' <tex>n</tex>: <tex> I[j]</tex> = <tex> I[j] \oplus v[j]</tex> <tex>I[pos]</tex> = <tex>I[pos] \cup p[1] </tex> '''break''' '''return''' <tex>I</tex> == Источники информации ==
[http://math.mit.edu/~goemans/1843818438F09/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13]
