Jiménez, AndreaZamora Canales, Aline Valentina2026-04-162026-04-162025-08-12https://repositoriobibliotecas.uv.cl/handle/uvscl/17216En este trabajo se estudia el Problema de Localización Dinámica (PLD) en grafos, formulado por Chung, Graham y Saks [CGS89] en el año 1989. El Problema de Localización Dinámica es un problema de optimización combinatoria enmarcado dentro de las matemáticas discretas, que tiene como sistema un grafo G = (V,E) en donde una fuente ubicada en una cierta posici´on inicial en alg ´un v´ ertice de G, tiene la habilidad de desplazarse con el objetivo de resolver secuencialmente una lista de requerimientos ubicados en los v´ ertices del grafo minimizando el costo de desplazarse y resolverlos. Estudiamos dos escenarios: el Off-line, en donde la lista de requerimientos por resolver está totalmente disponible desde un inicio, y el On-line, en donde la lista de requerimientos por resolver se va revelando progresivamente y cada desplazamiento de la fuente se debe decidir con información parcial del futuro. En el contexto Offline estudiamos propiedades estructurales fundamentales que describen el comportamiento del óptimo para el PLD y diseñamos un algoritmo óptimo, basado en el paradigma de diseño de algoritmos conocido como programación dinámica. Justificamos teóricamente la correctitud de este algoritmo y calculamos la complejidad temporal, resultando en O(n2k), en donde n es la cantidad de vértices del grafo del sistema, y k es la cantidad de requerimientos por resolver. Implementamos este algoritmo en el lenguaje de programaci´on Python para utilizarlo como referencia para comparar el desempeño de algoritmos On-line. En el caso On-line, siguiendo el trabajo de Chung, Graham y Saks [CGS87, CGS89], introducimos un parámetro en grafos llamado Window Index (Windex), que mide el menor valor de ventana k para el cual existe un algoritmo óptimo para el PLD en G que trabaje tan solo conociendo los siguientes k requerimientos por resolver, es decir, el Windex esencialmente mide que tanta información necesito conocer del futuro para asegurar la existencia de un algoritmo que encuentre soluciones óptimas. Estudiamos grafos con Windex finito e infinito a partir del cálculo del Windex de clases particulares de grafos. Por otro lado, analizamos la correctitud y complejidad computacional de dos algoritmos: Algoritmo Glotón (de ventana 1) que en su diseño se utiliza el paradigma codicioso y garantiza un radio de aproximación 2 para el PLD en cualquier grafo. Algoritmo Windex 2 (de ventana 2) que es óptimo para grafos de Windex 2, y sustenta su diseño en la Propiedad de Tripleta de Steiner Única (USTP). Basándonos en la caracterización de Chung, Graham y Saks [CGS87], probamos que los grafos con Windex 2 son exactamente los grafos medianos, lo que incluye estructuras como árboles, grillas cuadradas e hipercubos. Para finalizar, realizamos una parte experimental en donde evaluamos el desempeño del Algoritmo Glotón y del Algoritmo Windex 2 en diferentes grafos, sustentando nuestra elección en el Windex de los grafos seleccionados y variando la densidad de las aristas de los grafos. Las implementaciones de los algoritmos las desarrollamos en el lenguaje de programación Python. En el caso del Algoritmo Windex 2, nuestros resultados dan evidencia empırica para la conjetura hecha por Chung, Graham y Saks [CGS89] acerca de la existencia de un algoritmo con ventana 2 y radio de aproximación 3/2. Por otro lado, a partir de los experimentos realizados, podemos decir que el Algoritmo Windex 2 supera consistentemente al Algoritmo Glotón, especialmente en grafos con Windex 2 o grafos con alta densidad, y que la estructura y densidad del grafo tienen un impacto directo en el desempeño de los algoritmos.esAtribución-NoComercial-CompartirIgual 3.0 Chile (CC BY-NC-SA 3.0 CL)ALGORITMOSTEORIA DE GRAFOSCOMPLEJIDAD COMPUTACIONALTDPRE