Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 108 vistas

    Algoritmo Voraz

    Cargado por

    lukyto7000
    El algoritmo voraz es un método para resolver problemas de optimización que elige la mejor opción local en cada paso con la esperanza de alcanzar la solución óptima global. Funciona eligiendo sucesivamente las opciones de mayor valor que no superen el objetivo, y es rápido pero no garantiza siempre encontrar la solución óptima. Se usa comúnmente para problemas como el cambio de monedas, donde elige monedas de mayor valor hasta completar el cambio.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd

    Algoritmo Voraz

    Cargado por

    lukyto7000
    108 vistas13 páginas
    El algoritmo voraz es un método para resolver problemas de optimización que elige la mejor opción local en cada paso con la esperanza de alcanzar la solución óptima global. Funciona eligiendo sucesivamente las opciones de mayor valor que no superen el objetivo, y es rápido pero no garantiza siempre encontrar la solución óptima. Se usa comúnmente para problemas como el cambio de monedas, donde elige monedas de mayor valor hasta completar el cambio.

    Título original

    Algoritmo Voraz - copia.pptx

    Derechos de autor

    © Attribution Non-Commercial (BY-NC)

    Formatos disponibles

    PPTX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El algoritmo voraz es un método para resolver problemas de optimización que elige la mejor opción local en cada paso con la esperanza de alcanzar la solución óptima global. Funciona eligiendo sucesivamente las opciones de mayor valor que no superen el objetivo, y es rápido pero no garantiza siempre encontrar la solución óptima. Se usa comúnmente para problemas como el cambio de monedas, donde elige monedas de mayor valor hasta completar el cambio.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    108 vistas13 páginas

    Algoritmo Voraz

    Cargado por

    lukyto7000
    El algoritmo voraz es un método para resolver problemas de optimización que elige la mejor opción local en cada paso con la esperanza de alcanzar la solución óptima global. Funciona eligiendo sucesivamente las opciones de mayor valor que no superen el objetivo, y es rápido pero no garantiza siempre encontrar la solución óptima. Se usa comúnmente para problemas como el cambio de monedas, donde elige monedas de mayor valor hasta completar el cambio.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    Está en la página 1de 13

    Universidad Cientfica del Per

    Facultad de Ciencias e Ingeniera Carrera Profesional de Ingeniera de Sistemas e informtica


    Tema:

    Algoritmo Voraz
    1. 2. 3. 4. 5.

    Expositores: Mendoza Macedo, Luis Machuca Daz, Vctor Freitas Leo , Luis (NT) Rodrguez Sol sol, ngelo Meza Ramrez, Mark

    Docente: ING. HERNAN MEDINA

    Definicin

    Ventajas

    Tiempo de ejecucin

    Anlisis Empleo Desventajas

    Funcionamiento

    Ejemplo

    Definicin
    Un algoritmo voraz (conocido como devorador) es aquel que, para resolver un determinado problema, sigue un procedimiento consistente en elegir la opcin ptima en cada paso local con la esperanza de llegar a una solucin general ptima.
    Los algoritmos voraces suelen ser bastantes simples y se aplican a los problemas de optimizacin.

    Es uno de los esquemas ms simples y al mismo tiempo de los ms utilizados.

    TPICAMENTE SE EMPLEA PARA RESOLVER PROBLEMAS DE OPTIMIZACIN:

    Existe una entrada de tamao n que son los candidatos a formar parte de la solucin;

    Existe un subconjunto de esos n candidatos que satisface ciertas restricciones: se llama solucin factible;
    Hay que obtener la solucin factible que maximice o minimice una cierta funcin objetivo: se llama solucin ptima.

    EL FUNCIONAMIENTO DE ESTA TCNICA SIGUE LOS SIGUIENTES PASOS: Para cada paso en el algoritmo se elige la mejor opcin, que se tiene disponible. Se comprueba si la opcin elegida podra llevar a la solucin del problema. Si esa opcin puede llevar a la solucin se elige, sino se elige la siguiente mejor opcin. Si el conjunto de mejores opciones escogidas es solucin, se termina el algoritmo. Sino se contina

    VENTAJAS

    Las soluciones voraces son muy fciles de implementar Por lo tanto fciles de depurar La velocidad de ejecucin es muy rpida.

    Adems de usar muy poca memoria

    DESVENTAJA
    Aunque parecera que este es la mejor forma de solucionar un problema, existe una desventaja muy importante, no todos los problemas se pueden resolver con esta tcnica, ya que no daran la solucin apropiada para el mismo. Tambin hay que tomar en cuenta que existen mucho algoritmos conocidos que usan esta tcnica, como son: Algoritmo de Kruskal, Algoritmo de Prim, Algoritmo de Dijkstra.

    EJEMPLOS DEL CAMBIO DE MONEDA


    Enunciado: "Se pide crear un algoritmo que permita a una

    mquina expendedora devolver el cambio mediante el menor nmero de monedas posible, considerando que el nmero de monedas es limitado, es decir, se tiene un nmero concreto de monedas de cada tipo".

    Solucin: La estrategia a seguir consiste en escoger sucesivamente

    las monedas de valor mayor que no superen la cantidad de cambio a devolver. El buen funcionamiento del algoritmo depende de los tipos de monedas presentes en la entrada. As, por ejemplo, si no hay monedas de valor menor que diez, no se podr devolver un cambio menor que diez. Adems, la limitacin del nmero de monedas tambin influye en la optimalidad del algoritmo, el cual devuelve buenas soluciones bajo determinados conjuntos de datos, pero no siempre. Considrense los dos siguientes ejemplos como demostracin de lo dicho:

    Si hay que devolver la cantidad 110 siguiendo el mtodo del algoritmo voraz, se tomara primero una moneda de 50, quedando una cantidad restante de 60. Como 50 es an menor que 60, se tomara otra moneda de 50. Ahora la cantidad restante es 10, por tanto ya tenemos que devolver una moneda de 5, ya que 50 y 25 son mayores que 10, y por tanto se desechan. La cantidad a devolver ahora es 5. Se tomara otra moneda de 5, pero puesto que ya no nos queda ninguna, debern devolverse 5 de valor 1, terminando as el problema de forma correcta.

    Si queremos devolver la cantidad 8, siguiendo el procedimiento anterior, el algoritmo tomara primero una moneda de 6, quedando un resto de 2. Tomara 2 monedas de valor 1, habiendo devuelto por tanto 3 monedas, cuando es fcil ver que con 2 monedas de valor 4 se obtiene el resultado pedido.

    Elementos fundamentales del ejemplo de la Moneda


    Conjunto de candidatos: cada una de las monedas de los diferentes tipos que se pueden usar para realizar el desglose del importe dado. Solucin: un conjunto de monedas devuelto tras el desglose y cuyo valor total es igual al importe a desglosar. Completable: la suma de los valores de las monedas escogidas en un momento dado no supera el importe a desglosar. Funcin de seleccin: elegir si es posible la moneda de mayor valor de entre las candidatas. Funcin objetivo: nmero total de monedas utilizadas en la solucin (debe minimizarse).

    TIEMPO DE EJECUCION

    El orden de complejidad depende de:


    El nmero de candidatos existentes.

    Los tiempos de las funciones bsicas utilizadas.


    El nmero de elementos de la solucin.

    TIEMPO DE EJECUCION

    El anlisis depende de cada algoritmo concreto. En la prctica los algoritmos voraces suelen ser bastante rpidos, encontrndose dentro de rdenes de complejidad poligonales.
    Funcin solucin: Normalmente O(1) u O(n). Funcin de seleccin: Entre O(1) y O(n).

    Anlisis de un algoritmo Voraz


    Caractersticas Rapidez Dificultad de desarrollo Efectividad Eficiencia Rendimiento Alta Media Media Media

    También podría gustarte