Encontrar el mínimo de la matriz

Question

Considere lo siguiente $3\times 3$ matriz.

$\begin{pmatrix}3&6&9\\ 2& 4 &8\\ 1 &5& 7 \end{pmatrix}$

Necesito encontrar la combinación de tres números donde cada número proviene de una única columna y fila. Por ejemplo $3,6,8$ no es lo que quiero como $3$ y $6$ son de la misma fila.

$6,4,7$ tampoco es correcto porque $6$ y $4$ son de las mismas columnas.

$3,4,7$ es válida ya que cada número proviene de una columna y una fila diferentes.

Lo siguiente que quiero, es encontrar la combinación cuya suma sea mínima comparada con la suma de todas las demás combinaciones posibles. Por ejemplo $3,4,7$ será la respuesta final si $3+4+7 = \min$ . ¿Cómo puedo encontrar esto para $n \times n$ ¿Matriz?

Answer 1

Esto se conoce como el problema de asignación . El algoritmo más conocido para resolverlo es el Algoritmo húngaro .

Answer 2

Por la respuesta anterior, este es un lineales el problema de la asignación. Aquí está una manera simple de resolver (no necesariamente el más rápido de ejecutar si n es muy grande).

Si usted tiene MATLAB, puede descargar YALMIP de forma gratuita.

Sea a = n por n de la matriz de interés.

x = binvar(n,n,'full') % x define a ser un no necesariamente simétrica de n por n de la matriz de ceros y unos, que es la matriz de la optimización de las variables que especifica que las entradas son para ser elegido (1 si se selecciona, 0 si no).

optimize([sum(x,2) == 1, sum(x,1) == 1],sum(sum(x.*A))) % Soluciona el problema

Tenga en cuenta que en optimizar el comando,

sum(x,2) == 1 constrains row sums to 1
sum(x,1) == 1 constrains column sums to 1
sum(sum(x.*A)) is the objective to be minimized
value(x) provides the optimal selection matrix
value(sum(sum(x.*A)))) provides the optimal score.

Por su ejemplo

n = 3
A = [3 6 8;3 4 8;2 5 7]

el valor de(x) es

 1     0     0

 0     1     0

 0     0     1

Óptimo puntaje es de 14.

Si usted desea maximizar la suma, se podría cambiar el optimizar el comando para optimizar([sum(x,2) == 1, suma(x,1) == 1], sum(sum(x.*A))) que minimiza el negativo de la suma.

He aquí un azar de 5 por 5 matriz:

0.8147    0.0975    0.1576    0.1419    0.6557
0.9058    0.2785    0.9706    0.4218    0.0357
0.1270    0.5469    0.9572    0.9157    0.8491
0.9134    0.9575    0.4854    0.7922    0.9340
0.6324    0.9649    0.8003    0.9595    0.6787

Óptima (la producción de suma mínima) x es

0 1 0 0 0

0 0 0 0 1

1 0 0 0 0

0 0 1 0 0

0 0 0 1 0

Óptimo puntaje es 1.7051.