Encriptacion

FACULTAD DE INGENIERÍA CARRERA DE INGENIERÍA DE SISTEMAS

ASIGNATURA :

ANÁLISIS Y DISEÑO DE ALGORITMOS

TRABAJO

:

EL PROBLEMA DEL CAMBIO

DOCENTE

:

GOMEZ MORALES, Anthony JoséALUMNOS

: CORREA ANGULO, Akemi Marleny QUISPE CASTREJÓN, Jhony

CICLO

:

V - 2012

Cajamarca, Junio de 2012

ALGORITMOS VORACES
I. DEFINICIÓN También conocidos como algoritmos ávidos,glotones o Greedy. Son aplicados a problemas de decisión y de optimización. Es de fácil implementación. Suelen ser muy eficientes. II. ¿PARA QUÉ SE EMPLEA? Es un de los esquemas más simples y almismo tiempo el más utilizado. Se emplea típicamente para resolver problemas de Optimización. Existe una entrada de tamaño n que son los candidatos de formar parte de la solución. Hay que obtener lasolución factible que maximice y minimice una cierta función de objetivos a eso llamamos función Óptica. III. PASOS PARA RESOLVER UN ALGORITMO VORAZ Un algoritmo greedy toma las decisiones en función de linformación que está disponible en cada momento. Una vez tomada la decisión no vuelve a replantearse en el futuro. El algoritmo termina cuando no queda decisiones por tomar. Es correcto si podemosgarantizar que la solución encontrada es siempre óptima. No garantizan alcanzar la solución óptima.

IV.

ELEMENTOS DE LA TÉCNICA

Conjunto de candidatos a seleccionar

Conjunto de candidatos aseleccionados

Función solución

¿Los candidatos seleccionados alcanzaron una solución?

Función de Factibilidad

Es posible completar el conjunto de candidatos

Función SelecciónDeterminar el mejor candidato del conjunto a seleccionar

Función Objetivo

Da el valor de la solución alcanzada

V.

USADOS COMO HEURÍSTICOS Hay situaciones en las cuales no podemos encontrar unalgoritmo greedy que proporcione una solución óptima… En muchas ocasiones, se podrían obtener mejores soluciones reconsiderando alternativas desechadas por un algoritmo greedy (cuando, a partir de una...