Descripciones - Heineken97/PDC GitHub Wiki
Descripción detallada del (los) algoritmo(s) de solución desarrollado(s) (con su respectivo(s) diagrama(s)).
Descripción de los algoritmos implementados.
- Algoritmo Backtracking : Para la solucion en la funcion PDC-Todas se requiera el uso del algoritmo Backtracking para obtener todas las posibles soluciones, en este caso en particular para este problema se requeria que probara todos los caminos posibles desde una coordenada inicial especificada. En la solucion que ha sido planteada se logra implementar especificamente en la funcion 'getSteps', esta recibe una lista de movimientos, una lista de elementos recorridos y el tamaño de la matriz. Busca validar que el primer elemento de la lista de movimientos tenga mas posibles movimientos por recorrer, se llama recursivamante con los posibles movimientos a partir de esta coordenada, en cuanto la primera coordenada no tiene mas posibilidades de avance, se empieza a llamar recursivamente en busqueda de los posibles movimientos de los demas elementos de la lista. Siempre que se llama una nueva coordenada, esta se añade a la lista de movimientos ya recorridos, para lograr salir del ciclo es comprobar que el largo de la lista de movimientos es igual a la cantidad de elementos del tamaño de la matriz, lo cual implica que todos los elementos han sido recorridos.
- Algoritmo de Warnsdorff : Algoritmo que da solucion al problema del caballo, la regla de Warnsdorff es una heuristica que consiste en mover el caballo al cuadro a partir del cual tenga la menor cantidad de movimientos posibles o de menor grado, la heuristica original propone elegir de forma aleatoria entre dos posiciones con igual grado. Sin embargo, presenta errores en tableros de gran tamaño, para solucionar esto se plantea una especia de desempate propuesta hecha por Arn Roth, el cual dice que la condicion de desempate para posiciones con mismo grado se escoge el que se encuentre mas lejano al tablero a esto se le llama la distancia Euclidiana.