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:09] santo [Técnica de backtracking:] |
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 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 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 (habitualmente elimina el costo del chequeo de cada solución, que al repartirse entre todos los nodos, queda absorbido en la misma complejidad de generar los candidatos). | + | 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.1588219778.txt.gz · Última modificación: 2020/04/30 04:09 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
