Участник:Qtr/2 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 6 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Даны матроиды <tex>M_1 = \langle S_1, I_1 \rangle \dots M_n = \langle S_n, I_n \rangle</tex>. Необходимо найти максимальное по мощности независимое множество в [[Объединение_матроидов,_проверка_множества_на_независимость|объединении]] <tex>M_1\dots M_n</tex>.
+
Даны матроиды <tex>M_1 = \langle S_1, \mathcal{I}_1 \rangle \dots M_n = \langle S_n, \mathcal{I}_n \rangle</tex>. Необходимо найти максимальное по мощности независимое множество в [[Объединение_матроидов,_проверка_множества_на_независимость|объединении]] <tex>\bigcup\limits_{i=1}^{n}</tex> <tex>M_i</tex>.
 
}}
 
}}
  
 
== Алгоритм ==
 
== Алгоритм ==
  
Определим объединение матроидов как <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>
+
Пусть у нас есть множество <tex>I\in\mathcal{I}</tex>, где <tex> \mathcal{I} = \{ \bigcup\limits_{i=1}^{n} I_i \mid I_i \in \mathcal{I}_i\} </tex>, и разбиение <tex>I</tex> на <tex>\bigcup\limits_{i=1}^{n}I_i</tex>, такое, что <tex>I_i\in \mathcal{I}_i</tex>. То есть, <tex>I</tex> состоит из каких-то подмножеств семейства множеств <tex>\mathcal{I}_i</tex> для <tex>i</tex> от <tex>1</tex> до <tex>n</tex>. Рассмотрим элемент <tex>s\not \in I</tex>. Нужно определить, правда ли, что <tex>I+s\in \mathcal{I}</tex>. Если научиться это делать, то тогда можно решить задачу [[Теорема_Радо-Эдмондса_(жадный_алгоритм)|жадным алгоритмом]], добавляя в текущее множество по одному элементу <tex>s</tex> на каждом шаге.
  
Для каждого <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>M</tex> = <tex>\langle S,\mathcal{I} \rangle</tex> = <tex>\bigcup\limits_{i=1}^{n}</tex> <tex>M_i</tex>, где <tex>M_i</tex> = <tex>\langle S_i,\mathcal{I}_i \rangle</tex>.
  
Объединим все <tex>D_{M_i}(I_i)</tex> в один граф <tex>D</tex>, который будет суперпозицией ребер из этих графов.
+
Для <tex>i</tex> от <tex>1</tex> до <tex>n</tex> возьмем <tex>M_i</tex> и построим [[Основные_определения_теории_графов#.D0.94.D0.B2.D1.83.D0.B4.D0.BE.D0.BB.D1.8C.D0.BD.D1.8B.D0.B9_.D0.B3.D1.80.D0.B0.D1.84|двудольный ориентированный граф]] <tex>D_{M_i}(I_i)</tex>, где <tex>I_i \in \mathcal{I}_i</tex>. Вершины графа — элементы из <tex>S</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> D_{M_i}(I_i)</tex>.
|definition=
 
<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>i</tex> определим множество <tex>F_i</tex> как множество вершин <tex>S_i\setminus I_i</tex> таких, что множество <tex>I_i+x</tex> также независимое. Формально: <tex>F_i = \{ x \in S_i \setminus I_i \mid I_i + x \in \mathcal{I}_i \}</tex>.  
Здесь мы обозначим текущее множество как <tex>I</tex>.
 
Тогда нужно найти такой элемент <tex>s \in S \setminus I</tex>, что <tex>I + 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>F</tex> = <tex>\bigcup\limits_{k=1}^{n}</tex> <tex>F_i</tex>
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Для какого-нибудь <tex>s \in S \setminus I</tex> выполняется: <tex>I + s \in J \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
+
Для какого-нибудь <tex>s \in S \setminus I</tex> выполняется: <tex>I + s \in \mathcal{I} \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
 
|proof=
 
|proof=
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
  
Пусть существует путь из <tex>F</tex> в <tex>s</tex> и <tex>P</tex> — самый короткий такой путь. Запишем его вершины как <tex>\{s_0, s_1, \dots s_p\}</tex>. <tex>s_0 \in F</tex>, так что не умаляя общности можно сказать, что <tex>s_0 \in F_1</tex>. Для каждого <tex>j = 1...n</tex> определим множество вершин <tex>S_j =</tex> {<tex>s_i, s_{i+1}:(s_i, s_{i+1}) \in D_{M_j}(I_j)</tex>}, где <tex>i</tex> пробегает от <tex>0</tex> до <tex>p - 1</tex>.
+
:Пусть существует путь из <tex>F</tex> в <tex>s</tex> и <tex>P</tex> — самый короткий такой путь. Запишем его вершины как <tex>\{s_0, s_1, \dots s_p\}</tex>. Вершина <tex>s_0 \in F</tex>, так что не умаляя общности можно сказать, что <tex>s_0 \in F_1</tex>. Для каждого <tex>j = 1\dots n</tex> определим множество вершин <tex>S_j =</tex> <tex>\{s_i, s_{i+1}:(s_i, s_{i+1}) \in D_{M_j}(I_j)\}</tex>, где <tex>i</tex> пробегает от <tex>0</tex> до <tex>p - 1</tex>.
Положим, что <tex>I'_1 = (I_1 \oplus S_1) \cup \{s_0\}</tex>, для всех <tex>j > 1</tex> положим <tex>I'_j = (I_j \oplus S_j)</tex>. Ясно, что <tex>\cup _j I'_j = I + s</tex>. Для того, чтобы показать независимость <tex>I + s</tex> в объединении матроидов нужно показать, что <tex>I'_j \in J_j</tex> для всех <tex>j</tex>. Заметим, что так как мы выбирали путь <tex>P</tex> таким, что он будет наименьшим, для каждого <tex>j > 1</tex> существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать <tex>I'_j = I_j \oplus S_j</tex>. Так как паросочетание единственно, <tex>I'_j \in J_j</tex>. Аналогично <tex>s_0 \in F_1</tex>, значит <tex>I'_1 \in J_1</tex>. Следовательно <tex>I + s</tex> независимо в объединении матроидов.
+
:Положим <tex>I'_1 = (I_1 \oplus S_1) \cup \{s_0\}</tex>, для всех <tex>j > 1</tex> опеределим <tex>I'_j = (I_j \oplus S_j)</tex>. Ясно, что <tex>\cup _j I'_j = I + s</tex> (. Для того, чтобы показать независимость <tex>I + s</tex> в объединении матроидов нужно показать, что <tex>I'_j \in \mathcal{I}_j</tex> для всех <tex>j</tex>. Заметим, что так как мы выбирали путь <tex>P</tex> таким, что он будет наименьшим, для каждого <tex>j > 1</tex> существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать <tex>I'_j = I_j \oplus S_j</tex>. Так как паросочетание единственно, <tex>I'_j \in \mathcal{I}_j</tex>. Аналогично <tex>s_0 \in F_1</tex>, значит <tex>I'_1 \in \mathcal{I}_1</tex> (см. [[Лемма_о_единственном_паросочетании_в_графе_замен#.D0.9B.D0.B5.D0.BC.D0.BC.D0.B0_.D0.BE_.D0.B5.D0.B4.D0.B8.D0.BD.D1.81.D1.82.D0.B2.D0.B5.D0.BD.D0.BD.D0.BE.D0.BC_.D0.BF.D0.B0.D1.80.D0.BE.D1.81.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D0.B8_.D0.B2_.D0.B3.D1.80.D0.B0.D1.84.D0.B5_.D0.B7.D0.B0.D0.BC.D0.B5.D0.BD|лемму]]). Следовательно, <tex>I + s</tex> независимо в объединении матроидов.
  
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
  
Пусть нет пути из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>. Тогда пусть существует множество <tex>T</tex>, состоящее из вершин <tex>D</tex>, из которого мы можем достичь <tex>s</tex> : <tex>T = \{x, \exists x \leadsto s\}</tex> по допущению <tex>F\cap T = \varnothing</tex>. Утверждается, что для всех <tex>i : |I_i \cap T| = r_i(T)</tex>(что означает, что <tex>I_i \cap T</tex> — максимальное подмножество <tex>T</tex>, независимое в <tex>M_i</tex>).  
+
:Пусть нет пути из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>. Тогда пусть существует множество <tex>T</tex>, состоящее из вершин <tex>D</tex>, из которого мы можем достичь <tex>s</tex> : <tex>T = \{x\mid \exists x \leadsto s\}</tex>, по допущению <tex>F\cap T = \varnothing</tex>. Утверждается, что для всех <tex>i : |I_i \cap T| = r_i(T)</tex> (из чего [[Ранговая_функция,_полумодулярность|следует]], что <tex>I_i \cap T</tex> — максимальное подмножество <tex>T</tex>, независимое в <tex>M_i</tex>).  
  
Предположим, что это не так. <tex>|I_i \cap T| = r_i(I_i\cap T) \le r_i(T)</tex>, это возможно только если <tex>|I_i \cap T| < r_i(T)</tex>. Значит существует такой <tex>x \in T \cap (S \setminus I_i)</tex>, для которого <tex>(I_i \cap T) + x \in J_i</tex>. Но <tex>x \notin F</tex> (по предположению вначале доказательства), значит <tex>I_i + x \notin J_i</tex>. Из этого следует, что <tex>I_i + x</tex> содержит единственный цикл. Значит существует <tex>y \in I_i - T</tex>, такой что <tex>I_i + x - y \in J_i</tex>. Получается, что <tex>(y, x)</tex> — ребро в <tex>D_{M_i}(I_i)</tex> и оно содержит этот <tex>y \in T</tex>, что противоречит тому как был выбран <tex>y \in I_i \setminus T</tex>. Следовательно для всех <tex>i</tex> нам известно : <tex>|I_i \cap T| = r_i(T)</tex>.
+
:Предположим, что это не так. Так как <tex>|I_i \cap T| = r_i(I_i\cap T) \leqslant r_i(T)</tex>, остается возможным только случай <tex>|I_i \cap T| < r_i(T)</tex> (мы предположили, что утверждение в предыдущем абзаце неверно). Значит существует такой <tex>x \in T \cap (S \setminus I_i)</tex>, для которого <tex>(I_i \cap T) + x \in \mathcal{I}_i</tex>. Но <tex>x \notin F</tex> (по предположению в начале доказательства), значит <tex>I_i + x \notin  
У нас есть <tex>s \in T</tex> и <tex>(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s</tex>. Из определния функции ранга объединения матроидов имеем :  
+
\mathcal{I}_i</tex>. Из этого следует, что <tex>I_i + x</tex> содержит единственный цикл. Значит существует <tex>y \in I_i - T</tex>, такой, что <tex>I_i + x - y \in \mathcal{I}_i</tex>. Получается, что <tex>(y, x)</tex> — ребро в <tex>D_{M_i}(I_i)</tex> и оно содержит этот <tex>y \in T</tex>, что противоречит тому как был выбран <tex>y \in I_i \setminus T</tex>. Следовательно для всех <tex>i</tex> нам известно : <tex>|I_i \cap T| = r_i(T)</tex>.
 +
:У нас есть <tex>s \in T</tex> и <tex>(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s</tex>. Из определения функции ранга объединения матроидов имеем :  
  
<tex>r_M(I + s) \le (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))</tex>
+
:<tex>r_M(I + s) \leqslant (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))</tex>
  
<tex>r_M(I + s) \le |(I + s)\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I| < |I + s|</tex>  
+
:<tex>r_M(I + s) \leqslant |(I + s)\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I| < |I + s|</tex>  
и значит <tex>(I + s) \notin J</tex> — противоречие.
+
:и значит <tex>(I + s) \notin  
 +
\mathcal{I}</tex> — противоречие.
 
}}
 
}}
 +
 +
Итак, теперь мы можем описать сам алгоритм. Изначально инициализируем <tex>I</tex> как семейство пустых множеств. На каждом шаге будем строить граф  <tex>D</tex> из текущего <tex>I</tex> и <tex>S\setminus I</tex> и добавлять в <tex>I</tex> кандидата-вершину <tex>s</tex>, удовлетворяющую условию теоремы. При добавлении вершины нужно не забыть поменять местами вершины на пути <tex>F \leadsto s</tex>, так как ребра из <tex>I_i</tex> должны вести в <tex>S\setminus I_i</tex> (т.е. должен сохраняться инвариант). Когда вершины-кандидаты закончатся, по доказанной выше теореме получившееся множество <tex>I</tex> станет максимальным.
  
 
==Псевдокод==
 
==Псевдокод==
*<tex>S</tex> — принимаемое множество носитилей матроидов
+
В реализации алгоритма каждый элемент представлен целым числом.
*<tex>J</tex> — принимаемое множество баз матроидов
+
 
*<tex>I</tex> — возвращаемая база в объединении матроидов. <tex>I_1, I_2 \dots I_n</tex> содержат элементы, содержащиеся в полученной базе.
+
*<tex>s</tex> — принимаемое множество носитилей матроидов
 +
*<tex>\mathtt{base}</tex> — принимаемое множество баз матроидов
 +
*<tex>\mathtt{res}</tex> — возвращаемая база в объединении матроидов. <tex>res_1, res_2 \dots res_n</tex> содержат элементы, содержащиеся в полученной базе.
  
  '''int'''[][] union('''int''' <tex>S[n]</tex>, '''int''' <tex>J[n]</tex>):
+
  '''int[][]''' unionBase('''int[n]''' <tex>s</tex>, '''int[n]''' <tex>\mathtt{base}</tex>):
   '''int'''[] <tex>I[n]</tex> <font color="darkgreen">//На каждом шаге алгоритма заполняем очередным элементом </font>
+
   '''int[n][]''' <tex>\mathtt{res}</tex> <font color="darkgreen">// На каждом шаге алгоритма заполняем очередным элементом </font>
   '''bool''' <tex>reached</tex> = '''false'''
+
   '''bool''' <tex>\mathtt{reached}</tex> = ''false'' <font color="darkgreen">// Индикатор окончания работы цикла. Если true, то не нашли подходящую вершину</font>
   '''while''' '''not''' reached:
+
   '''while''' <tex>!\mathtt{reached}</tex>
     <tex>reached</tex> = '''true'''
+
     <tex>\mathtt{reached}</tex> = ''true''
     '''int''' <tex>F[n]</tex>
+
     '''int''' <tex>f[n]</tex> <font color="darkgreen">// Соответствует <tex>F</tex> </font>
     '''Graph''' <tex>D[n]</tex>
+
     '''Graph''' <tex>d[n]</tex>
 
     '''for''' <tex>i</tex> = 1 '''to''' <tex>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>d[i]</tex> = buildBipartiteGraph<tex>(\mathtt{res[i]} ,s[i] \setminus \mathtt{res}[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>
+
       <tex>f[i]</tex> = <tex> \{ x \in s[i] \setminus \mathtt{res[i]} : \mathtt{res}[i] + x \in base[i] \}</tex>  
     '''for''' <tex>s \in S\setminus I</tex>:
+
     '''for''' <tex>\mathtt{elem} \in s\setminus \mathtt{base}</tex>
       '''int[]''' <tex>p</tex> = find_shortest_path(<tex>F</tex>, <tex>s</tex>)
+
       '''List<int>''' <tex>p</tex> = findShortestPath(<tex>f</tex>, <tex>\mathtt{elem}</tex>)
       '''if''' find_shortest_path(<tex>F</tex>, <tex>s</tex>) <tex>\neq \varnothing </tex>:
+
       '''if''' <tex>p\neq \varnothing </tex>
         <tex>reached</tex> = '''false'''
+
         <tex>\mathtt{reached}</tex> = ''false'' <font color="darkgreen">// Нашли очередную вершину, цикл можно продолжить </font>
         '''int''' <tex>pos</tex> = get_f(<tex>p[1]</tex>) <font color="darkgreen">// Находим <tex>F_i</tex>, которому принадлежит стартовая вершина в пути</font>
+
         '''int''' <tex>\mathtt{pos}</tex> = getF(<tex>p[1]</tex>) <font color="darkgreen">// Находим <tex>f_i</tex>, которому принадлежит стартовая вершина в пути</font>
         '''int''' <tex>v[n]</tex>
+
         '''int''' <tex>v[n]</tex> <font color="darkgreen">// i-й элемент <tex>v</tex> хранит множество вершин, соответствующее i-му входному матроиду </font>
         '''for''' <tex> j</tex> = 1 '''to''' <tex>p.len - 1</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>  
+
           '''int''' <tex>\mathtt{vertex}</tex> = getDbyEdge<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[\mathtt{vertex}].add(j)</tex> <font color="darkgreen">// Добавляем в соответствующее вершинам множество концы ребра</font>
           <tex>v[vertex\_num].add(j + 1)</tex>
+
           <tex>v[\mathtt{vertex}].add(j + 1)</tex>
         '''for''' <tex>j</tex> = 1 '''to''' <tex>n</tex>:
+
         '''for''' <tex>j</tex> = 1 '''to''' <tex>n</tex>
           <tex> I[j]</tex> = <tex> I[j] \oplus v[j]</tex>
+
           <tex> \mathtt{res}[j]</tex> = <tex> \mathtt{res}[j] \oplus v[j]</tex> <font color="darkgreen"> // Удаляем и добавляем ребра на пути к конечной вершине </font>  
         <tex>I[pos]</tex> = <tex>I[pos] \cup p[1] </tex>
+
         <tex>\mathtt{res}[\mathtt{pos}]</tex> = <tex>res[\mathtt{pos}] \cup p[1] </tex>
 
         '''break'''
 
         '''break'''
   '''return''' <tex>I</tex>
+
   '''return''' <tex>\mathtt{res}</tex>
  
 
== См. также ==
 
== См. также ==
Строка 81: Строка 81:
 
*[[Объединение_матроидов,_доказательство_того,_что_объединение_является_матроидом| Объединение матроидов, доказательство того, что объединение является матроидом]]
 
*[[Объединение_матроидов,_доказательство_того,_что_объединение_является_матроидом| Объединение матроидов, доказательство того, что объединение является матроидом]]
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Пересечение матроидов, определение, примеры]]
 +
 +
== Асимптотика ==
 +
На каждом шаге алгоритма происходит построение графа D. Для того, чтобы его построить, нам нужно для <tex>i=1\dots n</tex> для каждого <tex>v</tex> из <tex>S</tex> и <tex>u</tex> из <tex>S\setminus I_i</tex>, где <tex>S</tex> — объединение матроидов, проверить условие <tex>(I_i \setminus u) \cup v \in \mathcal{I}_i</tex>. Построение графа занимает <tex>O(\sum\limits_{i=1}^{n}\vert (S_i\setminus I_i)\vert \vert I_i\vert </tex>) времени на каждой итерации. Нахождение кратчайшего пути  для всех вершин занимает <tex>O(\vert E\vert )</tex> единиц времени, где <tex>E</tex> — множество ребер графа <tex>D</tex>, если использовать [[обход_в_ширину| поиск в ширину]], что в худшем случае будет равно <tex>O(\vert S \vert ^2)</tex>. Обновление <tex>res</tex> занимает <tex>O(n|I_{max}|)</tex> времени, что равно <tex>O(\vert S \vert)</tex>. В худшем случае требуется <tex>|S|</tex> итераций, и общая асимптотика будет <tex>O(|S|^3)</tex>.
  
 
== Источники информации ==
 
== Источники информации ==
  
[http://math.mit.edu/~goemans/18438F09/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13]
+
*[http://math.mit.edu/~goemans/18438F09/lec13.pdf Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]
 
[[Категория:Объединение матроидов]]
 
[[Категория:Объединение матроидов]]

Текущая версия на 11:12, 9 июня 2016

Задача:
Даны матроиды [math]M_1 = \langle S_1, \mathcal{I}_1 \rangle \dots M_n = \langle S_n, \mathcal{I}_n \rangle[/math]. Необходимо найти максимальное по мощности независимое множество в объединении [math]\bigcup\limits_{i=1}^{n}[/math] [math]M_i[/math].


Алгоритм

Пусть у нас есть множество [math]I\in\mathcal{I}[/math], где [math] \mathcal{I} = \{ \bigcup\limits_{i=1}^{n} I_i \mid I_i \in \mathcal{I}_i\} [/math], и разбиение [math]I[/math] на [math]\bigcup\limits_{i=1}^{n}I_i[/math], такое, что [math]I_i\in \mathcal{I}_i[/math]. То есть, [math]I[/math] состоит из каких-то подмножеств семейства множеств [math]\mathcal{I}_i[/math] для [math]i[/math] от [math]1[/math] до [math]n[/math]. Рассмотрим элемент [math]s\not \in I[/math]. Нужно определить, правда ли, что [math]I+s\in \mathcal{I}[/math]. Если научиться это делать, то тогда можно решить задачу жадным алгоритмом, добавляя в текущее множество по одному элементу [math]s[/math] на каждом шаге.

Определим объединение матроидов как [math]M[/math] = [math]\langle S,\mathcal{I} \rangle[/math] = [math]\bigcup\limits_{i=1}^{n}[/math] [math]M_i[/math], где [math]M_i[/math] = [math]\langle S_i,\mathcal{I}_i \rangle[/math].

Для [math]i[/math] от [math]1[/math] до [math]n[/math] возьмем [math]M_i[/math] и построим двудольный ориентированный граф [math]D_{M_i}(I_i)[/math], где [math]I_i \in \mathcal{I}_i[/math]. Вершины графа — элементы из [math]S[/math], в левой доле находятся вершины из [math]I_i[/math], а в правой — элементы из [math]S \setminus I_i[/math]. Проведем ориентированные ребра из [math]y \in I_i[/math] в [math]x \in S \setminus I_i[/math], при условии, что [math](I_i \setminus y) \cup x \in \mathcal{I}_i[/math].

Объединим все [math]D_{M_i}(I_i)[/math] в один граф [math]D[/math], который будет наложением ребер из этих графов, то есть, будет содержать все рёбра всех графов [math] D_{M_i}(I_i)[/math].

Для каждого [math]i[/math] определим множество [math]F_i[/math] как множество вершин [math]S_i\setminus I_i[/math] таких, что множество [math]I_i+x[/math] также независимое. Формально: [math]F_i = \{ x \in S_i \setminus I_i \mid I_i + x \in \mathcal{I}_i \}[/math].

Определим [math]F[/math] = [math]\bigcup\limits_{k=1}^{n}[/math] [math]F_i[/math]

Теорема:
Для какого-нибудь [math]s \in S \setminus I[/math] выполняется: [math]I + s \in \mathcal{I} \Leftrightarrow [/math] существует ориентированный путь из [math]F[/math] в [math]s[/math] по ребрам [math]D[/math].
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow[/math]

Пусть существует путь из [math]F[/math] в [math]s[/math] и [math]P[/math] — самый короткий такой путь. Запишем его вершины как [math]\{s_0, s_1, \dots s_p\}[/math]. Вершина [math]s_0 \in F[/math], так что не умаляя общности можно сказать, что [math]s_0 \in F_1[/math]. Для каждого [math]j = 1\dots n[/math] определим множество вершин [math]S_j =[/math] [math]\{s_i, s_{i+1}:(s_i, s_{i+1}) \in D_{M_j}(I_j)\}[/math], где [math]i[/math] пробегает от [math]0[/math] до [math]p - 1[/math].
Положим [math]I'_1 = (I_1 \oplus S_1) \cup \{s_0\}[/math], для всех [math]j \gt 1[/math] опеределим [math]I'_j = (I_j \oplus S_j)[/math]. Ясно, что [math]\cup _j I'_j = I + s[/math] (. Для того, чтобы показать независимость [math]I + s[/math] в объединении матроидов нужно показать, что [math]I'_j \in \mathcal{I}_j[/math] для всех [math]j[/math]. Заметим, что так как мы выбирали путь [math]P[/math] таким, что он будет наименьшим, для каждого [math]j \gt 1[/math] существует единственное паросочетание между элементами, которые мы добавляли и удаляли, чтобы сконструировать [math]I'_j = I_j \oplus S_j[/math]. Так как паросочетание единственно, [math]I'_j \in \mathcal{I}_j[/math]. Аналогично [math]s_0 \in F_1[/math], значит [math]I'_1 \in \mathcal{I}_1[/math] (см. лемму). Следовательно, [math]I + s[/math] независимо в объединении матроидов.

[math]\Rightarrow[/math]

Пусть нет пути из [math]F[/math] в [math]s[/math] по ребрам [math]D[/math]. Тогда пусть существует множество [math]T[/math], состоящее из вершин [math]D[/math], из которого мы можем достичь [math]s[/math] : [math]T = \{x\mid \exists x \leadsto s\}[/math], по допущению [math]F\cap T = \varnothing[/math]. Утверждается, что для всех [math]i : |I_i \cap T| = r_i(T)[/math] (из чего следует, что [math]I_i \cap T[/math] — максимальное подмножество [math]T[/math], независимое в [math]M_i[/math]).
Предположим, что это не так. Так как [math]|I_i \cap T| = r_i(I_i\cap T) \leqslant r_i(T)[/math], остается возможным только случай [math]|I_i \cap T| \lt r_i(T)[/math] (мы предположили, что утверждение в предыдущем абзаце неверно). Значит существует такой [math]x \in T \cap (S \setminus I_i)[/math], для которого [math](I_i \cap T) + x \in \mathcal{I}_i[/math]. Но [math]x \notin F[/math] (по предположению в начале доказательства), значит [math]I_i + x \notin \mathcal{I}_i[/math]. Из этого следует, что [math]I_i + x[/math] содержит единственный цикл. Значит существует [math]y \in I_i - T[/math], такой, что [math]I_i + x - y \in \mathcal{I}_i[/math]. Получается, что [math](y, x)[/math] — ребро в [math]D_{M_i}(I_i)[/math] и оно содержит этот [math]y \in T[/math], что противоречит тому как был выбран [math]y \in I_i \setminus T[/math]. Следовательно для всех [math]i[/math] нам известно : [math]|I_i \cap T| = r_i(T)[/math].
У нас есть [math]s \in T[/math] и [math](I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s[/math]. Из определения функции ранга объединения матроидов имеем :
[math]r_M(I + s) \leqslant (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))[/math]
[math]r_M(I + s) \leqslant |(I + s)\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I\setminus T| + \sum\limits_{k=1}^{n} |I_i \cap T| = |I| \lt |I + s|[/math]
и значит [math](I + s) \notin \mathcal{I}[/math] — противоречие.
[math]\triangleleft[/math]

Итак, теперь мы можем описать сам алгоритм. Изначально инициализируем [math]I[/math] как семейство пустых множеств. На каждом шаге будем строить граф [math]D[/math] из текущего [math]I[/math] и [math]S\setminus I[/math] и добавлять в [math]I[/math] кандидата-вершину [math]s[/math], удовлетворяющую условию теоремы. При добавлении вершины нужно не забыть поменять местами вершины на пути [math]F \leadsto s[/math], так как ребра из [math]I_i[/math] должны вести в [math]S\setminus I_i[/math] (т.е. должен сохраняться инвариант). Когда вершины-кандидаты закончатся, по доказанной выше теореме получившееся множество [math]I[/math] станет максимальным.

Псевдокод

В реализации алгоритма каждый элемент представлен целым числом.

  • [math]s[/math] — принимаемое множество носитилей матроидов
  • [math]\mathtt{base}[/math] — принимаемое множество баз матроидов
  • [math]\mathtt{res}[/math] — возвращаемая база в объединении матроидов. [math]res_1, res_2 \dots res_n[/math] содержат элементы, содержащиеся в полученной базе.
int[][] unionBase(int[n] [math]s[/math], int[n] [math]\mathtt{base}[/math]):
  int[n][] [math]\mathtt{res}[/math] // На каждом шаге алгоритма заполняем очередным элементом 
  bool [math]\mathtt{reached}[/math] = false // Индикатор окончания работы цикла. Если true, то не нашли подходящую вершину
  while [math]!\mathtt{reached}[/math]
    [math]\mathtt{reached}[/math] = true
    int [math]f[n][/math] // Соответствует [math]F[/math] 
    Graph [math]d[n][/math]
    for [math]i[/math] = 1 to [math]n[/math]
      [math]d[i][/math] = buildBipartiteGraph[math](\mathtt{res[i]} ,s[i] \setminus \mathtt{res}[i])[/math] // Строим двудольный граф d[i] 
      [math]f[i][/math] = [math] \{ x \in s[i] \setminus \mathtt{res[i]} : \mathtt{res}[i] + x \in base[i] \}[/math] 
    for [math]\mathtt{elem} \in s\setminus \mathtt{base}[/math]
      List<int> [math]p[/math] = findShortestPath([math]f[/math], [math]\mathtt{elem}[/math])
      if [math]p\neq \varnothing [/math]
        [math]\mathtt{reached}[/math] = false // Нашли очередную вершину, цикл можно продолжить 
        int [math]\mathtt{pos}[/math] = getF([math]p[1][/math]) // Находим [math]f_i[/math], которому принадлежит стартовая вершина в пути
        int [math]v[n][/math] // i-й элемент [math]v[/math] хранит множество вершин, соответствующее i-му входному матроиду 
        for [math] j[/math] = 1 to [math]p.len - 1[/math]
          int [math]\mathtt{vertex}[/math] = getDbyEdge[math](p[j],p[j+1])[/math] // Находим номер графа, соответствующего ребру [math](p[j],p[j+1])[/math] 
          [math]v[\mathtt{vertex}].add(j)[/math] // Добавляем в соответствующее вершинам множество концы ребра
          [math]v[\mathtt{vertex}].add(j + 1)[/math]
        for [math]j[/math] = 1 to [math]n[/math]
          [math] \mathtt{res}[j][/math] = [math] \mathtt{res}[j] \oplus v[j][/math]  // Удаляем и добавляем ребра на пути к конечной вершине  
        [math]\mathtt{res}[\mathtt{pos}][/math] = [math]res[\mathtt{pos}] \cup p[1] [/math]
        break
  return [math]\mathtt{res}[/math]

См. также

Асимптотика

На каждом шаге алгоритма происходит построение графа D. Для того, чтобы его построить, нам нужно для [math]i=1\dots n[/math] для каждого [math]v[/math] из [math]S[/math] и [math]u[/math] из [math]S\setminus I_i[/math], где [math]S[/math] — объединение матроидов, проверить условие [math](I_i \setminus u) \cup v \in \mathcal{I}_i[/math]. Построение графа занимает [math]O(\sum\limits_{i=1}^{n}\vert (S_i\setminus I_i)\vert \vert I_i\vert [/math]) времени на каждой итерации. Нахождение кратчайшего пути для всех вершин занимает [math]O(\vert E\vert )[/math] единиц времени, где [math]E[/math] — множество ребер графа [math]D[/math], если использовать поиск в ширину, что в худшем случае будет равно [math]O(\vert S \vert ^2)[/math]. Обновление [math]res[/math] занимает [math]O(n|I_{max}|)[/math] времени, что равно [math]O(\vert S \vert)[/math]. В худшем случае требуется [math]|S|[/math] итераций, и общая асимптотика будет [math]O(|S|^3)[/math].

Источники информации