Informe








LABORATORIO
ALGORITMOS AVANZADOS
BACKTRACKING

SEBASTIÁN CALDERÓN DÍAZ




Profesora: Mónica Villanueva
Ayudantes: Alex Ahumada
Cristian Cornejo






















Tabla de Contenidos
CAPÍTULO 1: INTRODUCCIÓN 3
1.1 DESCRIPCIÓN DEL PROBLEMA 3
1.2 SOLUCIÓN PROPUESTA 3
1.3 OBJETIVOS 4
1.4 METODOLOGÍAS Y HERRAMIENTAS 4
CAPÍTULO 2: ANÁLISIS DEL ENUNCIADO 5
CAPÍTULO 3: DESARROLLO DEL TEMA6
3.1 FUNDAMENTOS TEÓRICOS 6
3.2 EXPLICACIÓN DE LA SOLUCIÓN 6
CAPÍTULO 4: ALGORITMO 9
4.1 MÉTODO MAIN 9
4.2 MÉTODO INICIO 10
4.3 MÉTODO MAYOR 11
4.5 MÉTODO BACKTRACKING 11
CAPÍTULO 5: TRAZA 13
CAPÍTULO 6: ANÁLISIS DE COMPLEJIDAD DEL ALGORITMO 18
6.1 MÉTODO BACKTRACKING 18
6.2 MÉTODO INICIO 19
6.3 MÉTODO MAIN 19
CAPÍTULO 7: ANÁLISIS DE RESULTADOS 21
CAPÍTULO 8: CONCLUSIONES 22
CAPÍTULO 9:REFERENCIAS 23
CAPÍTULO 10: ANEXOS 24
10.1 COMPILACIÓN Y EJECUCIÓN 24

CAPÍTULO 1: INTRODUCCIÓN
En el siguiente informe se da a conocer la implementación de backtracking en el problema planteado para laboratorio de algoritmos avanzados.
El problema a resolver surge en un contexto en el cual un grupo de personas quiere hacer un viaje, pero no sin planearlo con anterioridad. El desarrollo de este problemapuede resultar aplicable a un sinfín de actividades en las cuales se requiera determinar la mejor solución entre muchas, donde todas son válidas. Para esto surge el llamado backtracking, algoritmo que se encarga de realizar esta tarea.
1.1 DESCRIPCIÓN DEL PROBLEMA
El problema consiste en un viaje que debe ser hecho pasando por un número definido de campings y en un número limitado de días. Se debeencontrar la combinación en la que su distancia más larga sea las más corta en comparación con la más larga de las demás combinaciones. La entrada será un archivo con la cantidad de campings, número de noches y la distancia que hay entre el inicio y el primer camping, entre cada camping y entre el último y el final del trayecto.
1.2 SOLUCIÓN PROPUESTA
Como solución a este problema se creó unaclase para guardar todos los datos necesarios para poder obtener la distancia buscada. La clase contiene un arreglo, en el que se guardan las distancias obtenidas en la entrada, las noches y los campings, que también se obtienen de esta forma. Contiene, también, una variable para guardar la solución final entre otras que serán explicadas posteriormente. Luego se procede a buscar las condiciones deborde del algoritmo de backtracking que se debe utilizar, tomando en cuenta cuantas distancias deben ser juntadas para no sobrepasar las noches de campamento fijadas.
1.3 OBJETIVOS
Los objetivos de este laboratorio son la correcta implementación del algoritmo de backtracking y su comprensión.
1.4 METODOLOGÍAS Y HERRAMIENTAS
Para la implementación se utilizó el lenguaje java con el IDE NetBeans.CAPÍTULO 2: ANÁLISIS DEL ENUNCIADO

El enunciado muestra a un grupo de personas que quiere hacer un viaje a través de un sendero. El grupo considera que planear el viaje también es parte de la experiencia por lo que tiene en una lista todos los campings posibles que pueden utilizar, considerando K noches de campamento. Se establece como restricción que solo puede acampar una vez pornoche y se conocen todas las distancias entre campings consecutivos, desde el punto inicial al primero y del último al punto final.
Si se tiene 2 noches de campamento, que es lo equivalente a 3 días de caminata, se puede tener respectivamente 10,6 y 7, de donde 10 es el mayor, pero como las distancias dependen del numero de campamentos también, se puede tener 9, 8 y 7, y en esta nueva opción el mayores 9, como es menor que 10, este primer valor es solución a un ejemplo con estos dos caminos como únicos.
Se pide entonces que, dadas las distancias entre los N campamentos existentes y las noches que se tienen consideradas para acampar, se desarrolle una estrategia para poder encontrar este número, que es la distancia mínima entre todas las máximas de los caminos posibles.
La entrada puede...