Algoritmo de Edmonds

Algoritmo de Edmonds

El objetivo del algoritmo de Edmonds es encontrar un acoplamiento perfecto (de máxima cardinalidad) en un problema de asignación.

El problema del acoplamiento es el siguiente:

Construya un gráfico bipartito (los elementos de la izquierda están conectados solo a los elementos de la derecha por arcos, los elementos rectos no tienen conexión de salida) de modo que los elementos de la izquierda son las máquinas y los elementos rectos son las tareas a realizar. Los arcos tienen capacidad 1 y costo según tabla de asignación. Si un flujo pasa a través de un borde (i, j), esto equivale a decir que la máquina i realiza la tarea j.
Para completar el gráfico bipartito y convertirlo en un problema de flujo, cada elemento de la izquierda está vinculado como un vértice terminal a una fuente ficticia. Cada elemento de la línea está vinculado como un vértice original a un pozo ficticio. Todos estos arcos tienen capacidad 1 y costo 0. Para resolver el problema de asignación, aplicamos un algoritmo de flujo máximo a costo mínimo al gráfico bipartito construido.
Algorithme d'edmonds couplage parfait problème d'affectation
Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: