Aplicación informática KPTS (Kruskal, Prim, Tabu Search)

Granera, Julia Argentina and Valdivia, Victor Manuel and Blandón Dávila, Maria Elena (2016) Aplicación informática KPTS (Kruskal, Prim, Tabu Search). Revista Cientifica de FAREM-Esteli, 5 (17). pp. 81-90. ISSN 2305-5790

[img]
Preview
Text (Texto Completo)
243-905-1-PB.pdf

Download (1MB) | Preview
[img]
Preview
Image (Portada)
cover_issue_33_es_ES.jpg

Download (178kB) | Preview
[img]
Preview
Image
88x31_cc.png
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (1kB) | Preview
Official URL: http://www.farem.unan.edu.ni/revistas/index.php/RC...

Abstract

En este artículo se muestra la aplicación de una herramienta informática basada en teoría de grafos para analizar y resolver problemas de las rutas más cortas, utilizando los algoritmos de Prim, Kruskal y de búsqueda local de Tabú Search. Para el desarrollo de esta aplicación se utilizaron los siguientes elementos: Visual Studio 2010, librería GraphSharp y librería QuickGraph. Para la creación de esta herramienta, se estableció una estructura de clases que diera soporte a los gráficos: 1) PocGraph: representa el grafo; 2) PocEdge: representa las aristas del grafo; y 3) PocVertex: representa los nodos o vértices del grafo. Tanto el método de Kruskal como Prim generan un árbol mínimo recubridor del grafo, el cual consiste en un subgrafo del original. El algoritmo de Prim se trabajó con el objetivo de encontrar el árbol recubridor más corto; mientras que el algoritmo de Kruskal, con la finalidad de hallar el árbol minimal a partir de instancias TSP. El método de Tabú Search se aplica para encontrar el mínimo camino cerrado que une todos los vértices o nodos. Se diseñó el algoritmo de Tabú Search para minimizar las rutas partiendo de una solución inicial la cual se va modificando hasta obtener el resultado.

Item Type: Article
Uncontrolled Keywords: Algoritmo de Prim, Algoritmo de Kruskal, Algoritmo de Tabú Search, Herramienta informática.
Subjects: 500 Ciencias naturales y matemáticas > 510 Matemáticas > 519 Probalidades y matemática aplicada
Divisions: FACULTAD REGIONAL MULTIDISCIPLINARIA DE ESTELI > Revista Científica > La Revista Científica de la FAREM-Estelí: Medio Ambiente, Tecnología y Desarrollo Humano > Vol.5, Núm. 17 (2016)
Depositing User: Editor Datos
Date Deposited: 23 Oct 2017 14:15
Last Modified: 23 Oct 2017 14:15
URI: http://repositorio.unan.edu.ni/id/eprint/6474

Actions (login required)

View Item View Item
Estadisticas: Clic Aquí
Exportar: Clic Aquí