LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

El método húngaro es un algoritmo de optimización combinatoria que resuelve el problema de asignación en el tiempo polinomial y anticipó los métodos primigenio dual posteriores . Fue desarrollado y publicado en 1955 por Harold Kuhn , quien le dio el nombre de "método húngaro" porque el algoritmo se basó en gran medida en los trabajos anteriores de dos matemáticos húngaros : Dénes Kőnig y Jenő Egerváry . ^[1] [2]

James Munkres revisó el algoritmo en 1957 y observó que es (fuertemente) polinomial . ^[3] Desde entonces, el algoritmo se ha conocido también como el algoritmo de Kuhn-Munkres o el algoritmo de asignación de Munkres . La complejidad temporal del algoritmo original fue$${\ displaystyle O (n ^ {4})}, sin embargo, Edmonds y Karp , e independientemente Tomizawa notaron que se puede modificar para lograr un$${\ displaystyle O (n ^ {3})}tiempo de ejecución. Uno de los más populares$${\ displaystyle O (n ^ {3})}Las variantes es el algoritmo de Jonker-Volgenant. ^[4] Ford y Fulkerson extendieron el método a problemas generales de transporte. ^{[ cita requerida ]} En 2006, se descubrió que Carl Gustav Jacobi había resuelto el problema de la asignación en el siglo XIX, y la solución se había publicado póstumamente en 1890 en latín. 

El problema [ editar ]

Artículo principal: Problema de asignación

Ejemplo [ editar ]

En este ejemplo simple hay tres trabajadores: Armond, Francine y Herbert. Uno de ellos tiene que limpiar el baño, otro barre los pisos y el tercero lava las ventanas, pero cada uno de ellos exige un pago diferente para las diversas tareas. El problema es encontrar la forma más económica de asignar los trabajos. El problema se puede representar en una matriz de los costos de los trabajadores que realizan los trabajos. Por ejemplo:

	Baño limpio	Barrer pisos	Lavar ventanas
Armond	$ 2	$ 3	$ 3
Francine	$ 3	$ 2	$ 3
Herbert	$ 3	$ 3	$ 2

El método húngaro, cuando se aplica a la tabla anterior, daría el costo mínimo: esto es $ 6, que se logra al hacer que Armond limpie el baño, Francine limpie los pisos y Herbert lave las ventanas.

Formulación de la matriz [ editar ]

Hay dos formas de formular el problema: como una matriz o como un gráfico bipartito .

En la formulación de la matriz, se nos da una matriz no negativa n × n , donde el elemento en la i -ésima fila y j -ª columna representa el costo de asignar el trabajo j -ésimo al i -ésimo trabajador. Tenemos que encontrar una asignación de los trabajos a los trabajadores, de modo que cada trabajo se asigne a un trabajador y cada trabajador se le asigne un trabajo, de tal manera que el costo total de la asignación sea mínimo.

Si el objetivo es encontrar la asignación que arroja el costo máximo , el problema puede modificarse para que se ajuste a la configuración reemplazando cada costo con el costo máximo restado por el costo.

Bigraph formulación [ editar ]

El algoritmo es más fácil de describir si formulamos el problema utilizando un gráfico bipartito. Contamos con un completo gráfico bipartito. $${\ displaystyle G = (S, T; E)} con $${\ displaystyle n} vértices de trabajadores ($${\ displaystyle S}) y $${\ displaystyle n} vértices de trabajo ($${\ displaystyle T}), y cada borde tiene un costo no negativo $${\ displaystyle c (i, j)}. Queremos encontrar una combinación perfecta con un costo total mínimo.

El algoritmo en términos de gráficos bipartitos [ editar ]

Llamemos a una función $${\ displaystyle y: (S \ cup T) \ to \ mathbb {R}}un potencial si$${\ displaystyle y (i) + y (j) \ leq c (i, j)} para cada $${\ displaystyle i \ en S, j \ en T}. El valor del potencial.$${\ displaystyle y} es la suma del potencial sobre todos los vértices: $${\ displaystyle \ sum _ {v \ en S \ cup T} y (v)}.

Es fácil ver que el costo de cada coincidencia perfecta es al menos el valor de cada potencial: el costo total de la coincidencia es la suma de los costos de todos los bordes; el costo de cada borde es al menos la suma de potenciales de sus puntos finales; como la coincidencia es perfecta, cada vértice es un punto final de exactamente un borde; por lo tanto, el costo total es al menos el potencial total.

El método húngaro encuentra una coincidencia perfecta y un potencial tal que el costo coincidente sea igual al valor potencial. Esto prueba que ambos son óptimos. De hecho, el método húngaro encuentra una combinación perfecta de bordes apretados : un borde$${\ displaystyle ij} Se llama apretado por un potencial $${\ displaystyle y} Si $${\ displaystyle y (i) + y (j) = c (i, j)}. Denotemos el subgrafo de bordes apretados por$${\ displaystyle G_ {y}}. El costo de una combinación perfecta en$${\ displaystyle G_ {y}} (si hay uno) es igual al valor de $${\ displaystyle y}.

Durante el algoritmo mantenemos un potencial. $${\ displaystyle y}y una orientación de$${\ displaystyle G_ {y}} (denotado por $${\ displaystyle {\ overrightarrow {G_ {y}}}}) que tiene la propiedad de que los bordes orientados de T a S forman una M coincidente . Inicialmente, y es 0 en todas partes, y todos los bordes están orientados de S a T (por lo que M está vacío). En cada paso, modificamos y para que su valor aumente, o modificamos la orientación para obtener una coincidencia con más bordes. Mantenemos el invariante de que todos los bordes de M están ajustados. Hemos terminado si M es una combinación perfecta.

En un paso general, vamos $${\ displaystyle R_ {S} \ subseteq S} y $${\ displaystyle R_ {T} \ subseteq T}Ser los vértices no cubiertos por M (así$${\ displaystyle R_ {S}}consiste en los vértices en S sin borde entrante y$${\ displaystyle R_ {T}}consiste en los vértices en T sin borde saliente). Dejar$${\ displaystyle Z} ser el conjunto de vértices alcanzables en $${\ displaystyle {\ overrightarrow {G_ {y}}}} desde $${\ displaystyle R_ {S}}Por un camino dirigido solo siguiendo bordes que estén apretados. Esto se puede calcular por primera búsqueda de amplitud .

Si $${\ displaystyle R_ {T} \ cap Z} es no vacío, luego invierta la orientación de un camino dirigido en $${\ displaystyle {\ overrightarrow {G_ {y}}}} desde $${\ displaystyle R_ {S}} a $${\ displaystyle R_ {T}}. Por lo tanto, el tamaño de la correspondencia correspondiente aumenta en 1.

Si $${\ displaystyle R_ {T} \ cap Z} está vacío, entonces vamos

$${\ displaystyle \ Delta: = \ min \ {c (i, j) -y (i) -y (j): i \ en Z \ cap S, j \ en T \ setminus Z \}.}

$${\ displaystyle \ Delta} es positivo porque no hay bordes apretados entre $${\ displaystyle Z \ cap S} y $${\ displaystyle T \ setminus Z}. Aumentar y por$${\ displaystyle \ Delta} en los vértices de $${\ displaystyle Z \ cap S}y disminuir y por$${\ displaystyle \ Delta} en los vértices de $${\ displaystyle Z \ cap T}. La y resultante es todavía un potencial, y aunque la gráfica$${\ displaystyle G_ {y}}cambios, todavía contiene M (ver las siguientes subsecciones). Nos orientamos los nuevos bordes de S a T . Por la definición de$${\ displaystyle \ Delta}el conjunto Z de vértices alcanzables desde$${\ displaystyle R_ {S}} aumentos (tenga en cuenta que el número de bordes ajustados no necesariamente aumenta).

Repetimos estos pasos hasta que M sea ​​una coincidencia perfecta, en cuyo caso da una asignación de costo mínimo. El tiempo de ejecución de esta versión del método es$${\ displaystyle O (n ^ {4})}: M se aumenta n veces, y en una fase donde M no se modifica, hay como máximo n cambios potenciales (ya que Z aumenta cada vez). El tiempo suficiente para un cambio potencial es$${\ displaystyle O (n ^ {2})}.

Prueba de que ajustar el potencial y deja M sin cambios [ editar ]

Para mostrar que cada borde en M permanece después de ajustar y , es suficiente para mostrar que para un borde arbitrario en M , ya sea tanto de sus puntos finales, o ninguno de ellos, están en Z . Con este fin let vu ser una ventaja en M de T a S . Es fácil ver que si v está en Z , u también debe estarlo, ya que cada borde en M está apretado. Ahora supongamos, hacia la contradicción, que$${\ displaystyle u \ en Z} pero $${\ displaystyle v \ notin Z}. tú mismo no puedes estar en$${\ displaystyle R_ {S}}porque es el punto final de un borde coincidente, por lo que debe haber algún camino dirigido de bordes ajustados desde un vértice en $${\ displaystyle R_ {S}}a u . Esta ruta debe evitar v , ya que se supone que no está en Z , por lo que el vértice que precede inmediatamente a u en esta ruta es otro vértice$${\ displaystyle v '\ en T}. $${\ displaystyle v'u}es un borde estrecho de T a S y está así en M . Pero luego M contiene dos aristas que comparten el vértice u , lo que contradice el hecho de que M es una coincidencia. Así, cada borde en M tiene cualquiera de los dos puntos finales o ni punto final en Z .

Prueba de que y sigue siendo un potencial [ editar ]

Para mostrar que y sigue siendo un potencial después de ser ajustado, basta con demostrar que ninguna ventaja tiene su potencial total aumentado más allá de su costo. Esto ya está establecido para bordes en M por el párrafo anterior, por lo que considera un borde arbitrario uv de S a T . Si$${\ displaystyle y (u)} se incrementa en $${\ displaystyle \ Delta}, entonces tambien $${\ displaystyle v \ en Z \ cap T}, en ese caso $${\ displaystyle y (v)} es disminuido por $${\ displaystyle \ Delta}, dejando el potencial total del borde sin cambios, o $${\ displaystyle v \ en T \ setminus Z}, en cuyo caso la definición de $${\ displaystyle \ Delta} garantiza que $${\ displaystyle y (u) + y (v) + \ Delta \ leq c (u, v)}. Así, y sigue siendo un potencial.

La interpretación de la matriz [ editar ]

Dado $${\ displaystyle n}trabajadores y tareas, y una matriz n × n que contiene el costo de asignar a cada trabajador a una tarea, encuentre la asignación de minimización de costos.

Primero, el problema está escrito en la forma de una matriz como se indica a continuación.

a1	a2	a3	a4
b1	b2	b3	b4
c1	c2	c3	c4
d1	d2	d3	d4

donde a, b, c y d son los trabajadores que tienen que realizar las tareas 1, 2, 3 y 4. a1, a2, a3, a4 indican las penalizaciones incurridas cuando el trabajador "a" realiza la tarea 1, 2, 3, 4 respectivamente . Lo mismo se aplica a los otros símbolos también. La matriz es cuadrada, por lo que cada trabajador puede realizar una sola tarea.

Paso 1

Luego realizamos operaciones de fila en la matriz. Para ello, el más bajo de todos una _i (i perteneciente a 1-4) se toma y se resta de cada elemento en la fila. Esto llevará a al menos un cero en esa fila (obtenemos ceros múltiples cuando hay dos elementos iguales que también son los más bajos en esa fila). Este procedimiento se repite para todas las filas. Ahora tenemos una matriz con al menos un cero por fila. Ahora tratamos de asignar tareas a los agentes de modo que cada agente esté haciendo solo una tarea y la penalización incurrida en cada caso sea cero. Esto se ilustra a continuación.

0	a2 '	a3 '	a4 '
b1 '	b2 '	b3 '	0
c1 '	0	c3 '	c4 '
d1 '	d2 '	0	d4 '

Los ceros que se indican como 0 son las tareas asignadas.

Paso 2

A veces puede resultar que la matriz en esta etapa no se pueda usar para asignar, como es el caso de la matriz a continuación.

0	a2 '	a3 '	a4 '
b1 '	b2 '	b3 '	0
0	c2 '	c3 '	c4 '
d1 '	0	d3 '	d4 '

En el caso anterior, no se puede hacer ninguna asignación. Tenga en cuenta que la tarea 1 se realiza de manera eficiente tanto por el agente a como por el c. A ambos no se les puede asignar la misma tarea. También tenga en cuenta que nadie hace la tarea 3 de manera eficiente. Para superar esto, repetimos el procedimiento anterior para todas las columnas (es decir, el elemento mínimo en cada columna se resta de todos los elementos en esa columna) y luego verificamos si es posible una asignación.

En la mayoría de las situaciones, esto dará el resultado, pero si aún no es posible, debemos continuar.

Paso 3

Todos los ceros en la matriz deben cubrirse marcando el menor número posible de filas y / o columnas. El siguiente procedimiento es una forma de lograr esto:

Primero, asigne tantas tareas como sea posible.

• La fila 1 tiene un cero, por lo que se asigna. El 0 en la fila 3 está tachado porque está en la misma columna.
• La fila 2 tiene un cero, por lo que se asigna.
• El único cero de la fila 3 se ha tachado, por lo que no se asigna nada.
• La fila 4 tiene dos ceros sin cruzar. Cualquiera de los dos puede asignarse, y el otro cero está tachado.

Alternativamente, se puede asignar el 0 en la fila 3, lo que hace que el 0 en la fila 1 se cruce en su lugar.

0 '	a2 '	a3 '	a4 '
b1 '	b2 '	b3 '	0 '
0	c2 '	c3 '	c4 '
d1 '	0 '	0	d4 '

Ahora a la parte de dibujo.

• Marque todas las filas que no tienen asignaciones (fila 3).
• Marque todas las columnas que tienen ceros en las filas recién marcadas (columna 1).
• Marque todas las filas que tengan asignaciones en columnas recién marcadas (fila 1).
• Repita para todas las filas no asignadas.

×
0 '	a2 '	a3 '	a4 '	×
b1 '	b2 '	b3 '	0 '
0	c2 '	c3 '	c4 '	×
d1 '	0 '	0	d4 '

Ahora dibuja líneas a través de todas las columnas marcadas y filas sin marcar .

×
0 '	a2 '	a3 '	a4 '	×
b1 '	b2 '	b3 '	0 '
0	c2 '	c3 '	c4 '	×
d1 '	0 '	0	d4 '

La descripción detallada mencionada anteriormente es solo una forma de dibujar el número mínimo de líneas para cubrir todos los 0s. Otros métodos funcionan también.

Etapa 4

De los elementos que quedan, encuentra el valor más bajo. Resta esto de cada elemento no marcado y agrégalo a cada elemento cubierto por dos líneas.

Repita los pasos 3 a 4 hasta que sea posible una asignación; esto es cuando el número mínimo de líneas utilizadas para cubrir todos los 0s es igual a max (número de personas, número de asignaciones), asumiendo que las variables ficticias (generalmente el costo máximo) se utilizan para completar cuando el número de personas es mayor que El número de asignaciones.

Básicamente encuentras el segundo costo mínimo entre las opciones restantes. El procedimiento se repite hasta que pueda distinguir entre los trabajadores en términos de menor costo.

secuencia de Prüfer (también el código de Prüfer o los números de Prüfer) de un árbol etiquetado es una secuencia única asociada con el árbol. La secuencia de un árbol en n vértices tiene una longitud n  - 2, y puede generarse mediante un algoritmo iterativo simple. Heinz Prüfer utilizó las secuencias de Prüfer por primera vez para probar la fórmula de Cayley en 1918.

Algoritmo para convertir un árbol en una secuencia de Prüfer [ editar ]

Uno puede generar la secuencia Prüfer de un árbol etiquetado eliminando iterativamente los vértices del árbol hasta que solo queden dos vértices. Específicamente, considere un árbol T etiquetado con vértices {1, 2, ..., n }. En el paso i , retire la hoja con la etiqueta más pequeña y configure el elemento i th de la secuencia de Prüfer para que sea la etiqueta del vecino de esta hoja.

La secuencia de Prüfer de un árbol etiquetado es única y tiene una longitud n  - 2.

Ejemplo [ editar ]

Un árbol etiquetado con secuencia de Prüfer {4,4,4,5}.

Considere el algoritmo anterior ejecutado en el árbol que se muestra a la derecha. Inicialmente, el vértice 1 es la hoja con la etiqueta más pequeña, por lo que se elimina primero y 4 se coloca en la secuencia de Prüfer. Los vértices 2 y 3 se eliminan a continuación, por lo que 4 se agregan dos veces más. Vertex 4 ahora es una hoja y tiene la etiqueta más pequeña, por lo que se elimina y adjuntamos 5 a la secuencia. Nos quedan solo dos vértices, así que nos detenemos. La secuencia del árbol es {4,4,4,5}.

Algoritmo para convertir una secuencia de Prüfer en un árbol [ editar ]

Sea {a[1], a[2], ..., a[n]}una secuencia de Prüfer:

El árbol tendrá n+2nodos, numerados desde 1hasta n+2. Para cada nodo, establezca su grado en el número de veces que aparece en la secuencia más 1. Por ejemplo, en pseudocódigo:

 Convert-Prüfer-to-Tree ( a )
 1 n ← longitud [ a ]
 2 T ← una gráfica con n + 2 nodos aislados, numerados de 1 a  n + 2
 3 grados ← una matriz de enteros
 4 para cada nodo i en T 
 5      do  grado [ i ] ← 1
 6 para cada valor i en un grado de 
 7      do  [ i ] ← grado [ i ] + 1

Luego, para cada número en la secuencia a[i], encuentre el primer nodo (con el número más bajo) j, con un grado igual a 1, agregue el borde (j, a[i])al árbol y disminuya los grados de jy a[i]. En pseudocódigo:

8 para cada valor i en un 
 9      para cada nodo j en T 
10           si el  grado [ j ] = 1
11              luego inserte el borde [ i , j ] en T 
12                   grado [ i ] ← grado [ i ] - 1
13                   grado [ j ] ← grado [ j ] - 1
14                   descanso

Al final de este bucle quedarán dos nodos con grado 1 (llámalos u, v). Por último, agregue el borde (u,v)al árbol. ^[2]

15 u ← v ← 0
16 para cada nodo i en T 
17      si el  grado [ i ] = 1
18          entonces  si  u = 0
19              luego  u ← i 
20              else  v ← i 
21                   break 
22 Inserte el borde [ u , v ] en T 
23 grados [ u ] ← grado [ u ] - 1
24 grados [ v ] ← grado [ v ] - 1
25 retorno  T

Fórmula de Cayley [ editar ]

La secuencia de Prüfer de un árbol etiquetado en n vértices es una secuencia única de longitud n  - 2 en las etiquetas 1 a n . Para una determinada secuencia S de longitud n -2 en las etiquetas 1 a n , hay un único árbol de marcado cuya secuencia de Prüfer es S .

La consecuencia inmediata es que las secuencias de Prüfer proporcionan una bijección entre el conjunto de árboles etiquetados en n vértices y el conjunto de secuencias de longitud n –2 en las etiquetas 1 a n . El último conjunto tiene tamaño n ^n −2 , por lo que la existencia de esta bijección prueba la fórmula de Cayley , es decir, que hay n ^n −2 árboles etiquetados en n vértices.

Otras aplicaciones ^[3] [ editar ]

• La fórmula de Cayley puede fortalecerse para probar la siguiente afirmación:

El número de árboles que abarcan en un gráfico completo $${\ displaystyle K_ {n}} con un grado $${\ displaystyle d_ {i}} especificado para cada vértice $${\ displaystyle i}es igual al coeficiente multinomial

$${\ displaystyle {\ binom {n-2} {d_ {1} -1, \, d_ {2} -1, \, \ dots, \, d_ {n} -1}} = {\ frac {(n -2)!} {(D_ {1} -1)! (D_ {2} -1)! \ Cdots (d_ {n} -1)!}}.}

La prueba sigue observando que en el número de secuencia de Prüfer $${\ displaystyle i} aparece exactamente $${\ displaystyle (d_ {i} -1)}veces.

• La fórmula de Cayley se puede generalizar: un árbol etiquetado es de hecho un árbol de expansión del gráfico completo etiquetado . Al colocar restricciones en las secuencias de Prüfer enumeradas, métodos similares pueden dar el número de árboles que abarcan un gráfico bipartito completo . Si G es el gráfico bipartito completo con los vértices 1 a n ₁ en una partición y los vértices n ₁  + 1 a n en la otra partición, el número de árboles de expansión etiquetados de G es$${\ displaystyle n_ {1} ^ {n_ {2} -1} n_ {2} ^ {n_ {1} -1}}, donde n ₂ = n  -  n ₁ .
• La generación de secuencias de Prüfer aleatorias distribuidas uniformemente y su conversión en los árboles correspondientes es un método sencillo para generar árboles etiquetados aleatorios distribuidos uniformemente.