Algoritmos voraces

Algoritmo Voraz

Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurística consistente en elegir la opciónóptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento.Normalmente se aplica a los problemas de optimización.

Grafos
Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), queconsiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del conceptomatemático de grafo.
Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas. Formalmente, un grafo, G, se define como un par ordenado, G = (V, E),donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.

Recorrido de un grafo.

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionadoscon uno que llamaremos nodo de salida.    Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.

• Recorrido en anchura:    El recorrido enanchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, yasí sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.

• Recorrido en profundidad:el recorrido en profundidad trata de buscar los caminos que partendesde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron...