Я разработал новую методику дерандомизации, которая нацелена на рекурсивные рандомизированные алгоритмы (или) более общие рандомизированные алгоритмы, которые используют стек. К сожалению, я не смог найти естественные рандомизированные алгоритмы для применения моих методов. Рекурсивные цепи Маркова и стохастические грамматики очень близки к тому, что я ищу. Существуют ли другие (более естественные) рандомизированные алгоритмы, которые "существенно" используют стек? Любая помощь очень ценится, так как я застрял с этим в течение более шести месяцев.
Чтобы дать вам больше контекста, я ищу список проблем, похожих на те, что описаны в статье SivaKumar . Обратите внимание, что SivaKumar использовал псевдослучайный генератор Нисана, чтобы дерандомизировать эти проблемы.
источник
Ответы:
Как указывает Пер Вогнсен, и в более общем смысле, существует множество геометрических алгоритмов, которые работают следующим образом: выбирают случайную выборку и рекурсивно запускают выборку и другие производные от нее структуры. Рандомизированный алгоритм Кларксона для линейного программирования, а также ряд Зейделя и, в действительности, ряд Матусека-Шарира-Вельцля, о котором упоминает Пер, работают именно таким образом, и парадигма Кларксона распространяется и на другие ситуации, когда вы строите некую разновидность резания или эпсилон-сеть и рекурсивную ,
К сожалению, вы вряд ли получите новый результат от этого, потому что есть оптимальные дерандомизации этих алгоритмов, благодаря работе Matousek и Chazelle. Статья Шазель является хорошим ориентиром для этой работы и предыдущей работы Матусека. Но это может быть хорошей проверкой вашего метода: трудно было придумать эти дерандомизации, и если ваш метод обеспечивает подход черного ящика, начинающийся с (более простого) рандомизированного алгоритма, это было бы здорово.
ps это, пожалуй, самый скучный пример из всех возможных, но работает ли ваш метод на быстрой сортировке или на любом из методов рандомизированного нахождения медианы?
источник
Как насчет рандомизированного алгоритма Вельцля для минимальных вмещающих эллипсоидов? Он имеет глубину рекурсии O (d), где d - размерность пространства.
Я почти ничего не знаю о дерандомизации, так что это может быть не то, что вы ищете. Если мой пример не подходит (может быть, по вашему определению он использует только рекурсию?), Возможно, вы могли бы уточнить, почему это так. Это увеличило бы шансы получить более качественные и более подходящие ответы от других.
источник
Более быстрая версия алгоритма min-cut действительно очень рекурсивна. Смотрите рисунок 2.5 здесь , или любой стандартный учебник по рандомизированным алгоритмам.
источник