Algoritmo húngaro para el problema de asignación | Conjunto 2 (Implementación)

Ejemplo

Entrada: arr[][] = {{3, 5}, {10, 1}}
Salida: 4
Explicación: La asignación óptima es asignar el trabajo 1 al primer trabajador, el trabajo 2 al segundo trabajador.
Por lo tanto, el costo óptimo es 3 + 1 = 4.

Entrada: arr[][] = {{2500, 4000, 3500}, {4000, 6000, 3500}, {2000, 4000, 2500}}
Salida: 4
Explicación: la asignación óptima es asignar el trabajo 2 al primer trabajador , trabajo 3 al segundo trabajador y trabajo 1 al 3er trabajador.
Por lo tanto, el costo óptimo es 4000 + 3500 + 2000 = 9500.

En este artículo se analizan diferentes enfoques para resolver este problema .

Enfoque: La idea es utilizar el algoritmo húngaro para resolver este problema. El algoritmo es como sigue:

1. Para cada fila de la array, encuentre el elemento más pequeño y réstelo de cada elemento en su fila.
2. Repita el paso 1 para todas las columnas.
3. Cubre todos los ceros en la array usando el número mínimo de líneas horizontales y verticales.
4. Prueba de Optimalidad : Si el número mínimo de líneas de cobertura es N , es posible una asignación óptima. De lo contrario, si las líneas son menores que N , no se encuentra una asignación óptima y se debe continuar con el paso 5.
5. Determine la entrada más pequeña no cubierta por ninguna línea. Reste esta entrada de cada fila descubierta y luego súmela a cada columna cubierta. Regrese al paso 3.

Considere un ejemplo para entender el enfoque:

Sea la array 2D:

2500 4000 3500
4000 6000 3500
2000 4000 2500

Paso 1: Resta el mínimo de cada fila. Se restan 2500, 3500 y 2000 de las filas 1, 2 y 3 respectivamente.

0 1500 1000
500 2500 0
0 2000 500

Paso 2: Resta el mínimo de cada columna. 0, 1500 y 0 se restan de las columnas 1, 2 y 3 respectivamente.

0 0 1000
500 1000 0
0 500 500

Paso 3: cubra todos los ceros con un número mínimo de líneas horizontales y verticales.

Paso 4: Dado que necesitamos 3 líneas para cubrir todos los ceros, se encuentra la asignación óptima. 

 2500   4000  3500
 4000 6000   3500
 2000  4000 2500

Entonces el costo óptimo es 4000 + 3500 + 2000 = 9500

Para implementar el algoritmo anterior, la idea es usar la función max_cost_assignment() definida en la biblioteca dlib . Esta función es una implementación del algoritmo húngaro (también conocido como algoritmo Kuhn-Munkres) que se ejecuta en tiempo O(N ³ ) . Resuelve el problema de asignación óptima. 

A continuación se muestra la implementación del enfoque anterior:

# Python program for the above approach
import dlib
  
# Function to find out the best
# assignment of people to jobs so that
# total cost of the assignment is minimized
def minCost(arr):
  
    # Call the max_cost_assignment() function
    # and store the assignment
    assignment = dlib.max_cost_assignment(arr)
  
    # Print the optimal cost
    print(dlib.assignment_cost(arr, assignment))
  
  
# Driver Code
  
# Given 2D array
arr = dlib.matrix([[3, 5], [10, 1]])
  
# Function Call
minCost(arr)

4

Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(N ² )