miércoles, 14 de enero de 2015

Algoritmos voraces

Una algoritmo voraz es un tipo de algoritmo que nos permite resolver un determinado problema de una forma concreta.

Este tipo de algoritmos voraces se aplica a problemas de optimización en los que la solución se puede construir paso a paso sin necesitar ningún dato o decisión anterior. Generalmente estos algoritmos encuentran un conjunto de candidatos que constituyen la solución y que la optimiza. Es usado en problemas de planificación, problemas que se pueden modelar con grafos y en los que se suele realizar una búsqueda, cálculo de recorridos, optimización de pesos, etc.

Por regla general los problemas que se suelen resolver con este tipo de algoritmos constan de unos candidatos y se trata de encontrar una solución basada en obtener un subconjunto de esos candidatos o una secuencia ordenada de los mismos de manera que se optimice una función objetivo (lo que queramos conseguir).

Para aplicar este tipo de algoritmos se suele trabajar por etapas o fases,  tratando un candidato en cada fase. Hay que ir seleccionando en cada etapa al candidato más "bueno" para lo que buscamos de los aún disponibles y decidir si se incluye o no en la solución.

Trabajando así podemos ver que se examina una vez cada candidato y se decide si se selecciona o se rechaza. Luego se intentará seleccionar al mejor de los candidatos restantes hasta encontrar la solución que se busque. Si el algoritmo es correcto, la primera solución encontrada es la solución óptima.

La principal característica que distingue los algoritmos voraces de otros tipos de algoritmos es que nunca se vuelve a atrás y se anula una decisión ya tomada por lo que cuando se incorpora un candidato a la solución, este permanece hasta el final. Del mismo modo cuando se rechaza un candidato no se vuelve a tener en cuenta.

Este tipo de algoritmos voraces pueden parecer sencillos y al no volver a "ver" los candidatos que ya han sido tratados suelen resultar eficientes en la mayoría de los casos.

Dos problemas de grafos muy conocidos que se resuelven con este tipo de algoritmos son hallar un árbol de recubrimiento de distancia o coste mínimo y calcular el camino de coste mínimo entre un nodo y los demás. Algunos algoritmos muy conocidos para resolverlos son los algoritmos de Prim, algoritmo de Kruskal, algoritmo de Dijkstra.

Otro problemas conocidos que se pueden resolver con algoritmos voraces son el problema de la mochila con objetos fraccionables, problemas de mantenimiento de la conectividad, problemas de mensajería urgente, etc.

Si queréis que profundicemos más sobre este tipo de algoritmos o que resolvamos algún problema con ellos no dudéis en ponerlo en los comentarios ;)


10 comentarios:

  1. Buenas tardes, para una unediano atrasada entendiendo Dijsktra y todo como puedo llegar a plasmar estos problemas en Bluej o Eclipse de la asignatura de programación y estructuras (acabo de empezar y ando verde). Te adjunto las practicas y haber si me puedes iluminar jeje. Adjunto mi correo irenene23@hotmail.com
    https://apuntrix.com/practicas/uned/grado-en-ingenieria-en-tecnologias-de-la-informacion/programacion-y-estructuras-de-datos-avanzadas

    Gracias

    ResponderEliminar
  2. a que te refieres con plasmarlo en Bluej o Eclipse? a hacer una interface gráfica? o al código? por la página tengo algunos vídeos que tienen una forma gráfica de hacerlo como este del algoritmo de Prim https://www.youtube.com/watch?v=AXbOfTsfivY

    ResponderEliminar
  3. Gracias, el otro día escribí pero no se agrego el comentario. No se como hacerlo en código como empezarlo porque tengo cacho de código y nose como traducirlo o como tirar de hay. Muchas gracias

    tipo VectorNat = matriz[O .. n] de natural
    fun Dijkstra (G = (N,A): grafo): VectorNat, VectorNat
    var
    especial, predecesor: VectorNat
    C: conjunto de nodos
    fvar
    Iniciar conjunto C con todos los nodos 1,2,3, .. n excepto el 19
    para i f- 1 hasta n 1\ i -¡. 19 hacer
    especial[i] f- Distancia(l9,i)
    predecesor[i] f- 19
    fpara
    mientras C contenga al nodo S hacer {el nodo 2 es S }
    V f- nodo E C que minimiza especial[ V]
    Cf-C\{v}
    si v -¡. S entonces
    fsi
    para cada w E C hacer
    si especial[w] > especial[v] + Distancia(v,w) entonces
    especial[w] f- especial[v] + Distancia(v,w)
    predecesor[ w] f- v
    fsi
    fpara
    fmientras
    dev especial[] ,predecesor[]
    ffun

    ResponderEliminar
    Respuestas
    1. cual es la duda que tienes? pasar ese pseudocódigo a código real?

      Eliminar
  4. Sip, creo que si entendiese como pasar eso algo avanzaría. Eso por ejemplo como lo pasaría? Muchas gracias

    ResponderEliminar
    Respuestas
    1. según el pseudocódigo que pones tiene en la primera línea una declaración de un vector de tipo int (números naturales) y el resto es una función desde donde pone fun (inicio de la función) hasta ffun (fin de la función). Dentro de la función tienes declaración de variables donde pone var hasta fvar. Después es una inicialización y seguidamente un bucle for desde para hasta fpara. Donde pone mientras tienes un while que tiene dentro un if donde pone si hasta fsi, luego un for donde pone para con un if dentro y finalmente lo que devuelve la función es especial y predecesor que son dos vectores naturales

      Eliminar
  5. Gracias, todavía lo veo negro porque tengo alguna mas he imagino que no sera solo traducir eso. Lo harías en eclipse o bluej? Quien me habrá mandado a mi meterme en este jaleo...esta semana tengo clase con el haber si nos resuelve algo sino ya te pediré mas sopitas jeje. Muchas gracias

    ResponderEliminar
    Respuestas
    1. yo empecé java con bluej y muy bien, a la hora de hacer proyectos más grandes ya me cambié a eclipse, con cualquiera de los dos lo puedes hacer perfectamente, utiliza el que mejor conozcas ahora para no gastar tiempo en aprender a usar el ide, si ves que no lo logras sacar me lo dices y hago un publicación nueva con el código y eso (aunque te recomiendo que lo hagas tu solo para poder entenderlo mejor, intenta traducirlo línea a línea y entendiendo que hace cada línea)

      Eliminar
  6. Gracias por tu ayuda, empezare con blue creo que sera mas fácil. el profe nos dio una clase el otro día y nos a subido un esqueleto. Comento algo también de usar monticulos. Como me vea apurado tendré que pedir sopitas y ya le daré mi correo que sino me lo plagian jejeje

    ResponderEliminar