Ah, los algoritmos aleatorios son ciertamente muy hermosos. A menudo pueden expresarse de manera muy simple e intuitiva , y aún así ser un dolor de analizar. Después de haber hecho un curso sobre el tema, puedo empatizar totalmente contigo.
En el núcleo de los algos aleatorizados, está el análisis . El hecho de que pueden ser bastante prácticos e intuitivos está muy bien, pero en el momento en que te pones a analizar, ¡ es cuando todo pasa por alto ! Si alguna vez siente que es “simplemente teórico”, estoy seguro de que es solo porque el análisis es bastante complejo.
Métodos de Monte Carlo:
Hay bastantes sabores de algoritmos aleatorios. Como mencionó Devansh Gupta, existe el método Monte Carlo , que estima las probabilidades ejecutando una gran cantidad de simulaciones.
Considera esta pregunta:
Q. Estime el número de divisores de un número dado [math] n [/ math].
Resp. Considere el siguiente algoritmo …
para iteraciones M, haga:
d = número aleatorio en 1 a n
si (d es un divisor de n):
cnt incremental
retorno cnt / M * n
Entonces, aquí tenemos un gran espacio de búsqueda (tamaño [matemático] n [/ matemático]), y si tuviéramos que probar cada valor, tomaría [matemático] O (n) [/ matemático] tiempo. Pero si hiciéramos lo anterior, solo tomaría tiempo [matemático] O (M) [/ matemático]. Estaría apagado, pero luego la pregunta pide una estimación .
Bueno, claramente la intuición del algoritmo es bastante sencilla. Pero cualquiera haría la pregunta “¿Pero qué tan bueno es el algoritmo? ¿Qué tan lejos del valor real está la respuesta? Si tuviera que probar el algoritmo con una [matemática] M [/ matemática] mayor , ¿cuánto mejor sería mi estimación? ? “ Y ahí es donde entra el análisis . Ahí es donde parece que “los algoritmos aleatorios son solo sobre teoría”.
Supongamos que debo usar el hecho de que, si [matemática] d [/ matemática] es un factor, entonces también lo es [matemática] n / d [/ matemática], y simplemente estimar el número de divisores en el rango [matemática] [ 1, \ sqrt {n}] [/ math] y duplica eso?
para iteraciones M, haga:
d = número aleatorio en 1 a sqrt (n)
si (d es un divisor de n):
cnt incremental
devuelve 2 * cnt / M * root (n)
Bueno, bastante intuitivamente, este segundo enfoque es mejor que el primero. ¿Pero cómo mostramos eso? Esta es solo una ilustración simple de cómo se pueden usar diferentes esquemas de simulación para estimar la misma cantidad usando los métodos de Monte Carlo, y sin embargo, uno es mejor que el otro.
Palabra final: en general, está tratando de responder la pregunta: “¿Cuál es el menor número de simulaciones que necesito ( M ) para asegurar que con al menos probabilidad p (algún tipo de valor de confianza) no me salga de la respuesta correcta? más de dx (algún valor de tolerancia)? ”
Muestreo:
Otro tipo de área donde uno podría usar algoritmos aleatorios es prácticamente solo buscar un tipo particular de estructura. El espacio de búsqueda puede ser enorme, y en tales casos uno probará un montón de ejemplos y luego dirá “encontrado” o “probablemente no existe”. Además, versiones como “Esta estructura se da para existir. Encuéntrela”.
Podemos modificar nuestro ejemplo anterior aquí también.
isPrime (n):
para iteraciones M, haga:
d = número aleatorio en 2 a n-1
si (d es divisor de n):
volver "no es primo"
volver "probablemente sea primo"
Ahora, si tuviéramos que compararlo con
isPrime (n):
para iteraciones M, haga:
d = número aleatorio en 2 a sqrt (n)
si (d es divisor de n):
volver "no es primo"
volver "probablemente sea primo"
Algunos analisis:
Sea [math] d (n) [/ math] = número de divisores de [math] n [/ math] distintos de 1 y n
Ahora, en algo (1), el problema de encontrar un factor [matemática] p_1 (n) = d (n) / (n-2) [/ matemática]
Entonces, la probabilidad de estar equivocado = Prob que n es compuesto y devuelve “es probablemente primo” = [matemática] (1-p_1 (n)) ^ M [/ matemática]
En algo (2), problema de encontrar un factor [matemática] p_2 (n) = (d (n) / 2) / \ sqrt {n} -1) [/ matemática]
Entonces, la probabilidad de estar equivocado = … = [matemática] (1-p_2 (n)) ^ M [/ matemática].
Nota, [matemáticas] p_2 (n)> p_1 (n) [/ matemáticas]
Por lo tanto, para un valor de tolerancia dado, necesitamos ejecutar muchas menos iteraciones del algoritmo 2.
Un ejemplo de programación competitiva:
Teniendo en cuenta que “Codechef”, “Codeforces” y “TopCoder” se han etiquetado como temas de preguntas, me gustaría ofrecer este ejemplo como voluntario, ya que uno de “existe una estructura: encuéntrelo”.
Esta pregunta apareció en una ronda reciente de Codeforces (# 192, Div1, C): Problema – C – Codeforces. La pregunta básicamente pregunta lo siguiente:
Dado un gráfico sobre los vértices [matemáticos] n [/ matemáticos] y los bordes [matemáticos] m [/ matemáticos] , donde cada vértice tiene un grado máximo de 2, encuentre una subgrafía de su complemento que tenga las mismas propiedades (grado limitado, número de vértices, número de aristas) .
Debido al hecho de que el grado de cada vértice es al menos 2, para large-ish [math] n [/ math], el grado del vértice en el complemento también es grande. Por lo tanto, las posibilidades de encontrar un gráfico de este tipo son bastante altas.
Lo que había hecho fue que, para [matemáticas] n <= 7 [/ matemáticas], verifiqué todas las posibles subgrafías del complemento para las propiedades. Para [matemáticas] n> 7 [/ matemáticas], busqué un ciclo de longitud [matemáticas] m [/ matemáticas] en el gráfico del complemento.
aunque cierto:
seleccione x [] una permutación aleatoria de 1 a n
para i en 1 a m-1:
if (x [i], x [i + 1]) es una arista en el gráfico original:
baraja la permutación desde (x [i-1] ... x [i + 2])
reiniciar la comprobación desde i = i-2
si (x [1], x [m]) están conectados:
repetir todo el procedimiento
más:
ciclo de salida definido por vértices x [1], x [2], ..., x [m] y salir
Tenga en cuenta que, dado que sé que x [1], x [2], …, x [i-2] no causan ningún conflicto, después de mi reorganización solo necesito verificar si hay conflictos desde i-2 en adelante. Este tipo de técnica de “arreglo local” se ha utilizado mucho recientemente como el lema local Algorithmic Lovász (por desgracia, parece que la página de wikipedia es bastante compleja :()
El editorial de Ashar Fuadi describe una solución similar (Codeforces Round # 192 Editorial – Codeforces se desplaza hacia abajo a “solución no determinista” 329C), excepto que el procedimiento se repite desde cero tan pronto como se encuentra un borde. Esto también aparentemente funciona lo suficientemente bien en 100 iteraciones.
