-1

En cuadrada :

def calcular_opciones(valor, tabla):
    maximo = valor
    minimo = valor
    for index, row in tabla.iterrows():
        maximo += max(row)
        minimo += min(row)       
    return [minimo, maximo]

def asignacion_tareas_grafo(nodos, profundidad_restante):

    if profundidad_restante == 0:

        return nodos

    nuevos_nodos = []
    nodos_candidatos = []
    minimos_de_candidatos = []
    maximos_de_candidatos = []

    for nodo in nodos:

        solucion, valor, tabla = nodo
        columns = list(tabla)

        for column in columns:
            opcion = tabla[column][0]
            nueva_solucion = solucion + [column]
            nuevo_valor = valor + opcion
            nueva_tabla = tabla[1:]
            nueva_tabla = nueva_tabla.drop(column, axis=1)
            nuevo_nodo = [nueva_solucion, nuevo_valor, nueva_tabla]
            nodos_candidatos.append(nuevo_nodo)

            opcion_minimo, opcion_maximo = calcular_opciones(nuevo_valor, nueva_tabla)
            minimos_de_candidatos.append(opcion_minimo)
            maximos_de_candidatos.append(opcion_maximo)

    profundidad_restante -= 1


    valor_prune = max(minimos_de_candidatos)
    for i in range(len(minimos_de_candidatos)):
        if maximos_de_candidatos[i] >= valor_prune:
            nuevos_nodos.append(nodos_candidatos[i])

    return asignacion_tareas_grafo(nuevos_nodos, profundidad_restante)

def asignacion_tareas(tabla):
     size = len(list(tabla))

    nodo_inicial = [[], 0, tabla]
    nodos_inicio = [nodo_inicial]
    soluciones = asignacion_tareas_grafo(nodos_inicio, size)

    count = 0
    for solucion in soluciones: 
        asignacion, valor, tabla = solucion
        print("---------------")
        print("Solucion " + str(count) + ":")
        print("Las asignaciones por admin son: " + str(asignacion))
        print("El valor obtenido con las asignaciones es: " + str(valor))
        count +=1

asignacion_tareas(tabla_tareas)

2
  • 1
    La pregunta no está bien planteada. Debes comenzar por explicar o dar alguna referencia a cuál es el algoritmo Húngaro. Después proporcionas un código, pero sin explicaciones ni contexto ¿de dónde sale? ¿lo has escrito tú? ¿lo has copiado? ¿por qué está ahí? ¿hay algo en él que no funciona o que no entiedes? ¿el qué? ¿Da algún error al ejecutar? ¿Cuál? ¿No sale lo que esperabas? ¿Qué esperabas y qué es lo que sale? Tal como está no se entiende qué preguntas.
    – abulafia
    Commented el 21 nov. 2019 a las 12:46
  • Hola puedes añadir una matriz de entrada de ejemplo. Muchas gracias.
    – J Campos
    Commented el 21 nov. 2019 a las 14:00

2 respuestas 2

0

Como no das ejemplo de entrada, lo he tenido que deducir mas o menos. Tampoco domino el algoritmo hungaro. He probado con dos dataframes: cuadrado (df1) y rectangular (df2). Sintacticamente funciona pero semanticamente tendria que dedicar mas tiempo a ver si el resultado es correcto.

import pandas as pd

def calcular_opciones(valor, tabla):
    maximo = valor
    minimo = valor
    for index, row in tabla.iterrows():
        try:
            maximo += max(row)
        except:
            maximo += 0
        try:
            minimo += min(row)
        except:
            minimo += 0
    return [minimo, maximo]

def asignacion_tareas_grafo(nodos, profundidad_restante,index_ini):



    if profundidad_restante == 0:

        return nodos

    nuevos_nodos = []
    nodos_candidatos = []
    minimos_de_candidatos = []
    maximos_de_candidatos = []

    for nodo in nodos:

        solucion, valor, tabla = nodo
        columns = list(tabla)



        for column in columns:

            opcion = tabla[column][index_ini]

            nueva_solucion = solucion + [column]
            nuevo_valor = valor + opcion
            nueva_tabla = tabla[1:]
            nueva_tabla = nueva_tabla.drop(column, axis=1)
            nuevo_nodo = [nueva_solucion, nuevo_valor, nueva_tabla]
            nodos_candidatos.append(nuevo_nodo)

            opcion_minimo, opcion_maximo = calcular_opciones(nuevo_valor, nueva_tabla)
            minimos_de_candidatos.append(opcion_minimo)
            maximos_de_candidatos.append(opcion_maximo)

    profundidad_restante -= 1


    valor_prune = max(minimos_de_candidatos)
    for i in range(len(minimos_de_candidatos)):
        if maximos_de_candidatos[i] >= valor_prune:
            nuevos_nodos.append(nodos_candidatos[i])

    return asignacion_tareas_grafo(nuevos_nodos, profundidad_restante, index_ini+1)

def asignacion_tareas(tabla):
    size = len(list(tabla))

    nodo_inicial = [[], 0, tabla]
    nodos_inicio = [nodo_inicial]
    soluciones = asignacion_tareas_grafo(nodos_inicio, size, 0)

    count = 0
    for solucion in soluciones: 
        asignacion, valor, tabla = solucion
        print("---------------")
        print("Solucion " + str(count) + ":")
        print("Las asignaciones por admin son: " + str(asignacion))
        print("El valor obtenido con las asignaciones es: " + str(valor))
        count +=1

df1 = pd.DataFrame({0: [2, 4, 8, 0],
    1: [2, 1, 2, 3],
    2: [9, 2, 1, 7],
    3: [8, 2, 1, 4]},
    index=[0, 1, 2, 3]
   )
df2 = pd.DataFrame({0: [2, 4, 8, 0],
    1: [2, 1, 2, 3]},
    index=[0, 1, 2, 3]
   )

print(df1.to_string())

asignacion_tareas(df1)

Con el df1 obtengo

   0  1  2  3
0  2  2  9  8
1  4  1  2  2
2  8  2  1  1
3  0  3  7  4
---------------
Solucion 0:
Las asignaciones por admin son: [3L, 1L, 0L, 2L]
El valor obtenido con las asignaciones es: 24

Con el df2 obtengo

   0  1
0  2  2
1  4  1
2  8  2
3  0  3
---------------
Solucion 0:
Las asignaciones por admin son: [1L, 0L]
El valor obtenido con las asignaciones es: 6
0

Añado una respuesta mejor, ya que no acabo de entender el codigo y para no inventar la rueda. He investigado algo mas y he visto que el Algoritmo Hungaro o Munkres para asignacion de tareas consiste en lo siguiente.

Se construye una matriz de costes de tal manera que: Las tareas estan representadas en las columnas de la matriz Los recursos estan representados en las filas En cada celda aparece el coste de asignar la tarea en la columna x al recurso y El objetivo es minimzar la suma total de asignar la tarea x al recurso y

Es un problema de asignacion de suma lineal ("linear sum assignment problem"), que resuelve la función de la libreria de python scipy:

scipy.optimize.linear_sum_assignment

https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

La documentacion que explica el algoritmo esta aqui (en inglés): http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html

Asi mismo hay una implementación completa en Python aquí:

https://github.com/bmc/munkres

Por ejemplo, usando scipy:

import numpy as np
from scipy.optimize import linear_sum_assignment

cost = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]])

row_ind, col_ind = linear_sum_assignment(cost)

print "Solucion"
print col_ind

print "Coste"
print cost[row_ind, col_ind].sum()

Resultado

[[4 1 3]
 [2 0 5]
 [3 2 2]]
Solucion
[1 0 2]
Coste
5
2
  • No debes agregar varias respuestas, realiza solo una o editala, saludos.
    – Jorgesys
    Commented el 10 dic. 2019 a las 15:14
  • Tienes razon, pero queria agregar mas informacion sin borrar la que el usuario marco como correcta. Como lo hago?
    – J Campos
    Commented el 11 dic. 2019 a las 9:14

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.