La estrategia de los algoritmos de vuelta atrás consiste en recorrer el espacio completo de soluciones de un problema dado y se suele utilizar cuando no existe ningún otro algoritmo más eficiente que pueda aplicarse. Aunque se trata de recorrer el espacio completo de soluciones, se puede optimizar aplicando una poda a aquellas ramas que sabemos de antemano que no conducen a una solución.
El procedimiento es el siguiente:
A continuación se muestran algunos ejemplos. Puedes acceder a ellos desde el menú de la parte superior.
Este problema consiste en encontrar todos los ciclos hamiltonianos de un grafo. Un ciclo hamiltoniano es aquel camino que pasa por cada nodo exactamente una vez y termina en el nodo inicial.
Si cada arista tuviese un valor que representa la distancia entre los nodos y buscásemos el ciclo hamiltoniano de longitud mínima, estaríamos ante el problema del viajante de comercio (PVC).
Este problema consiste en asignar un color de un conjunto de M colores a cada vértice de un grafo, de forma que no haya dos vértices adyacentes con el mismo color. Se sabe que cuatro colores son suficientes para colorear cualquier grafo, pero en ocasiones necesitaremos menos colores.
Si cada vértice representase un pais y las aristas representasen las fronteras entre países, tendríamos un problema de coloreado de mapas.
Este problema consiste en disolver una sociedad comercial compuesta por \(n\) activos y 2 socios. El conjunto de activos debe repartirse a medias. Por lo tanto, habrá que estudiar todas las formas posibles de dividir el conjunto de activos en dos subconjuntos disjuntos de forma que los dos subconjuntos tengan el mismo valor.
Este término de origen japonés define un juego mental muy popular de pensamiento lógico, razonamiento y paciencia. Existen sudokus de todos los niveles de dificultad. El juego consiste en rellenar las casillas con números del 1 al 9, de forma que no se repita el mismo número en la fila, columna y región de 3x3 a la que pertenece la casilla. Se estima que podría haber más de 5000 millones de combinaciones posibles.