Я часто слышу, что для многих задач мы знаем очень изящные рандомизированные алгоритмы, но нет или только более сложные детерминированные решения. Тем не менее, я знаю только несколько примеров для этого. Наиболее заметно
- Рандомизированная быстрая сортировка (и связанные геометрические алгоритмы, например, для выпуклых оболочек)
- Рандомизированный Минцут
- Проверка полиномиальной идентичности
- Проблема измерения Кли
Среди них только полиномиальное тестирование идентичности кажется действительно трудным без использования случайности.
Знаете ли вы больше примеров проблем, когда рандомизированное решение является очень элегантным или очень эффективным, а детерминированные решения - нет? В идеале, проблемы должны быть легко мотивированы для непрофессионалов (в отличие, например, от проверки полиномиальной идентичности).
Ответы:
Сортировка гайки и болты
Следующая проблема была предложена Роулинсом в 1992 году. Предположим, вам дан набор из n гаек и n болтов. Каждый болт соответствует ровно одной гайке, в противном случае гайки и болты имеют разные размеры. Размеры слишком близки, чтобы позволить прямое сравнение между парами болтов или парами гаек. Однако вы можете сравнить любую гайку с любым болтом, пытаясь скрутить их вместе; в постоянное время вы обнаружите, является ли болт слишком большим, слишком маленьким или подходящим для гайки. Ваша задача - выяснить, какой болт подходит для каждой гайки, или, что то же самое, отсортировать гайки и болты по размеру.
Простой вариант рандомизированной быстрой сортировки решает проблему за время с высокой вероятностью. Выберите случайный болт; используйте это, чтобы разделить орехи; используйте подходящую гайку для разделения болтов; и рекурсировать. Однако найти детерминистический алгоритм, который работает даже в o ( n 2 ) , нетривиально. Детерминированные O ( n log n ) -временные алгоритмы были наконец найдены в 1995 году Брэдфордом и независимо друг от друга Комлосом, Ма и Семереди. В обоих случаях оба алгоритма используют варианты параллельной сортировочной сети AKS, поэтому скрытая константа в O ( n log n )O(nlogn) o(n2) O(nlogn) O(nlogn) ограничение по времени довольно большое; скрытая константа для рандомизированного алгоритма равна 4.
источник
Если вы не просто говорите о поли-времени, а скорее смотрите на многие модели вычислений, которые мы изучаем, везде есть примеры:
В Logspace: Ненаправленное подключение ST (в RL с 1979 года и в L только с 2005 года)
В NC: Нахождение идеального соответствия в двудольном графе параллельно (в RNC и до сих пор неизвестно, что в NC)
В интерактивных доказательствах: детерминированные дают NP, в то время как рандомизированные могут делать PSPACE. Связанный: проверка доказательства детерминистически требует рассмотрения всех доказательств, в то время как доказательства PCP позволяют проверять только постоянное число битов.
В алгоритмическом проектировании механизмов: множество рандомизированных механизмов достоверного приближения без детерминированного аналога.
В сложности коммуникации: функция равенства требует линейной связи детерминистически, но логарифмически (или, в зависимости от точной модели, константы) связь случайно
В деревьях решений: оценка дерева и / или дерева требует линейных запросов детерминистически, но намного меньше с рандомизацией. Это по сути эквивалентно альфа-бета-обрезке, которая дает рандомизированный сублинейный алгоритм для оценки игрового дерева.
В потоковых моделях, моделях распределенных вычислений: см. Предыдущие ответы.
источник
Большинство потоковых алгоритмов
В потоковой модели вычислений ( AMS , book ) алгоритм обрабатывает онлайн-последовательность обновлений и ограничивается только сублинейным пространством. В любой момент времени алгоритм должен иметь возможность ответить на запрос.
источник
[1] Майкл Луби: простой параллельный алгоритм для задачи о максимальном независимом множестве. SIAM J. Comput. 15 (4): 1036-1053 (1986) http://dx.doi.org/10.1137/0215074
[2] Алессандро Панконези, Аравинд Шринивасан: О сложности разложения распределенных сетей. J. Алгоритмы 20 (2): 356-374 (1996) http://dx.doi.org/10.1006/jagm.1996.0017
[3] Фабиан Кун, Томас Москиброда, Роджер Ваттенхофер: Локальные вычисления: нижние и верхние границы. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470
источник
Выборы лидера в анонимном кольце процессов
Есть простой аргумент (например, [1]), что для анонимного кольца не существует детерминированного алгоритма выбора лидера.
Модель: мы предполагаем, что вычисления продвигаются в синхронных раундах, где в каждом раунде каждый процесс выполняет некоторые локальные вычисления, отправляет сообщения своим соседям по кольцу и получает сообщения от своих соседей.
[1] Дана Англуин: Локальные и глобальные свойства в сетях процессоров (расширенная аннотация). STOC 1980: 82-93. http://doi.acm.org/10.1145/800141.804655
источник
Проблема большинства в модели запросов.
FRK Chung, RL Graham, J. Mao и AC Yao. Забывчивые и адаптивные стратегии для задач большинства и множественности, Proc. COCOON 2005 , с. 329–338.
источник