Жадный алгоритм поиска базы минимального веса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
  <tex>sort(X)</tex>    // сортируем элементы по возрастанию веса
 
  <tex>sort(X)</tex>    // сортируем элементы по возрастанию веса
 
  <tex>B \leftarrow \emptyset</tex>
 
  <tex>B \leftarrow \emptyset</tex>
  '''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>\mid X \mid</tex> '''do'''
+
  '''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>\mid X \mid-1</tex> '''do'''
   '''if''' <tex>B \cup ArgOf(X[i]) \in I</tex>
+
   '''if''' <tex>B \cup X[i] \in I</tex>
     <tex>B \leftarrow B \cup ArgOf(X[i])</tex>
+
     <tex>B \leftarrow B \cup X[i]</tex>
Рассмотрим шаг алгоритма, когда мы пытаемся добавить элемент <tex>ArgOf(X[i])</tex>. Заметим, что если его можно добавить с сохранением независимости множества <tex>B</tex>, то это элемент минимального веса не из <tex>B</tex>, который можно добавить (при условии сохранения независимости <tex>B</tex> при добавлении). В самом деле, пусть <tex>ArgOf(X[j])</tex> — элемент минимального веса, который можно добавить к <tex>B</tex> с сохранением его независимости, тогда <tex>j<i</tex>. Но тогда он уже был бы добавлен на <tex>j</tex>-ом шаге алгоритма.
+
Рассмотрим шаг алгоритма, когда мы пытаемся добавить элемент <tex>X[i]</tex>. Заметим, что если его можно добавить с сохранением независимости множества <tex>B</tex>, то это элемент минимального веса не из <tex>B</tex>, который можно добавить (при условии сохранения независимости <tex>B</tex> при добавлении). В самом деле, пусть <tex>X[j]</tex> — элемент минимального веса, который можно добавить к <tex>B</tex> с сохранением его независимости, тогда <tex>j<i</tex>. Но тогда он уже был бы добавлен на <tex>j</tex>-ом шаге алгоритма.
  
 
Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
 
Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
  
Алгоритм работает за <tex>O(\mid X \mid log(\mid X \mid))</tex>: <tex>O(\mid X \mid log(\mid X \mid))</tex> — на сортировку массива весов элементов из <tex>X</tex> и <tex>O(\mid X \mid)</tex> шагов цикла, каждый из которых работает <tex>O(1)</tex> времени (если считать, что проверка множества на независимость происходит за <tex>O(1)</tex>).
+
Алгоритм работает за <tex>O(\mid X \mid log(\mid X \mid))</tex>. <tex>O(\mid X \mid log(\mid X \mid))</tex> — на сортировку элементов из <tex>X</tex> по возрастанию весов и <tex>O(\mid X \mid)</tex> шагов цикла, каждый из которых работает <tex>O(1)</tex> времени (если считать, что проверка множества на независимость происходит за <tex>O(1)</tex>).
 
}}
 
}}

Версия 22:09, 17 мая 2011

Теорема (жадный алгоритм поиска базы минимального веса):
Пусть на носителе матроида [math]M = \langle X, I \rangle[/math] задана весовая функция [math]\omega: X \to \mathbb R[/math]. Для любого [math]A \subset X[/math] выполнено: [math]\omega(A) = \sum\limits _{x \in A} \omega(x)[/math]. Тогда база минимального веса матроида [math]M[/math] ищется жадно.
Доказательство:
[math]\triangleright[/math]

Псевдокод алгоритма:

[math]sort(X)[/math]    // сортируем элементы по возрастанию веса
[math]B \leftarrow \emptyset[/math]
for [math]i \leftarrow 0[/math] to [math]\mid X \mid-1[/math] do
  if [math]B \cup X[i] \in I[/math]
    [math]B \leftarrow B \cup X[i][/math]

Рассмотрим шаг алгоритма, когда мы пытаемся добавить элемент [math]X[i][/math]. Заметим, что если его можно добавить с сохранением независимости множества [math]B[/math], то это элемент минимального веса не из [math]B[/math], который можно добавить (при условии сохранения независимости [math]B[/math] при добавлении). В самом деле, пусть [math]X[j][/math] — элемент минимального веса, который можно добавить к [math]B[/math] с сохранением его независимости, тогда [math]j\lt i[/math]. Но тогда он уже был бы добавлен на [math]j[/math]-ом шаге алгоритма.

Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По теореме Радо-Эдмондса множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из [math]X[/math] так, чтобы после каждого добавления множество оставалось независимым.

Алгоритм работает за [math]O(\mid X \mid log(\mid X \mid))[/math]. [math]O(\mid X \mid log(\mid X \mid))[/math] — на сортировку элементов из [math]X[/math] по возрастанию весов и [math]O(\mid X \mid)[/math] шагов цикла, каждый из которых работает [math]O(1)[/math] времени (если считать, что проверка множества на независимость происходит за [math]O(1)[/math]).
[math]\triangleleft[/math]