Algoritmo Vecino Mas Cercano
Páginas: 2 (430 palabras)
Publicado: 11 de octubre de 2015
Universidad Nacional Autónoma de Nicaragua
UNAN – Managua
Recinto Universitario “Rubén Darío”
Facultad de Ciencias e Ingenierías
Departamento de Computación
Aplicaciones De Grafos
“AlgoritmoDel Vecino Más Cercano”
Asignatura:
Algoritmos y Estructuras de Datos II
Profesora:
Msc. Amparo Herrera.
Autor:
Br. Carlos Javier Reyes Espinoza.
Lunes, 28 de septiembre de 2015.Índice
Pág.
I. Teoría ………………………………………………………………. 1
II. Aplicaciones en la vida real ………………………………. 2
III. Bibliografía ………………………………………………………. 3
Teoría
El algoritmo del vecino más cercano es, en lasciencias de la computación, uno de los primeros algoritmos utilizados para determinar la ruta más corta en el recorrido de un punto a otro, aunque generalmente no es el ideal para resolver este tipo deproblemas. La idea de este algoritmo consiste en que, una vez seleccionado un vértice del grafo, se toma la arista de menor peso conectada al vértice actual y a otro vértice del grafo.
Estos son lospasos del algoritmo:
1. Elección de un vértice arbitrario respecto al vértice actual.
2. Descubrir la arista de menor peso que ya esté conectada al vértice actual y a un vértice no visitado.
3.Convertir el vértice actual en V.
4. Marcar V como visitado.
5. Si todos los vértices del dominio estuvieran visitados, cierre el algoritmo.
6. Volver al paso 2.
La resolución obliga a tomar un vérticeinicial, examinar todos los otros vértices y todas las aristas del grafo, tomando en cuenta que el vértice siguiente a visitar tiene que ser el más próximo tomando la arista más corta, y asísucesivamente hasta llegar al punto final del recorrido.
La secuencia de los vértices visitados es la salida del algoritmo.
Aplicaciones en la vida real
El algoritmo del vecino más cercano, se puedeimplementar para generar trayectos, en los cuales podemos obtener el camino más corto para desplazarse de un lugar a otro, el ejemplo más práctico es el problema del viajante, que desea recorrer todas las...
UNAN – Managua
Recinto Universitario “Rubén Darío”
Facultad de Ciencias e Ingenierías
Departamento de Computación
Aplicaciones De Grafos
“AlgoritmoDel Vecino Más Cercano”
Asignatura:
Algoritmos y Estructuras de Datos II
Profesora:
Msc. Amparo Herrera.
Autor:
Br. Carlos Javier Reyes Espinoza.
Lunes, 28 de septiembre de 2015.Índice
Pág.
I. Teoría ………………………………………………………………. 1
II. Aplicaciones en la vida real ………………………………. 2
III. Bibliografía ………………………………………………………. 3
Teoría
El algoritmo del vecino más cercano es, en lasciencias de la computación, uno de los primeros algoritmos utilizados para determinar la ruta más corta en el recorrido de un punto a otro, aunque generalmente no es el ideal para resolver este tipo deproblemas. La idea de este algoritmo consiste en que, una vez seleccionado un vértice del grafo, se toma la arista de menor peso conectada al vértice actual y a otro vértice del grafo.
Estos son lospasos del algoritmo:
1. Elección de un vértice arbitrario respecto al vértice actual.
2. Descubrir la arista de menor peso que ya esté conectada al vértice actual y a un vértice no visitado.
3.Convertir el vértice actual en V.
4. Marcar V como visitado.
5. Si todos los vértices del dominio estuvieran visitados, cierre el algoritmo.
6. Volver al paso 2.
La resolución obliga a tomar un vérticeinicial, examinar todos los otros vértices y todas las aristas del grafo, tomando en cuenta que el vértice siguiente a visitar tiene que ser el más próximo tomando la arista más corta, y asísucesivamente hasta llegar al punto final del recorrido.
La secuencia de los vértices visitados es la salida del algoritmo.
Aplicaciones en la vida real
El algoritmo del vecino más cercano, se puedeimplementar para generar trayectos, en los cuales podemos obtener el camino más corto para desplazarse de un lugar a otro, el ejemplo más práctico es el problema del viajante, que desea recorrer todas las...
Leer documento completo
Regístrate para leer el documento completo.