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

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

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 sigui...

Descripción completa

Detalles Bibliográficos
Autores principales: Granera, Julia Argentina, Valdivia, Victor Manuel, Blandón Dávila, Maria Elena
Formato: Online
Idioma:spa
Publicado: Centro Universitario Regional de Estelí. UNAN-Managua/CUR-Estelí 2016
Acceso en línea:https://revistas.unan.edu.ni/index.php/Cientifica/article/view/2919
id CIESTELI2919
record_format ojs
spelling CIESTELI29192024-02-13T15:02:20Z KPTS computer application ( Kruskal , Prim , Tabu Search) Aplicación informática KPTS (Kruskal, Prim, Tabu Search) Granera, Julia Argentina Valdivia, Victor Manuel Blandón Dávila, Maria Elena This article describes the application of a software tool based on graph theory to analyze and solve problems of the shortest routes, using the algorithms of Prim, Kruskal and Tabu. For the development of this application the following elements were used: Visual Studio 2010, GraphSharp and QuickGraph. TO create this tool, a class structure that would support the graphics was established:1) PocGraph : represents the graph ; 2) PocEdge: represents the edges of the graph ; and 3 ) PocVertex : represents the nodes or vertices of the graph. The Prim algorithm worked with the aim of finding the shortest spanning tree; while Kruskal’s algorithm , in order to find the minimal tree from TSP instances . Tabu Search method is applied to find the minimum closed road connecting all the vertices or nodes. The Tabu Search algorithm was designed to minimize the routes from an initial solution which is modified to obtain the result.Keywords: Prim algorithm, Kruskal algorithm, Tabu Search Algorithm, Computer tool. 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.     Palabras claves: Algoritmo de Prim, Algoritmo de  Kruskal, Algoritmo de Tabú Search, Herramienta informática. Centro Universitario Regional de Estelí. UNAN-Managua/CUR-Estelí 2016-04-19 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Artículo revisado por pares application/pdf https://revistas.unan.edu.ni/index.php/Cientifica/article/view/2919 Revista Científica Estelí; No. 17 (2016); 81-90 Revista Científica Estelí; Núm. 17 (2016); 81-90 spa https://revistas.unan.edu.ni/index.php/Cientifica/article/view/2919/4365 Derechos de autor 2016 Revista Científica FAREM - Estelí
institution Universidad Nacional Autónoma de Nicaragua, UNAN-Managua
collection Revista Científica Estelí
language spa
format Online
author Granera, Julia Argentina
Valdivia, Victor Manuel
Blandón Dávila, Maria Elena
spellingShingle Granera, Julia Argentina
Valdivia, Victor Manuel
Blandón Dávila, Maria Elena
Aplicación informática KPTS (Kruskal, Prim, Tabu Search)
author_facet Granera, Julia Argentina
Valdivia, Victor Manuel
Blandón Dávila, Maria Elena
author_sort Granera, Julia Argentina
description 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.     Palabras claves: Algoritmo de Prim, Algoritmo de  Kruskal, Algoritmo de Tabú Search, Herramienta informática.
title Aplicación informática KPTS (Kruskal, Prim, Tabu Search)
title_short Aplicación informática KPTS (Kruskal, Prim, Tabu Search)
title_full Aplicación informática KPTS (Kruskal, Prim, Tabu Search)
title_fullStr Aplicación informática KPTS (Kruskal, Prim, Tabu Search)
title_full_unstemmed Aplicación informática KPTS (Kruskal, Prim, Tabu Search)
title_sort aplicación informática kpts (kruskal, prim, tabu search)
title_alt KPTS computer application ( Kruskal , Prim , Tabu Search)
publisher Centro Universitario Regional de Estelí. UNAN-Managua/CUR-Estelí
publishDate 2016
url https://revistas.unan.edu.ni/index.php/Cientifica/article/view/2919
work_keys_str_mv AT granerajuliaargentina kptscomputerapplicationkruskalprimtabusearch
AT valdiviavictormanuel kptscomputerapplicationkruskalprimtabusearch
AT blandondavilamariaelena kptscomputerapplicationkruskalprimtabusearch
AT granerajuliaargentina aplicacioninformaticakptskruskalprimtabusearch
AT valdiviavictormanuel aplicacioninformaticakptskruskalprimtabusearch
AT blandondavilamariaelena aplicacioninformaticakptskruskalprimtabusearch
_version_ 1805407310519992320

Ejemplares similares