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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 7: Строка 7:
 
Псевдокод алгоритма:
 
Псевдокод алгоритма:
 
  <tex>sort(X)</tex>    // сортируем элементы по возрастанию веса
 
  <tex>sort(X)</tex>    // сортируем элементы по возрастанию веса
  <tex>B \leftarrow \emptyset</tex>
+
  <tex>B \leftarrow \varnothing</tex>
 
  '''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>|X|-1</tex> '''do'''
 
  '''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>|X|-1</tex> '''do'''
 
   '''if''' <tex>B \cup X[i] \in I</tex>
 
   '''if''' <tex>B \cup X[i] \in I</tex>

Версия 05:54, 29 июня 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 \varnothing[/math]
for [math]i \leftarrow 0[/math] to [math]|X|-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]B[/math] с сохранением его независимости, тогда [math]j\lt i[/math]. Но тогда он уже был бы добавлен на [math]j[/math]-ом шаге алгоритма.

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

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