Algoritmo: encuentra la resta mínima entre la suma de dos matrices

Question

Ahora estoy trabajando y haciendo muchos ejercicios de algoritmo. Aquí está mi problema:

---

Dados dos matrices: un y b con la misma longitud, el tema es hacer | suma (a) -sum (b) | mínimo, al intercambiar elementos entre a y b.

---

Aquí es mi aunque:

asumir que cambiar una [i] y b [j], ajuste Delt = suma (a) - suma (b), x = a [i] -b [j]
luego Delt2 = suma (a) -a [i] + b [j] - (suma (b) -b [j] + a [i]) = Delt - 2 * x,
luego el cambio = | Delt | - | Delt2 |, que es proporcional a | Delt |^2 - | Delt2 |^2 = 4 * x * (Delt-x),

Basándose en la idea anterior Tengo el siguiente código:

---

Delt = sum(a) - sum(b); 
done = false; 
while(!done) 
{ 
    done = true; 
    for i = [0, n) 
    { 
     for j = [0,n) 
     { 
      x = a[i]-b[j]; 
      change = x*(Delt-x); 
      if(change >0) 
      { 
       swap(a[i], b[j]); 
       Delt = Delt - 2*x; 
       done = false; 
      } 
     } 
    } 
} 

---

Sin embargo, ¿alguien tiene una solución mucho mejor? Si tienes, por favor dímelo y te estaría muy agradecido.

Answer 1

Este problema es básicamente el problema de optimización para Partition Problem con una restricción adicional de partes iguales. Demostraré que agregar esta restricción no facilita el problema.

NP-Hardness prueba:
asumir que hubo un algoritmo A que resuelve este problema en tiempo polinómico, podemos resolver el Partition-Problem en tiempo polinómico.

Partition(S): 
for i in range(|S|): 
    S += {0} 
    result <- A(S\2,S\2) //arbitrary split S into 2 parts 
    if result is a partition: //simple to check, since partition is NP. 
    return true. 
return false //no partition 

Corrección:
Si hay una partición denotan como (S1, S2) [asumir S2 tiene más elementos], en iteración | S2 | - | S1 | [es decir. cuando se agrega | S2 | - | S1 | ceros]. La entrada a A contendrá suficientes ceros para que podamos devolver dos matrices de igual longitud: S2, S1 + {0,0, ..., 0}, que será una partición de S, y el algoritmo arrojará verdadero.
Si el algoritmo arroja verdadero, y la iteración k, teníamos dos matrices: S2, S1, con el mismo número de elementos y valores iguales. eliminando k ceros de las matrices, obtenemos una partición en la S original, por lo que S tenía una partición.

polinómica:
asumen A toma P(n) tiempo, el algoritmo produjimos se llevará a n*P(n) tiempo, que también es polinómica.

Conclusión:
Si este problema es solveable en tiempo polinómico, también lo hace la Partion-problema, y ​​por lo tanto P = NP. basado en esto: este problema es NP-Hard.

Como este problema es NP-Hard, para una solución exacta probablemente necesite un algoritmo exponencial. Uno de ellos es sencilla backtracking [lo dejo como ejercicio para el lector para implementar una solución retroceso]

EDITAR: como se ha mencionado por @jpalecek: simplemente creando una reducción: S->S+(0,0,...,0) [k veces 0], una puede demostrar directamente la dureza NP por reducción. el polinomio es trivial y la corrección es muy similar a la prueba de corrección de la parte anterior: [si hay una partición, es posible agregar ceros de 'equilibrio'; la otra dirección es simplemente recortar esos ceros]

Answer 2

Apenas un comentario. A través de todo este intercambio, básicamente puede organizar los contenidos de ambas matrices a su gusto. Por lo tanto, no es importante en qué matriz están los valores al inicio.

No puedo hacerlo en mi cabeza, pero estoy bastante seguro de que hay una solución constructiva. Creo que si los clasifica primero y luego los trata según alguna regla. Algo a lo largo de las líneas If value > 0 and if sum(a)>sum(b) then insert to a else into b