algoritmos devoradores

República Bolivariana de Venezuela
Instituto Universitario Politécnico “Santiago Mariño”
Escuela de Ingeniería de Sistemas
Extensión MaturínProfesora:
María Aguilera
Asignatura:
Programación No Numérica II





Autor:
Carlos Bermúdez


Algoritmos devoradores.
Es una serie de pasos que se repiten con la intención de irutilizando la mayor cantidad de datos por vez cumpliendo con las condiciones para así resolver el problema.
Generalmente el desarrollo de esta clase de algoritmos no es difícil, solo hay que estar seguro deque es adecuado para el problema que queremos resolver, este tipo de algoritmos es muy utilizado en los problemas de optimización, problemas en los cuales se tiene un conjunto de candidatos (datos deentrada), de los cuales se debe elegir un subconjunto que satisfaga una cierta condición de optimalidad (posibles soluciones no necesariamente optimas) y eventualmente condiciones de factibilidad.Árbol de expansión mínimo (algoritmo de Prim).

Es un algoritmo usado para resolver problemas gráficos como lo podría ser la planificación de redes de carreteras en los que se necesiteinterconexión entre ciudades con el mínimo de longitud entre estas. Se selecciona el tramo de menor costo así sucesivamente hasta completar una red que conecte con todas las ciudades, donde cada nuevo tramo es demenor longitud.

Algoritmo Dijkstra.

Conocido como algoritmo de caminos mínimos, determina el camino más corto de un de un arista (segmento de origen) al resto de aristas (segmentos en elgrafo) determinando el valor de cada segmento que los une.

Algoritmo

Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al finaldel algoritmo las distancias desde x al resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se...