Hay éxito algoritmos numéricos que consiste en una secuencia de números aleatorios, como métodos de Monte Carlo o recocido simulado. Puedo seguir las líneas de las pruebas de su convergencia y realmente verlos trabajar. Sin embargo a veces creo que es paradójico que resulta útil añadir deliberadamente un factor impredecible en un proceso, mientras que tenemos la oportunidad de tener el control completo sobre él. ¿Podrías dar una explicación intuitiva para esto?
Respuestas
¿Demasiados anuncios?
CodingWithoutComments
Puntos
9412
Imagínese que usted está buscando para una estructura con ciertas propiedades, dentro de un universo de posibles estructuras. Es que a veces (tal vez "a menudo"?) en el caso de que las estructuras en realidad se puede crear de forma explícita la forma de una pequeña fracción de ese universo, pero por otro lado que todos no tienen la propiedad que usted busca.
Por lo tanto, si usted quería escribir un programa para generar "buenas" de las estructuras, se podría trabajar muy duro y encontrar una manera de construir explícitamente a ellos, o simplemente puede elegir una estructura al azar (suponiendo que se tiene una buena manera de hacer esto), comprobar si es "buena", y repetir si no.
Un ejemplo clásico: el expansor de gráfico. Es ridículamente fácil crear uno con sólo la elección de un gráfico al azar. Explícito construcciones, por otro lado, están lejos de ser trivial.
Es un problema abierto si esto realmente ayuda, desde la perspectiva de la teoría de la complejidad. Las personas han encontrado inteligente "derandomization" los esquemas que, básicamente, convertir un algoritmo aleatorio para un determinista. Todavía no se sabe si lo que usted puede hacer en un tiempo razonable con la aleatorización (RP) es realmente más de lo que usted puede hacer en un tiempo razonable, sin acceso a la aleatoriedad (P), y creo que la mayoría de la gente cree que no es - en otras palabras, la aleatoriedad no es realmente el "trabajo".
Jarod Elliott
Puntos
7124
No estoy seguro que si este es el tipo de respuesta que busca, pero en algunos casos, se le garantiza una cierta probabilidad de éxito si elige su parámetro al azar, pero no hay ningún procedimiento conocido para elegir un buen parámetro. El mejor ejemplo de esto es la prueba de primalidad, donde usted puede demostrar que al menos 1/2 de los posibles testigos para el trabajo de primalidad.
Arda Xi
Puntos
1099
Además de los diversos razonables general de las cosas descritas por otras personas, es posible que desee aprender acerca de la formalización de la noción de aleatoriedad: la BFF de la complejidad de la clase.
Es interesante que la mayoría de los científicos creen P = BPP. Esta igualdad significa que (al menos teóricamente) se puede reescribir todos los algoritmos que usan la aleatoriedad como los algoritmos no el uso de la aleatoriedad. Pero no está comprobado.
Por ejemplo, la existencia de fuertes generadores pseudoaleatorios (enlace a mi MO pregunta) implica P = BPP. Pero que es en sí mismo un gran problema.
Así que es muy duro para demostrar el teorema de eiher manera. Por supuesto, cuando la gente trató de probar P = BPP o su opuesto, que tenía un montón de explicaciones de por qué su teorema es verdadero. Ninguna de esas explicaciones es totalmente acertado, pero que podría responder a su pregunta acerca de la idea de aleatoriedad.
skfd
Puntos
463
Esto no es una respuesta completa, pero he encontrado que es útil para pensar de esta manera en el pasado. Parte de la razón por la que la aleatoriedad es "mejor", aunque, de nuevo, ciertamente no todos-es sólo debido a la forma en que se cuantifica en lo bueno o malo de los algoritmos.
Por lo que debe ser un familiar el hecho de que existen algoritmos que lo hacen muy bien la mayoría del tiempo, pero que no hacen bien en el peor de los casos. Dos ejemplos cotidianos son quicksort y el algoritmo del simplex. La razón de esto es que estos algoritmos no son tan sensibles como podría ser para ciertos tipos de cambios en los datos, por lo que un adversario que está tratando de hacer que su algoritmo de ejecución lenta tiene un montón de espacio para trabajar." Pero una distribución uniforme (o algo moralmente equivalente, o un montón de distribuciones que surgen en el mundo real) no es contradictorio.
Así lo aleatorio algoritmos que vamos a hacer es tomar una sola instancia de un problema, y en lugar de la muestra a partir de una distribución de un montón de instancias de otro, relacionadas con el problema, por lo que llegar a su trabajo (hasta cierto punto) con un promedio de de caso de la complejidad en lugar de con el peor de los casos. Otra manera de pensar acerca de ti: tu adversario desde antes de que pudiera crear duro instancias, ya que él sabía lo que su algoritmo de hacer de antemano, y que él había sneaky maneras de hacer el problema más difícil sin su algoritmo de darse cuenta hasta que fue demasiado tarde. Pero ahora él no sabe lo que el algoritmo -- es al azar! Para la creación de un duro instancia parece bastante desesperada.
La mayoría del resto de la ventaja de azar algoritmos, la "gran ventaja", si se quiere -- viene de lo Alon dijo anteriormente. Hay ciertas propiedades deseables que parecen estar correlacionados con los de "alta complejidad" o cadenas de distribución, que, por definición, no puede ser alcanzado rápidamente y de manera determinista. Esto está estrechamente relacionada con la eficacia del método de probabilidades en la combinatoria.
Michiel de Mare
Puntos
15888
Hay alternativas al azar métodos que intentan mantener las ventajas de azar métodos y mejorar en ellos.
Cuasi-métodos de Monte Carlo son deterministas. Ellos dependen de las secuencias que se distribuye de forma más homogénea de lo que realmente secuencias aleatorias. (Irónicamente, se parecen más a lo que la mayoría de la gente espera de la aleatoriedad. Verdadera aleatoriedad parece demasiado grumoso para ojos no entrenados. Ver estos gráficos.)
Para algunos de integración numérica de problemas, QMC métodos de superar MC métodos. Arte Owen publicado varios artículos sobre esto. QMC funciona mejor cuando la dimensión efectiva de un problema es inferior a la completa dimensión. Por ejemplo, un problema que depende de 500 variables, pero el 20 de esas variables son mucho más importantes que el resto.
QMC métodos no proporcionar fácilmente un error de estimación. Para evitar esto, la gente a veces se combinan QMC con MC. Se puede tomar un QMC cuadrícula de puntos y se agitan al azar. En algunos problemas, este enfoque híbrido funciona mejor que cualquiera de los enfoques por separado.
