He desarrollado una nueva técnica de desrandomización que está dirigida a algoritmos aleatorios recursivos (o) algoritmos aleatorios más generales que usan una pila. Desafortunadamente, no pude encontrar algoritmos aleatorios naturales para aplicar mis técnicas. Las cadenas recursivas de Markov y las gramáticas estocásticas están muy cerca de lo que estoy buscando. ¿Existen otros algoritmos aleatorios (más naturales) que hacen un uso "esencial" de la pila? Cualquier ayuda es muy apreciada, ya que estoy atrapado en esto por más de seis meses.
Para darle más contexto, estoy buscando una lista de problemas similares a los del Documento de SivaKumar . Tenga en cuenta que SivaKumar utilizó el generador pseudoaleatorio de Nisan para desrandomizar estos problemas.
fuente
Respuestas:
Como señala Per Vognsen, y de manera más general también, hay muchos algoritmos geométricos que operan de la siguiente manera: Elija una muestra aleatoria y corra recursivamente en la muestra y en otras estructuras derivadas de la misma. El algoritmo aleatorio de Clarkson para programación lineal, así como el de Seidel y, de hecho, la serie Matousek-Sharir-Welzl que menciona Per, funcionan de esta manera, y el paradigma de Clarkson se extiende a otras situaciones en las que se construye algún tipo de corte o epsilon-net y recurse .
Desafortunadamente, es poco probable que obtenga un nuevo resultado de esto, porque hay desrandomizaciones óptimas de estos algoritmos, debido al trabajo de Matousek y Chazelle. El artículo de Chazelle es un buen punto de referencia para este trabajo y el trabajo previo de Matousek. Pero podría ser una buena prueba de su método: fue difícil encontrar estas desviaciones aleatorias, y si su método proporciona un enfoque de recuadro negro que comience con el algoritmo aleatorio (más fácil), sería genial.
PD: este es probablemente el ejemplo más aburrido posible, pero ¿funciona su método en la clasificación rápida o en alguno de los métodos de búsqueda mediana aleatorizados?
fuente
¿Qué tal el algoritmo aleatorizado de Welzl para elipsoides envolventes mínimos? Tiene una profundidad de recursión O (d) donde d es la dimensión del espacio.
No sé casi nada sobre la desrandomización, por lo que puede que esto no sea lo que estás buscando. Si mi ejemplo no califica (¿tal vez, según su definición, solo hace un uso no esencial de la recursividad?), Tal vez podría aclarar por qué es así. Eso aumentaría las posibilidades de una mayor calidad, respuestas más pertinentes de otros.
fuente
La versión más rápida del algoritmo min-cut es muy recursiva. Vea la figura 2.5 aquí , o cualquier libro de texto de algoritmos aleatorios estándar.
fuente