Sistemas De Archivos
Páginas: 2 (324 palabras)
Publicado: 26 de septiembre de 2013
Hugo Araya Carrasco (haraya@spock.ucm.cl)
ANALISIS DE ALGORITMOS
Algoritmos Voraces
Hugo Araya Carrasco
Los algoritmos voraces suelen ser bastante simples. Se emplean principalmente
pararesolver problemas de optimización, como por ejemplo, encontrar la
secuencia óptima para procesar un conjunto de tareas por un computador, hallar
el camino mínimo de un grafo, etc. Habitualmente, loselementos que
intervienen son:
•
Un conjunto o lista de candidatos (tareas a procesar, vértices del grafo, etc.);
•
Un conjunto de decisiones ya tomadas (candidatos ya escogidos);
•Una función que determina si un conjunto de candidatos es una solución al
problema (aunque no tiene por qué ser la óptima);
•
Una función que determina si un conjunto es completable, es decir,si
añadiendo a este conjunto nuevos candidatos es posible alcanzar una solución
al problema, suponiendo que esta exista;
•
Una función de selección que escoge el candidato aún no seleccionadoque es
más prometedor;
•
Una función objetivo que da el valor/costo de una solución (tiempo total del
proceso, la longitud del camino, etc.) y que es la que se pretende maximizar
o minimizar;Para resolver el problema de optimización hay que encontrar un conjunto de
candidatos que optimiza la función objetivo.
Los algoritmos voraces proceden por pasos.
Inicialmente el conjunto decandidatos es vacío.
Pág. 1
Hugo Araya Carrasco (haraya@spock.ucm.cl)
A continuación, en cada paso, se intenta añadir al conjunto el mejor candidato
de los aún no escogidos, utilizando lafunción de selección.
Si el conjunto resultante no es completable, se rechaza el candidato y no se le
vuelve a considerar en el futuro. En caso contrario, se incorpora al conjunto de
candidatosescogidos y permanece siempre en él.
Tras cada incorporación se comprueba si el conjunto resultante es una solución
del problema.
Un algoritmo voraz es correcto si la solución así encontrada es siempre...
ANALISIS DE ALGORITMOS
Algoritmos Voraces
Hugo Araya Carrasco
Los algoritmos voraces suelen ser bastante simples. Se emplean principalmente
pararesolver problemas de optimización, como por ejemplo, encontrar la
secuencia óptima para procesar un conjunto de tareas por un computador, hallar
el camino mínimo de un grafo, etc. Habitualmente, loselementos que
intervienen son:
•
Un conjunto o lista de candidatos (tareas a procesar, vértices del grafo, etc.);
•
Un conjunto de decisiones ya tomadas (candidatos ya escogidos);
•Una función que determina si un conjunto de candidatos es una solución al
problema (aunque no tiene por qué ser la óptima);
•
Una función que determina si un conjunto es completable, es decir,si
añadiendo a este conjunto nuevos candidatos es posible alcanzar una solución
al problema, suponiendo que esta exista;
•
Una función de selección que escoge el candidato aún no seleccionadoque es
más prometedor;
•
Una función objetivo que da el valor/costo de una solución (tiempo total del
proceso, la longitud del camino, etc.) y que es la que se pretende maximizar
o minimizar;Para resolver el problema de optimización hay que encontrar un conjunto de
candidatos que optimiza la función objetivo.
Los algoritmos voraces proceden por pasos.
Inicialmente el conjunto decandidatos es vacío.
Pág. 1
Hugo Araya Carrasco (haraya@spock.ucm.cl)
A continuación, en cada paso, se intenta añadir al conjunto el mejor candidato
de los aún no escogidos, utilizando lafunción de selección.
Si el conjunto resultante no es completable, se rechaza el candidato y no se le
vuelve a considerar en el futuro. En caso contrario, se incorpora al conjunto de
candidatosescogidos y permanece siempre en él.
Tras cada incorporación se comprueba si el conjunto resultante es una solución
del problema.
Un algoritmo voraz es correcto si la solución así encontrada es siempre...
Leer documento completo
Regístrate para leer el documento completo.