Repository files navigation

Repositorio sobre los algoritmos devoradores.Se presentará un esquema general, descripición,elementos que lo componen y ejemplos de uso. Para ello seha realizado un resumen y modificado las partes que he creido pertinentesdel temario dado en la asignatura"Diseño de Algoritmos " añadiendoy traduciendo los algoritmos del temario a códigopython.

• Conjunto de candidatos:candidates_set
• Conjunto de candidatos selecionados:candidates_selected_set
• Función solución: Comprueba si un conjunto de candidatosseleccionados es una solución válida. Represetada medianteis_solution()
• Función selección: Selecciona el candidato más prometedor del conjuntode candidatos. Representada mediante:select()
• Función de factibilidad: Comprueba que el conjunto de candidatos seleccionadosse puede expandir añadiendo un candidato seleccionado. Representada mediante:feasible()
• Función objetivo: Función que asocia un valor a una solución de nuestroalgoritmo devorador, y que queremos minimizar o maximizar (optimizar)según nuestro objetivo.
• Objetivo: Minimizar, maximizar.

• El candidato más prometedor, puede ser no único.
• Una vez elegido un candidato, nunca más vuelve a ser procesado.
• Puede que la solución no exista o no pueda ser encontrada.
• Aunque se encuentre una solución, puede que no sea la más óptima.
• Se emplean normalmente en problemas de optimización.

defgreedy(candidates_set):candidates_selected_set=Nonewhilenotis_solution(candidates_selected_set)andcandidates_set:candidate_selected=select(candidates_set)candidates_set.remove(candidate_selected)iffeasible(candidates_selected_set,candidate_selected):candidates_selected_set.append(candidate_selected)returncandidates_selected_set

"Dado un cojuntoO de objetos, cada uno con un valorv y un pesop, y una mochila con una capacidadc, que limita el peso total que puede transportar,se desea hallar la composición de la mochila que maximiza el valor de la carga."

• En su versión continua, donde los objetos pueden fraccionarse, puederesolverse con un algoritmo devorador de forma óptima, usando laestrategia correcta para la selección de objetos. Esta estrategiase implementa dentro de lafunción de selección.

• Estrategia: Se seleccionaran los objetos en orden decreciente de relacióndevalor/peso.

• Conjunto de candidatos: Los objetos que queremos meter en la mochila.

• Función Solución: Comprobar si la mochila está llena.

• Función Selección: Elegir el objeto con mayor ratiovalor/peso

• Función de factibilidad: Que el objeto se pueda introducir en lamochila sin exceder la capacidad de esta.

• Función objetivo: La suma de los valores de los objetos que hayen la mochila.

• Objetivo: Maximizar.

defknapsack_problem(objetos,capacidad):candidates_set=objetos[:]candidates_selected= []whilecapacidad!=0andcandidates_set:candidato=select(candidates_set)candidates_set.remove(candidato)ifcandidato.peso<=capacidad:capacidad=capacidad-candidato.pesocandidates_selected.append(candidato)else:candidato.peso=capacidadcandidato.valor=candidato.valor*capacidad/candidato.pesocandidates_selected.append(candidato)capacidad=0returncandidates_selected

importmathdefselect(candidates_set):limit=-math.infbest_candidate=Noneforcandidateincandidates_set:ifcandidate.valor/candidate.peso>limit:best_candidate=candidatelimit=candidate.valor/candidate.pesoreturnbest_candidate

Implementada directamente en el código del algoritmo principal mediantela sentencia:

ifcandidato.peso<=capacidad:

whilecapacidad!=0 ...:

Especificada mediante la condición del bucle, y forma parte de la condiciónde parada del algoritmo.

defobjetivo(mochila):valor_total=0forobjetoinmochila:valor_total+=objeto.valorreturnvalor_total

"SeaM un conjunto de monedas yc una cantidad a devolver. Por cadatipo de moneda de valorv se dispone de un suministro dek unidades. Se desea hallar la composición del cambio que posee el menor número demonedas."

• En general, esta aproximación no produce una solución óptima,solo para un conjunto determinados de monedas, como por ejemplosi se dispondría de un número de un número suficiente de monedas de1, 5, 10, 15, 25, 50, 100, 200 y 500 unidades.

• Estrategia: Elegir, de las que quedan, la de mayor valor y si es posibleseleccionar todas las monedas del mismo valor de una vez.

• Conjunto de candidatos: Monedas.

• Función solución: El cambio a devolver es igual a 0.

• Función de selección: Elegir las monedas de mayor valor.

• Función de factibilidad: Valor de las monedas no supera el valor a devolver.

• Función objetivo: Número de monedas devueltas.

• Objetivo: Minimizar.

defcoinChange(conjunto_monedas,cambio):candidates_set=conjunto_monedascandidates_selected= []c=cambiocandidate_selected=Nonewhilec!=0andcandidates_set:candidate=select(candidates_set)candidates_set.remove(candidate)candidate.cantidad=min(candidate.cantidad,c//candidate.valor)ifcandidate.cantidad>0:candidates_selected.append(candidate)c=c-candidate.valor*candidate.cantidadreturncandidates_selected

importmathdefselect(candidate_set):candidate_selected=Nonelimit=-math.infforcandidateincandidate_set:iflimit<candidate.valor:candidate_selected=candidatelimit=candidate.valorreturncandidate_selected

Se realiza mediante estas dos sentencias. Primero se obtiene el mínimonúmero de esas monedas con las que se puede dar el cambio. Si es mayorque 0 entonces se puede dar un cambio parcial o total con al menosuna moneda de ese valor.

candidate.cantidad=min(candidate.cantidad,c//candidate.valor)ifcandidate.cantidad>0:

Especificada mediante la condición del bucle, y forma parte de la condiciónde parada del algoritmo.

whilec!=0 ... :

defobjetivo(monedas):suma=0formonedainmonedas:suma+=moneda.cantidadreturnsuma

"Dado un grafoG = <V,A> siendoV los vértices yA las aristas que componen el grafoG" conexo y ponderado con valores no negativosen sus aristas, se trata de calcular un subgrafoH = <V,S> conexo y acíclico deforma que la suma de los valores de sus aristas sea mínima."

• Se demuestra que el subgrafo resultante es un árbol.
• Un grafo puede tener más de un árbol de expansión mínimo.
• La comprobación que se debe realizar al ir generando el subgrafo para mantenerlo acíclico es costosa,así que se simplifica manteniendo el subgrafo acíclico por construcción.
• Supondremos un orden enA (aristas) inducido por la función de ponderación:{i, j} <= {k, j} <=> p(i, j)

• Conjunto candidatos: Las Aristas que componen el grafo.
• Función Solución: Hemos conseguido unir todos los vertices sin ciclos.
• Función Selección: Obtener la arista con menos valor.
• Función de factibilidad: Comprobar si al introducir una nueva arista, genera un ciclo.
• Función objetio: Suma total del valor de las aristas que conforman nuestro árbol de expansión mínimo.
• Objetivo: Minimizar.

A. Salguero, F. Palomo, I. Medina.
Algoritmos Devoradores.Universidad de Cádiz.

Brassard, Gilles & Bratley, Paul.
Fundamentos de Algoritmia.Prentice-Hall. 1997.

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. &Stein, Cli�ord.
Introduction to Algorithms.MIT Press. 2001. 2a ed.

Manber, Udi.
Introduction to Algorithms. A Creative Approach.Addison-Wesley. 1989.

Sedgevick, Robert.
Algorithms.Addison-Wesley. 1988. 2a edición.