• RSS
  • Delicious
  • Digg
  • Facebook
  • Twitter
  • Linkedin

Algoritmos Backtracking

Publicado por Ingeniero Sistemas 12 agosto 2011

Esta vez publicaré un archivo en el cual vienen 11 problemas de los cuales se busca crear sus algoritmos por medio de la técnica Backtracking.

El Proyecto Final de la materia Análisis y Diseño de Algoritmos consistió en escoger uno de esos 11 problemas y realizar el algoritmo con la técnica de Backtracking en lenguaje Java.

Esto les puede servir para practicar, les dejo los 11 problemas:

Construya algoritmos por la técnica Backtracking para los siguientes problemas:

1. Dado un sistema de rutas aéreas modelado mediante un grafo, determine la ruta que contenga la mínima cantidad de escalas entre un par de ciudades dadas.
2. N reinas. Construir un algoritmo que ubique n reinas en un tablero de ajedrez de nxn de modo tal que no se puedan capturar entre sí.
3. Suma de subconjuntos. Dados n números positivos distintos, se desea encontrar todas las combinaciones de esos números tal que la suma sea M.
4. Partición de conjunto. Dado un conjunto de n enteros se desea encontrar, si existe, una partición en dos subconjuntos disjuntos, tal que la suma de sus elementos sea la misma.
5. Dada una pirámide de números naturales, partiendo desde el tope de la pirámide, encontrar el camino que maximice la sumatoria hasta la base. La sumatoria deberá realizarse considerando solamente los números sobre los que se “apoya” el número de la fila anterior.

Piramide
6. Colocar un entero positivo (menor que 100) en cada casilla de una pirámide de modo que cada número sea igual a la suma de las casillas sobre las que está apoyado. Los números de todas las casillas deben ser diferentes.
7. Caballo de Atila. Todos sabemos que por donde pisa el caballo de Atila jamás vuelve a crecer el pasto. El caballo fue directamente hacia el jardín de n x n casillas. Empezó su paseo por una casilla cualquiera y volvió a ella, es decir hizo un recorrido cerrado. No visitó dos veces una misma casilla, se movió de una casilla a otra vecina en forma horizontal o vertical, pero nunca en diagonal. Por donde pisó el caballo, el pasto jamás volvió a crecer. Luego de terminado el recorrido en algunas casillas todavía había pasto (señal de que en ellas no había estado el caballo). Escriba un algoritmo que deduzca el recorrido completo que hizo el caballo.
8. Tablero mágico. Dado un tablero de tamaño n x n, construir un algoritmo que ubique (si es posible) n x n números naturales diferentes, entre 1 y un cierto k, de manera tal que la suma de las columnas y de las filas sea S.
9. Juego de los fósforos. Se disponen de 11 fósforos. Dos jugadores pueden retirar por turno 1, 2 o 3 fósforos. Pierde aquel jugador que retira el último fósforo. Construir un algoritmo que determine para un jugador si existe una secuencia de jugadas ganadora.
10. Pilas de monedas. Dada una pila de n monedas, y 2 jugadores, quienes alternan movimientos, cada uno de ellos puede dividir una pila en otras 2, siempre y cuando haya más de 2 monedas. Pierde el jugador que no puede dividir ninguna pila. Construir un algoritmo que determine para un jugador si existe una secuencia de jugadas ganadora.
11. Dado un tablero de 4 x 4, en cuyas casillas se encuentran desordenados los números enteros del 1 al 15 y una casilla desocupada en cualquier posición, determinar una secuencia de pasos tal que los números en el tablero queden ordenados (como muestra la figura) y la casilla desocupada quede en la
posición 4,4.

tablero

Pueden descargar el archivo del siguiente enlace:

 

Espero que les sirva ;)