4511
правок
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Перейти к навигации
Перейти к поиску
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:33, 16 апреля 2016
, 16 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время исполнения составляло O(m log n). Среди них стоит упомянуть алгоритмы Борувки [ ], Ярника [8] (впоследствии переоткрытый Дейкстрой и Примом [ ]) и Крускала [5]. | Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время исполнения составляло O(m log n). Среди них стоит упомянуть алгоритмы Борувки [1], Ярника [8] (впоследствии переоткрытый Дейкстрой и Примом [5]) и Крускала [5]. | ||
Самый быстрый известный алгоритм MST до создания KKT исполнялся за время O( | Самый быстрый известный алгоритм MST до создания KKT исполнялся за время <math>O(m \; log \; \beta (m, n))</math> [7], где <math>\beta (m, n) = min \{ i | log^{(i)} n \le m/n \}</math> [7]; здесь <math>log^{(i)} n \;</math> определяется как <math>log \; n</math>, если i = 1, и <math>log \; log^{(i - 1)} n \;</math>, если i > 1. Хотя это время исполнения близко к линейному, оно не является линейным в случае очень разреженных графов. | ||