Aplicar el algoritmo del árbol de mínima expansión como herramienta para determinar la mejor ruta que se debe seguir en una visita a los museos del casco viejo en la ciudad de La Paz

Aplicar el algoritmo del árbol de mínima expansión como herramienta para determinar la mejor ruta que se debe seguir en una visita a los museos del casco viejo en la ciudad de La Paz

1. Resumen

La palpable dificultad de tomar decisiones ha hecho que el hombre busque herramientas o métodos que se lo permitan en el menor tiempo posible, minimizando de esta manera los factores de riesgo. Tales herramientas que dan consistencia para la aplicación de la toma de decisiones se encuentra en los modelos matemáticos de investigación operativa en redes, de la cual estudiaremos el árbol de mínima expansión para determinar la mejor ruta en una visita a los museos del casco viejo de la ciudad de La Paz.

2. Abstract

The palpable difficulty of making decisions has made man look for tools or methods that allow it in the shortest possible time, thus minimizing the risk factors. Such tools that give consistency for the application of decision making are found in the mathematical models of operational research in networks, of which we will study the tree of minimum expansion to determine the best route in a visit to the museums of the old quarter of the city La Paz.

3. Palabras clave

Investigación operativa en redes, árbol de mínima expansión.

4. Key words

Operational research in networks, minimum expansion tree.

5. Introducción

El ser humano siempre ha buscado la forma de minimizar su esfuerzo y poder ahorrar tiempo o dinero en la realización de las diferentes actividades que realiza durante toda su vida. En este sentido la investigación operativa nos presenta una serie de herramientas las cuales nos ayudan a tomar decisiones adecuadas a problemas puntuales del que hacer cotidiano y también en el ámbito laboral. Una vez definido el problema se debe formular un modelo matemático de acuerdo a las variables localizadas de cada problema, diseñando para esto ecuaciones que permitan ver el panorama general del problema. Un modelo siempre debe ser menos complejo que el problema real, es una aproximación abstracta de la realidad con consideraciones y simplificaciones que hacen más manejable el problema y permiten evaluar eficientemente las alternativas de solución.

6. Antecedentes

Título: Trabajo fin de máster “Programación en R de problemas de búsqueda de árboles óptimos”

Autor : Manuel Fontela Cadavid

Universidad Santiago de Compostela  

Resumen

 Cuando navegamos por internet, al consultar una ruta en el navegador GPS, al buscar billetes de avión, incluso al abrir un grifo o encender una simple bombilla. En todos esos actos cotidianos interviene, de una u otra forma, la teoría de grafos y la determinación de árboles óptimos.

Convertidos en estructuras fundamentales para el día a día de individuos, organizaciones y empresas; su extensa repercusión e anuencia es un gran aliciente para el estudio de los problemas que permiten determinar caminos y rutas óptimas entre los nodos y arcos de un grafo. Los orígenes de la teoría de grafos se remontan a 1736, año en el que Leonhard Euler público su afamado trabajo sobre los siete puentes de Konigsberg. Con su obra presento los antecedentes de toda una rama de conocimiento que carecería de nombre hasta la aparición del término \grafo" en la segunda mitad del siglo XIX. Su primer uso en un sentido similar al actual data de 1878, en un artículo publicado en la revista Nature. Unos años antes, otro término relacionado había irrumpido en los círculos académicos inaugurando uno de los apartados de mayor desarrollo dentro del propio ámbito de la teoría de grafos: el de los _arboles.

El concepto de árbol, entendido como un grafo conectado sin ciclos, se presentó en sociedad de la mano de Gustav Kirchho, en cuyos trabajos sobre corrientes en circuitos eléctricos aparecía de forma implícita. Conceptos similares eran también recurso habitual en el campo de la química molecular con los escritos de James Joseph Sylvester o de Arthur Cayley. Es precisamente a este último al que se le atribuye el mérito de acuñar el termino árbol". Un término cuyo uso permaneció inicialmente vinculado a los campos que lo vieron nacer, no siendo hasta bien entrado el siglo XX cuando su utilidad empezaría a multiplicarse, dando píe, entre otros, al inicio de los problemas de búsqueda de árboles óptimos que aquí nos ocupan.

Durante los últimos 50 años la teoría de grafos ha experimentado su mayor crecimiento. Ello es debido, en buena medida, al impulso ejercido por el desarrollo de las modernas redes de transportes y telecomunicaciones. Es justo en ese sector en donde destacan estructuras como los árboles, dada su utilidad para el estudio de estas u otras redes, como pueden ser redes eléctricas, de suministros o de distribución. No sólo eso, sus aplicaciones en la vida real se extienden por numerosos ámbitos y su uso también es recurso habitual a modo de subrutina de otros algoritmos, conformando uno de los campos más estudiados en teoría computacional. De todo lo anterior da buena fe la vasta literatura existente y el hecho de que sus algoritmos han sido programados en multitud de lenguajes, existiendo herramientas y utilidades para mostrar su funcionamiento. A pesar de ello, existe un vacío importante en uno de los lenguajes de programación que ha ganado más popularidad en los _últimos años: R. Aunque está orientado principalmente a la Estadística, R cuenta con varias librerías relacionadas con el _área de la investigación operativa, algunas de ellas centradas precisamente en el estudio de redes y grafos. De lo que todavía carece es de un paquete común sobre árboles y arborescencias y los problemas relacionados con la búsqueda de los mismos.

Título: Selección de rutas en una red de sensor inalámbrica, en base al nivel de batería y distancia entre nodos sensores mediante la utilización del algoritmo de Kruskal.

Autor: Ing. Mesias Basurto Diana Carolina

Pontificia universidad católica del Ecuador.

Facultad de ingeniería.

Resumen

En los años 90, las redes han revolucionado la forma en la que las personas y las organizaciones intercambian información y coordinan sus actividades”. (Sanchis, 2007). Los sistemas de monitoreo inalámbricos de bajo costo han adquirido gran importancia actualmente, esto gracias a los avances tecnológicos en modulación digital y a las necesidades de la industria en la adquisición de datos en línea, por estos motivos se han desarrollado sistemas de sensores cada vez más económicos, de bajo consumo energético, y se pueden instalar, controlar y monitorear de manera remota.

...