Eu desenvolvi uma nova técnica de derandomização que visa algoritmos aleatórios recursivos (ou) algoritmos aleatórios mais geralmente que usam uma pilha. Infelizmente, não consegui encontrar algoritmos aleatórios naturais para aplicar minhas técnicas. As correntes recursivas de Markov e as gramáticas estocásticas estão muito próximas do que estou procurando. Existem outros algoritmos aleatórios (mais naturais) que fazem uso "essencial" da pilha? Qualquer ajuda é muito apreciada, pois estou preso a isso há mais de seis meses.
Para lhe dar mais contexto, estou procurando uma lista de problemas semelhantes aos do documento de SivaKumar . Observe que o SivaKumar usou o gerador pseudo-aleatório do Nisan para derandomizar esses problemas.
randomness
derandomization
Shiva Kintali
fonte
fonte
Respostas:
Como aponta Per Vognsen, e de maneira mais geral, existem muitos algoritmos geométricos que operam da seguinte maneira: Escolha uma amostra aleatória e execute recursivamente na amostra e em outras estruturas derivadas dela. O algoritmo aleatório de Clarkson para programação linear, bem como o de Seidel e, de fato, a série Matousek-Sharir-Welzl que Per menciona, todos operam dessa maneira, e o paradigma de Clarkson se estende a outras situações em que você cria algum tipo de corte ou rede de epsilon e recorre .
Infelizmente, é improvável que você obtenha um novo resultado disso, porque existem derandomizações ótimas desses algoritmos, devido ao trabalho de Matousek e Chazelle. O artigo de Chazelle é um bom ponto de referência para este trabalho e trabalho anterior de Matousek. Mas pode ser um bom teste para o seu método: era difícil criar essas derandomizações, e se o seu método fornecer uma abordagem de caixa preta começando com o algoritmo aleatório (mais fácil), isso seria legal.
ps este é provavelmente o exemplo mais chato possível, mas o seu método funciona no quicksort ou em algum dos métodos aleatórios de mediana?
fonte
E o algoritmo aleatório de Welzl para o mínimo de elipsóides anexos? Possui profundidade de recursão O (d) onde d é a dimensão do espaço.
Não sei quase nada sobre derandomização, portanto, pode não ser o que você está procurando. Se meu exemplo não se qualificar (talvez por sua definição ele faça uso desnecessário de recursão?), Talvez você possa esclarecer por que motivo. Isso aumentaria as chances de maior qualidade, respostas mais pertinentes de outras pessoas.
fonte
A versão mais rápida do algoritmo min-cut é realmente muito recursiva. Veja a figura 2.5 aqui ou qualquer manual padrão de algoritmos aleatórios.
fonte