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 | |||
|
algoritmos-oia:backtracking [2020/05/01 14:25] santo |
algoritmos-oia:backtracking [2020/05/01 14:26] (actual) santo [Técnica de backtracking:] |
||
|---|---|---|---|
| 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, ya que al repartirse el chequeo entre todas las etapas de construcción, 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 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. | 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. | ||
algoritmos-oia/backtracking.1588343141.txt.gz · Última modificación: 2020/05/01 14:25 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
