PROYECTO 5.- Asignación (matching): algoritmo húngaro

Asignación (matching): algoritmo húngaro

 INTRODUCCION:

Empezare describiendoles como es la asignación (matching)_
Dado un grafo un matching U en V es un conjunto de aristas no adyacentes entre sí.
Se dice  que un vértice está matched (asignado) si es contiguo con una arista en el matching.
En otro caso, el vértice está unmatched (libre).

Un matching perfecto es un matching que cubre todos los vértices del grafo. Ésto es, cada vértice está saturado bajo el matching.


2. Matchings en grafos bipartitos
Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U de azul y los vérices deV de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.

Los problemas de matching tienen relación muchas veces con grafos bipartitos. Encontrar un matching máximo bipartito (a menudo llamado cardinalidad máxima de un grafo bipartito) en un grafo bipartito es quizás el problema más simple.
En un grafo bipartito ponderado, cada arista tiene asociado un valor.
Un matching máximo bipartito ponderado está definido como un matching perfecto donde la suma de los valores de sus arcos en el matching tiene un valor maximal. Si el grafo no es completamente bipartito, los arcos ausentes son introducidos con valor cero.
Encontrar tal matching es conocido como problema del asignacion.

El más especializado es el algoritmo Húngaro que resuelve el problema de asignación con costo de tiempo .


DEFINICION:
La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955.

 Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro.

Esta fue revisada porJames Munkres en 1957, y ha sido conocido como el algoritmo húngaro, el algoritmo deasignación Munkres, o el algoritmo de Kuhn-Munkres.

El algoritmo modela un problema deasignación como una matriz de costo mn× ,donde cada elemento representa el costo de asignar el  n  trabajador al m trabajo.

El algoritmo realiza la minimización sobre los elementos de la matriz como en el caso de un problema de minimización de precios.

Seutiliza el método de eliminación Gaussiana para hacer aparecer ceros (al menos un ceropor línea y por columna). Sin embargo, en el caso de un problema de maximización de  beneficio, el costo de la matriz necesita ser modificada de modo que la minimización de sus elementos resulte maximizar los valores de costo originales.
En un problema de costo infinito, la matriz de costo inicial puede ser remodelada restando cada elemento de cada línea del valor máximo del elemento de esa línea (o la columna respectivamente). En un problema de costo finito, todos los elementos son restados del valor máximo de la matriz  entera.


FASES PARA LA APLICACION DE METODO HUNGARO:
 Las fases para la aplicación del método Húngaro son:

1.- Encontrar primero el elemento mas pequeño en cada fila de la matriz de costos m*m; se debe contruir una nueva matriz al restar de cada costo el costo  minimo de cada fila, encontrar para esta nueva matriz, el costo minimo en cada columna. A continuacion se debe construir una nueva matriz (denominada matriz de costos reucidos) al restar de cada costo el costo minimo de su columna.

2.- (En unos textos este paso se atribuye a Flood), consiste en trazar el numero minimo de lineas (horizontales o verticales o ambas unicamente de esas maneras), que se requieren para cubrir todos los ceros en la matriz de costos reducidos; si se necesitan m lineas para cubrir los todos los ceros, se tiene una solucion optima entre los ceros cubiertos de la matriz. Si se requieren menos de m lineas para cubrir todos los ceros, se debe continuar con el paso 3. El numero de lineas para cubrir los ceros es igual a la cantidad de asignaciones que hasta ese momento se puede realizar.

3.- Encontrar el menor elemento diferente de cero (llamado k) en la matriz de costos reducidos, que no esta cubierto por las lineas dibujadas en el paso 2; a continuacion se debe restar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elemento de la matriz de costos reducidos cubiertos por dos lineas (intersecciones). Por ultimo se deve regresar al paso 2.

NOTAS:
A) Para resolver un problema de asignacion en el cual la meta es maximizar la funcion objetivo, se debe multiplicar la matriz de ganancias por menos uno (-1) y resolver el problema como uno de minimizacion.
B) Si el numero de filas y de columnas en la matriz de costos son diferentes, el problema de asignacion esta desbalanceado. El metodo hungaro puede proporcionar una solucion incorrecta si el problema no esta balanceado; debido a lo anterior, se debe balancear primero cualquier problema de asignacion (añadiendo filas o columnas ficiticias) antes de resolverlo mediante el metodo Hungaro.

C) En un problema grande, puede resultar dificil obtener el minimo numero de filas necesarias para cubrir todos los ceros en la matriz de costos actual. Se puede demostrar que si se necesitan j lineas para cubrir  todos los ceros, entonces se pueden asignar solamente j trabajos a un costo cero en la matriz actual; esto explica porque termina cuando se necesitan m lineas.

DEFINIR SI ES DE DECISION O DE OPTIMIZACION:
El algoritmo húngaro es un algoritmo de optimización combinatoria que soluciona problemas de asignación en tiempo n(O)3.


Optimizacion combinatoria:
La optimización combinatoria es una rama de la optimización en matemáticas aplicadas y en ciencias de la computación, relacionada a la investigación de operaciones, teoría de algoritmos y teoría de la complejidad computacional. También está relacionada con otros campos, como la inteligencia artificial e ingeniería de software. Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.


Los algoritmos de optimización combinatoria a menudo son implementados en lenguajes imperativos como C y C++,en lenguajes de programación lógicos tales como Prolog, o incluso en lenguajes multi-paradigma tales como Oz.

Mediante el estudio de la teoría de la complejidad computacional es posible comprender la importancia de la optimización combinatoria. Los algoritmos de optimización combinatoria se relacionan comúnmente con problemas NP-hard. Dichos problemas en general no son resueltos eficientemente, sin embargo, varias aproximaciones de la teoría de la complejidad sugieren que ciertas instancias (ej. "pequeñas" instancias) de estos problemas pueden ser resueltas eficientemente. Dichas instancias a menudo tienen ramificaciones prácticas muy importantes.

COMPLEJIDAD COMPUTACIONAL:

La complejidad es O(n3),  Complejidad cúbica.
Suele darse en bucles con triple anidación. Si n se duplica, el tiempo de ejecución se multiplica por ocho. Para un valor grande de n empieza a crecer dramáticamente.

◦Contamos con una computadoracapaz de procesar datos en 10-4 seg. En esta computadora se ejecuta un algoritmo que lee registros de una base de datos, dicho algoritmo tiene una complejidad exponencial 2n, ¿Cuánto tiempo se tardará en procesar una entrada n de datos?

◦Ahora se tiene la misma computadora capaz de procesar datos en 10-4 seg. Pero se ejecuta un algoritmo que hace el mismo trabajo antes citado, pero este algoritmo tiene una complejidad cúbica n3, ¿Cuánto tiempo se tardará en procesar una entrada n de datos?

Se puede decir, que solo un algoritmo eficiente, con un orden de complejidad bajo, puede tratar grandes volumen de datos, se razona que un algoritmo es:

-Muy eficiente si su complejidad es de orden log n
-Eficiente si su complejidad es de orden na
-Ineficiente si su complejidad es de orden 2n
-Se considera que un problema es tratable si existe un algoritmo que lo resuelve con complejidad menor que 2n, y que es intratable o desprovisto de solución en caso contrario.

PSEUDOCODIGO DEL ALGORITMO:

 Esta es la liga donde encontre la informacion detallada sobre cada paso, y lo que se debe de tomar en cuenta.
http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html


ANALISIS ASINTOTICO DEL ALGORITMO (logaritmico, polinomial, exponencial):
Este algoritmo es de claser P, ya  que existe un algoritmo que puede resolverse en tiempo polinómico, algo que para valores razonables podrá resolverse en un ordenador mediante un programa adecuado.


ESTRUCTURA DE DATOS UTILIZADA (arreglos, listas, colas, pilas, arboles):
La estructura mas utilizada es: colas, pues proporciona una base teorica del tipo de servicio que podemos espeerar de un determinado recurso, como la forma en la que dicho recurso puede ser diseñado para proporcionar un determinado grado de servicio a sus clientes.

Los sistemas de colas son modelos de sistema que proporcionan servicio. Como modelo pueden determinar cualquier sistema en donde los trabajos o clientes llegan buscando un servicio de algun tipo, y salen despues de que dicho servicio haya sido atendido.
Podemos modelar los sistemas de este tipo, tanto como colas sencillas o como un sistema de colar interconectadas, formando una red de colas.

EJEMPLO (manual, programado, animado):
http://www.tu.tv/videos/metodo-hungaro

1. Localice el menor elemento de cada renglón y réstelo a los demás elementos del mismo renglón. Repítase este procedimiento para cada columna donde el mínimo por columna se determina después de las restas de los renglones.
2. Determine si existe una asignación factible que involucre costos cero en la matriz revisada de costos. Si existe tal asignación es óptima. Si no existe continúe con el paso 3.
3. Cubra todos los ceros en la matriz revisada de costos con el menor número de líneas horizontales y verticales que sea posible. Cada línea horizontal debe pasar por todo el renglón y cada línea vertical por toda la columna. Localice el número menor que no esté cubierto por una línea en la matriz de costos. Reste el valor de este número a cada elemento no cubierto por una línea y súmelo a cada elemento cubierto por dos líneas.
4. Repita el procedimiento del paso 2.
EJEMPLO:
Una competencia de relevos de 400 metros incluye a cuatro diferentes nadadores quienes nadan sucesivamente 100 metros de dorso, pecho, mariposa y libre. Un entrenador tiene 6 nadadores muy veloces cuyos tiempos esperados en segundos en los eventos individuales se dan en la tabla ¿Cómo deberá el entrenador asignar los nadadores a los relevos a fin de minimizar la suma de sus tiempos?

APLICACIONES (donde se presenta el problema):
Cuando existe dilema, sobre la asignacion de una persona o un servicio hacia una respuesta o trabajo, a fin de que se solucione el primer planteamiento, y sea eficaz y util para quien lo necesita.



EN QUE SE USA ESTE ALGORITMO:
Este algoritmo se usa para resolver problemas de minimización, ya que es más eficaz que el empleado para resolver el problema del transporte por el alto grado de degeneración que pueden presentar los problemas de asignación.




*ALGUNAS DEFINICIONES MENCIONAN VARIOS EJEMPLOS.
*Estos licks son algunos de los que hice mi investigacion*
http://www.itlalaguna.edu.mx/Academico/Carreras/industrial/invoperaciones1/u5.HTML
http://www.scribd.com/doc/62765/memmetpp

 http://www.sangakoo.com/es/Divulgacion/divulgacion/157/algoritmos.aspx
http://www.slideshare.net/rezzaca/u1-analisis-algoritmos-complejidad
http://www.pdfqueen.com/html/aHR0cDovL2l0LmNpaWRpdC51YW5sLm14L35lbGlzYS90ZWFjaGluZy9hYS9wZGYvYWEucGRm
http://www.eici.ucm.cl/Academicos/R_Villarroel/descargas/investigacion_operaciones/Asignacion_y_Vendedor_Viajero.pdf

http://www.monografias.com/trabajos27/complejidad-algoritmica/complejidad-algoritmica.shtml
 http://www.scribd.com/doc/7046323/EL-METODO-HUNGARO...