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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 26: Строка 26:
 
{{Теорема
 
{{Теорема
 
|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 J  \Leftrightarrow </tex> существует ориентированный путь из <tex>F</tex> в <tex>s</tex> по ребрам <tex>D</tex>.
 
|proof=
 
|proof=
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
Строка 53: Строка 53:
 
  '''int'''[][] union('''int''' <tex>S[n]</tex>, '''int''' <tex>J[n]</tex>):
 
  '''int'''[][] union('''int''' <tex>S[n]</tex>, '''int''' <tex>J[n]</tex>):
 
   '''int'''[] <tex>I[n]</tex> <font color="darkgreen">//На каждом шаге алгоритма заполняем очередным элементом </font>
 
   '''int'''[] <tex>I[n]</tex> <font color="darkgreen">//На каждом шаге алгоритма заполняем очередным элементом </font>
   '''bool''' reached = '''false'''
+
   '''bool''' <tex>reached</tex> = '''false'''
 
   '''while''' '''not''' reached:
 
   '''while''' '''not''' reached:
     reached = '''true'''
+
     <tex>reached</tex> = '''true'''
 
     '''int''' <tex>F[n]</tex>
 
     '''int''' <tex>F[n]</tex>
 
     '''Graph''' <tex>D[n]</tex>
 
     '''Graph''' <tex>D[n]</tex>
Строка 64: Строка 64:
 
       '''int[]''' <tex>p</tex> = find_shortest_path(<tex>F</tex>, <tex>s</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>:
 
       '''if''' find_shortest_path(<tex>F</tex>, <tex>s</tex>) <tex>\neq \varnothing </tex>:
         reached = '''false'''
+
         <tex>reached</tex> = '''false'''
 
         '''int''' <tex>pos</tex> = get_f(<tex>p[1]</tex>) <font color="darkgreen">// Находим <tex>F_i</tex>, которому принадлежит стартовая вершина в пути</font>
 
         '''int''' <tex>pos</tex> = get_f(<tex>p[1]</tex>) <font color="darkgreen">// Находим <tex>F_i</tex>, которому принадлежит стартовая вершина в пути</font>
 
         '''int''' <tex>v[n]</tex>
 
         '''int''' <tex>v[n]</tex>
         '''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>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)</tex>
Строка 76: Строка 76:
 
         '''break'''
 
         '''break'''
 
   '''return''' <tex>I</tex>
 
   '''return''' <tex>I</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]
+
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Матроиды]]
 +
[[Категория:Объединение матроидов]]

Версия 20:29, 8 июня 2016

Задача:
Даны матроиды [math]M_1 = \langle S_1, I_1 \rangle \dots M_n = \langle S_n, I_n \rangle[/math]. Необходимо найти максимальное по мощности независимое множество в объединении [math]M_1\dots M_n[/math].


Алгоритм

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

Для каждого [math]M_i[/math] построим двудольный ориентированный граф [math]D_{M_i}(I_i)[/math], где [math]I_i \in J_i[/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 J_i[/math].

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


Определение:
[math]F_i = \{ x \in S_i \setminus I_i : I_i + x \in J_i \}[/math]. [math]F[/math] = [math]\bigcup\limits_{k=1}^{n}[/math] [math]F_i[/math]


Нам известно, что объединение матроидов — матроид. При поиске базы матроида используется жадный алгоритм. В нем трудность может представлять шаг поиска нового элемента не из текущего множества, который оставит текущее множество независимым. Здесь мы обозначим текущее множество как [math]I[/math]. Тогда нужно найти такой элемент [math]s \in S \setminus I[/math], что [math]I + s[/math] — снова независимо. Все наши кандидаты находятся в [math]S \setminus I[/math]. Если мы найдем путь из [math]F[/math] в [math]S \setminus I[/math], то элемент [math]s[/math], которым путь закончился, можно будет добавить в [math]I[/math]. То есть шаг жадного алгоритма заключается в создании нового [math]D[/math] и поиске такого пути.


Теорема:
Для какого-нибудь [math]s \in S \setminus I[/math] выполняется: [math]I + s \in J \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...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 J_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 J_j[/math]. Аналогично [math]s_0 \in F_1[/math], значит [math]I'_1 \in J_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, \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) \le 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 J_i[/math]. Но [math]x \notin F[/math] (по предположению вначале доказательства), значит [math]I_i + x \notin J_i[/math]. Из этого следует, что [math]I_i + x[/math] содержит единственный цикл. Значит существует [math]y \in I_i - T[/math], такой что [math]I_i + x - y \in J_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) \le (|(I + s)\setminus T| + \sum\limits_{k=1}^{n}r_i(T))[/math]

[math]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| \lt |I + s|[/math]

и значит [math](I + s) \notin J[/math] — противоречие.
[math]\triangleleft[/math]

Псевдокод

  • [math]S[/math] — принимаемое множество носитилей матроидов
  • [math]J[/math] — принимаемое множество баз матроидов
  • [math]I[/math] — возвращаемая база в объединении матроидов. [math]I_1, I_2 \dots I_n[/math] содержат элементы, содержащиеся в полученной базе.
int[][] union(int [math]S[n][/math], int [math]J[n][/math]):
  int[] [math]I[n][/math] //На каждом шаге алгоритма заполняем очередным элементом 
  bool [math]reached[/math] = false
  while not reached:
    [math]reached[/math] = true
    int [math]F[n][/math]
    Graph [math]D[n][/math]
    for [math]i[/math] = 1 to [math]n[/math]
      [math]D[i][/math] = build_bipartite_graph[math](I[i] ,S[i] \setminus I[i])[/math] // Строим двудольный граф D[i] 
      [math]F[i][/math] =[math] \{ x \in S[i] \setminus I[i] : I[i] + x \in J[i] \}[/math]
    for [math]s \in S\setminus I[/math]:
      int[] [math]p[/math] = find_shortest_path([math]F[/math], [math]s[/math])
      if find_shortest_path([math]F[/math], [math]s[/math]) [math]\neq \varnothing [/math]:
        [math]reached[/math] = false
        int [math]pos[/math] = get_f([math]p[1][/math]) // Находим [math]F_i[/math], которому принадлежит стартовая вершина в пути
        int [math]v[n][/math]
        for [math] j[/math] = 1 to [math]p.len - 1[/math]:
          int [math]vertex\_num[/math] = get_D_by_edge[math](p[j],p[j+1])[/math] // Находим номер графа, соответствующего ребру [math](p[j],p[j+1])[/math] 
          [math]v[vertex\_num].add(j)[/math]
          [math]v[vertex\_num].add(j + 1)[/math]
        for [math]j[/math] = 1 to [math]n[/math]:
          [math] I[j][/math] = [math] I[j] \oplus v[j][/math]
        [math]I[pos][/math] = [math]I[pos] \cup p[1] [/math]
        break
  return [math]I[/math]

См. также

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

Michel X. Goemans. Advanced Combinatorial Optimization. Lecture 13