4511
правок
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:44, 16 апреля 2016
, 16 апреля 2016→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 66: | Строка 66: | ||
Остаются нерешенными следующие задачи: | Остаются нерешенными следующие задачи: | ||
1. Можно ли устранить рандомизированность из алгоритма KKT? Гибридный алгоритм, использующий KKT внутри модифицированной версии алгоритма Петти-Рамачандрана [14], приведен в работах [16, 17]; он исполняется за ожидаемое линейное время и использует только O(log* n) случайных бит. Можно ли избавиться и от этого небольшого влияния случайности? Если устранить из алгоритма KKT все случайные факторы, это позволит достичь линейной временной границы для алгоритма Петти-Рамачандрана [14] и создать еще один оптимальный детерминированный алгоритм MST – на сей раз на базе KKT. | 1. Можно ли устранить рандомизированность из алгоритма KKT? Гибридный алгоритм, использующий KKT внутри модифицированной версии алгоритма Петти-Рамачандрана [14], приведен в работах [16, 17]; он исполняется за ожидаемое линейное время и использует только <math>O(log^* \; n)</math> случайных бит. Можно ли избавиться и от этого небольшого влияния случайности? Если устранить из алгоритма KKT все случайные факторы, это позволит достичь линейной временной границы для алгоритма Петти-Рамачандрана [14] и создать еще один оптимальный детерминированный алгоритм MST – на сей раз на базе KKT. | ||
2. Можно ли устранить рандомизированность из оптимальных с точки зрения операций параллельных алгоритмов [ | 2. Можно ли устранить рандомизированность из оптимальных с точки зрения операций параллельных алгоритмов [10] для MST? Линейный по числу операций параллельный MST-алгоритм с ожидаемым логарифмическим временем исполнения для EREW PRAM приведен в [15]. Этот алгоритм является оптимальным и с точки зрения операций, и с точки зрения временных затрат. Однако он использует линейное количество случайных бит. В [16, 17] приведен оптимальный с точки зрения операций параллельный алгоритм, исполняющийся за ожидаемое полилогарифмическое время и использующий только полилогарифмическое число случайных бит. В силу этого интересны следующие, пока открытые, вопросы, касающиеся параллельных алгоритмов для задачи MST: | ||
• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней линейной границей) в оптимальном с точки зрения времени и операций параллельном алгоритме MST? | • До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней линейной границей) в оптимальном с точки зрения времени и операций параллельном алгоритме MST? | ||
• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней полилогарифмической границей) в оптимальном с точки зрения операций параллельном алгоритме с разумной степенью параллелизма (скажем, имеющем полилогарифмическое время параллельного исполнения)? | • До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней полилогарифмической границей) в оптимальном с точки зрения операций параллельном алгоритме с разумной степенью параллелизма (скажем, имеющем полилогарифмическое время параллельного исполнения)? | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||