Dise1o de Algoritmos

Apuntes

Diseño de Algoritmos Tema 6: Backtracking Grau d’Enginyeria de Dades Curso 2022 - 2023 ¿Qué es el backtracking ? En juegos de los llamados Metroidvania (por ejemplo, Hollow Knight ) el backtracking está muy ligado a la navegación en el mapa . No se puede ir al abismo (The Abyss ) hasta que no tienes una habilidad determinada . 2 Definición backtracking • Dentro del concepto de búsqueda de mejor solución partiendo de un grafo/árbol, la esencia del backtracking es encontrar la mejor combinación posible en un momento determinado, por eso, se dice que este tipo de algoritmo es una búsqueda en profundidad . • Durante la búsqueda, si se encuentra una alternativa incorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa . 3 Definición backtracking • Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción . • Si no hay más alternativas la búsqueda falla . De esta manera...