Herramientas de usuario
algoritmos-oia:backtracking
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:backtracking [2020/04/30 04:01] santo [Idea] |
algoritmos-oia:backtracking [2020/05/01 14:26] (actual) santo [Técnica de backtracking:] |
||
|---|---|---|---|
| Línea 3: | Línea 3: | ||
| En muchísimos problemas, existe un espacio de **potenciales candidatos**, entre los cuales solamente algunos cumplen ciertas condiciones, que los hacen **válidos**. Algunas cosas muy comunes que se pueden querer hacer en estos casos son: | En muchísimos problemas, existe un espacio de **potenciales candidatos**, entre los cuales solamente algunos cumplen ciertas condiciones, que los hacen **válidos**. Algunas cosas muy comunes que se pueden querer hacer en estos casos son: | ||
| - | * Encontrar alguna solución válidas. | + | * Encontrar alguna solución válida. |
| * Contar o enumerar todas las soluciones válidas. | * Contar o enumerar todas las soluciones válidas. | ||
| * Encontrar **la mejor** de todas las soluciones válidas (el criterio o "la cuenta" para determinar cuál de todas las soluciones es la mejor depende de cada problema) | * Encontrar **la mejor** de todas las soluciones válidas (el criterio o "la cuenta" para determinar cuál de todas las soluciones es la mejor depende de cada problema) | ||
| Línea 71: | Línea 71: | ||
| El método de backtracking se basa en especificar más precisamente cómo se van a explorar exhaustivamente los candidatos: en lugar de quedar a criterio del programador como en fuerza bruta (porque en ese caso igualmente se van a analizar todos uno por uno), el método de backtracking requiere definir un **proceso de construcción de solución en etapas**. La cantidad de etapas y la elección que hay que hacer en cada etapa pueden variar de problema en problema, de maneras muy complicadas, pero este método siempre requiere que definamos etapas o pasos incrementales que concluyen finalmente en un candidato bien construido. | El método de backtracking se basa en especificar más precisamente cómo se van a explorar exhaustivamente los candidatos: en lugar de quedar a criterio del programador como en fuerza bruta (porque en ese caso igualmente se van a analizar todos uno por uno), el método de backtracking requiere definir un **proceso de construcción de solución en etapas**. La cantidad de etapas y la elección que hay que hacer en cada etapa pueden variar de problema en problema, de maneras muy complicadas, pero este método siempre requiere que definamos etapas o pasos incrementales que concluyen finalmente en un candidato bien construido. | ||
| - | Desde la situación inicial, en la cual todavía no hemos elegido nada ni realizado ningún paso, a cada candidato posible podemos llegar mediante una serie de elecciones diferentes. **Es la secuencia de elecciones que realizamos en cada etapa lo que va a definir exactamente a qué candidato llegamos.** | + | Desde la situación inicial, en la cual todavía no hemos elegido nada ni realizado ningún paso, a cada candidato posible podemos llegar mediante una serie de elecciones diferentes. **Es la secuencia de elecciones que realizamos lo que va a definir exactamente a qué candidato llegamos.** |
| La clave está en que el método de backtracking nos exige verificar que el candidato que estamos construyendo sea válido no solamente al final (como en fuerza bruta) cuando ya está totalmente construido, sino **en cada paso** de la construcción. Lógicamente, no vamos a poder en general estar 100% seguros acerca de la validez con un candidato que solamente está parcialmente construido. Sin embargo, en la inmensa mayoría de los casos, existen secuencias de elecciones parciales que violan alguna restricción de nuestro problema, de manera que mirando solamente esas primeras elecciones ya podemos estar seguros de que **ningún** candidato que se obtenga agregando más elecciones podrá resultar válido al final, porque "ya empezamos mal". | La clave está en que el método de backtracking nos exige verificar que el candidato que estamos construyendo sea válido no solamente al final (como en fuerza bruta) cuando ya está totalmente construido, sino **en cada paso** de la construcción. Lógicamente, no vamos a poder en general estar 100% seguros acerca de la validez con un candidato que solamente está parcialmente construido. Sin embargo, en la inmensa mayoría de los casos, existen secuencias de elecciones parciales que violan alguna restricción de nuestro problema, de manera que mirando solamente esas primeras elecciones ya podemos estar seguros de que **ningún** candidato que se obtenga agregando más elecciones podrá resultar válido al final, porque "ya empezamos mal". | ||
| Línea 83: | Línea 83: | ||
| Luego de la primera elección, tenemos fijado $x$, así que sabemos el primer elemento de nuestra terna, pero no los últimos dos. ¿Tenemos algún chequeo que podamos realizar que nos garantice que es imposible que ese $x$ funcione? La ecuación $x^2 + y^2 = z^2$ no nos ayuda demasiado, ya que no conocemos aún ni $y$ ni $z$. Pero hay algo interesante en la última ecuación: se puede reescribir como $5(2y+403 z) = 448103 - 28x$. Esto nos muestra que $448103 - 28x$ ¡debe ser sí o sí un múltiplo de 5! Podemos verificar esto y si resulta que no lo es, directamente descartar esa elección. | Luego de la primera elección, tenemos fijado $x$, así que sabemos el primer elemento de nuestra terna, pero no los últimos dos. ¿Tenemos algún chequeo que podamos realizar que nos garantice que es imposible que ese $x$ funcione? La ecuación $x^2 + y^2 = z^2$ no nos ayuda demasiado, ya que no conocemos aún ni $y$ ni $z$. Pero hay algo interesante en la última ecuación: se puede reescribir como $5(2y+403 z) = 448103 - 28x$. Esto nos muestra que $448103 - 28x$ ¡debe ser sí o sí un múltiplo de 5! Podemos verificar esto y si resulta que no lo es, directamente descartar esa elección. | ||
| - | Similarmente, una vez que tenemos elegidos $x$ y $y$, como la última ecuación se puede ver también como $2015 z = 448103 - 28x-10y$, tenemos que el número $448103 - 28x-10y$ tiene que ser múltiplo de $2015$. | + | Similarmente, una vez que tenemos elegidos $x$ e $y$, como la última ecuación se puede ver también como $2015 z = 448103 - 28x-10y$, tenemos que el número $448103 - 28x-10y$ tiene que ser múltiplo de $2015$. |
| Agregando estos dos if al código anterior: | Agregando estos dos if al código anterior: | ||
| Línea 106: | Línea 106: | ||
| </code> | </code> | ||
| - | Al momento de escribir esto, este código funciona exactamente igual que el de fuerza bruta anteriormente dado, pero se ejecutó en solamente 4 décimas de segundo. Es posible mejorarlo aún más, notando que de hecho en el último paso no hace falta recorrer todas las opciones de $z$, pues de la ecuación surge que tiene que ser $z = \frac{448103 - 28x-10y}{2015}$. Esto borra un for, dejando solamente dos! | + | Al momento de escribir esto, este código funciona exactamente igual que el de fuerza bruta anteriormente dado, pero se ejecutó en solamente 4 décimas de segundo (en lugar de 150 segundos). Es posible mejorarlo aún más, notando que de hecho en el último paso no hace falta recorrer todas las opciones de $z$, pues de la ecuación surge que tiene que ser $z = \frac{448103 - 28x-10y}{2015}$. Esto borra un for, dejando solamente dos! |
| <code cpp> | <code cpp> | ||
| Línea 121: | Línea 121: | ||
| { | { | ||
| long long z = (448103 - 28 * x - 10 * y) / 2015; | long long z = (448103 - 28 * x - 10 * y) / 2015; | ||
| - | if (x*x + y*y == z*z && 28*x+10*y+2015*z == 448103) | + | if (x*x + y*y == z*z) |
| cout << x << " " << y << " " << z << endl; | cout << x << " " << y << " " << z << endl; | ||
| } | } | ||
| Línea 151: | Línea 151: | ||
| </code> | </code> | ||
| - | En este caso, el algoritmo tardo 4.5 segundos, ¡una gran diferencia! Si agregamos como antes la idea de despejar la ultima variable, en lugar de iterarla: | + | En este caso, el algoritmo tardó 4.5 segundos, ¡una gran diferencia! Si agregamos como antes la idea de despejar la ultima variable, en lugar de iterarla: |
| <code cpp> | <code cpp> | ||
| Línea 166: | Línea 166: | ||
| { | { | ||
| long long x = (448103 - 2015 * z - 10 * y) / 28; | long long x = (448103 - 2015 * z - 10 * y) / 28; | ||
| - | if (x*x + y*y == z*z && 28*x+10*y+2015*z == 448103) | + | if (x*x + y*y == z*z) |
| cout << x << " " << y << " " << z << endl; | cout << x << " " << y << " " << z << endl; | ||
| } | } | ||
| Línea 199: | Línea 199: | ||
| Tiene el esquema "for if for if for if for if" (aunque es habitual cambiar los for por recursión en la implementación, cuando no está prefijado de antemano cuántos for se necesitarán). | Tiene el esquema "for if for if for if for if" (aunque es habitual cambiar los for por recursión en la implementación, cuando no está prefijado de antemano cuántos for se necesitarán). | ||
| - | Ventaja: Es **mucho** más eficiente que fuerza bruta (un buen backtracking en la mayoría de los casos disminuye mucho la complejidad asintótica del algoritmo resultante comparado a un algoritmo similar de fuerza bruta; es decir, reduce el tiempo en más que un factor constante). | + | Ventaja: Es **mucho** más eficiente que fuerza bruta. Un buen backtracking en la mayoría de los casos disminuye mucho la complejidad asintótica del algoritmo resultante comparado a un algoritmo similar de fuerza bruta; es decir, reduce el tiempo en más que un factor constante (habitualmente elimina por completo el costo del chequeo de cada solución, ya que al repartirse el chequeo entre todas las etapas de construcción, queda absorbido en la misma complejidad de generar los candidatos). |
| - | Desventaja: Es claramente más difícil de programar que fuerza bruta. Adicionalmente al planteo de candidatos que hay que hacer para fuerza bruta, es necesario determinar también un proceso de construcción de solución en etapas: elegir el orden y las etapas que se utilizarán es algo que puede realizarse de muchas maneras posibles, y no siempre es fácil saber cuál es la más eficiente a priori sin estudiar cada problema en particular. | + | Desventaja: Es claramente más difícil de programar que fuerza bruta. Adicionalmente al planteo de candidatos que hay que hacer para fuerza bruta, es necesario determinar también un proceso de construcción de solución en etapas: elegir el orden y las etapas que se utilizarán es algo que puede realizarse de muchas maneras posibles, y no siempre es fácil saber cuál es la más eficiente a priori sin estudiar cada problema en particular y pensar las podas viables. A veces puede calcularse y predecirse de antemano la reducción de complejidad por las podas realizadas, pero muchas veces es necesario experimentar para ver los resultados. |
| + | ===== Adicional ===== | ||
| + | |||
| + | FIXME Tener link a Branch and Bound en la wiki! | ||
| + | |||
| + | * https://es.wikipedia.org/wiki/Ramificaci%C3%B3n_y_poda | ||
| + | * https://en.wikipedia.org/wiki/Branch_and_bound | ||
algoritmos-oia/backtracking.1588219289.txt.gz · Última modificación: 2020/04/30 04:01 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
