ALGORITMOS VORACES PDF

Dacage References Publications referenced by this paper. Topics Discussed in This Paper. Who is online Users browsing this forum: Knapsack problem Search for additional papers on this topic. PDF con un informe.

Author:	Doudal Kazijar
Country:	Azerbaijan
Language:	English (Spanish)
Genre:	Politics
Published (Last):	4 December 2019
Pages:	397
PDF File Size:	16.43 Mb
ePub File Size:	14.79 Mb
ISBN:	121-7-29673-475-5
Downloads:	81546
Price:	Free* [*Free Regsitration Required]
Uploader:	Voodoozil

Docente:Carlos A. El problema se interpreta como: tomar algunos elementos de entre un conjunto de candidatos. El orden en que se cogen puede ser importante o no. Un algoritmo voraz funciona por pasos: Inicialmente partimos de una solucin vaca. En cada paso se escoge el siguiente elemento para aadir a la solucin, entre los candidatos. Una vez tomada esta decisin no se podr deshacer.

El algoritmo acabar cuando el conjunto de elementos seleccionados constituya una solucin. Se puede generalizar el proceso intuitivo a un esquema algortmico general. El esquema trabaja con los siguientes conjuntos de elementos: C: Conjunto de elementos candidatos, pendientes de seleccionar inicialmente todos. S: Candidatos seleccionados para la solucin.

R: Candidatos seleccionados pero rechazados despus. Cul o cules son los candidatos? Depende de cada problema. Comprueba si un conjunto de candidatos es una solucin independientemente de que sea ptima o no. Devuelve el elemento ms prometedor del conjunto de candidatos pendientes no seleccionados ni rechazados. Indica si a partir del conjunto S y aadiendo x, es posible construir una solucin posiblemente aadiendo otros elementos. Aade el elemento x al conjunto solucin.

Adems, puede ser necesario hacer otras cosas. Funcin objetivo S. Dada una solucin devuelve el coste asociado a la misma resultado del problema de optimizacin. Ejemplo 1. Algoritmo de Dijkstra: Conjunto. Funcin de seleccin: escoger el nodo candidato con camino especial ms corto. Funcin factible: recalcular los caminos especiales. Solucin: cuando se acaben los candidatos. Algoritmo de caminos mnimos Ejemplo 2.

Algoritmo de Kruskal: Conjunto. Funcin de seleccin: escoger la arista con menor costo. Funcin factible: que no forme un ciclo en la solucin actual. Construir un algoritmo que dada una cantidad P devuelva esa cantidad usando el menor nmero posible de monedas.

Caso 1. Devolver Soles. Total: 8 monedas. Caso 2. El mtodo intuitivo se puede entender como un algoritmo voraz: en cada paso aadir una moneda nueva a la solucin actual, hasta llegar a P. Conjunto de candidatos: Todos los tipos de monedas disponibles. Supondremos una cantidad ilimitada de cada tipo. Solucin: conjunto de monedas que sumen P. Funcin objetivo: Minimizar el nmero de monedas. Representacin de la solucin: x1, x2, x3, x4, x5, x6, x7, x8 , donde xi es el nmero de monedas usadas de tipo i.

Suponemos que la moneda i vale ci. Formulacin: minimizar x.