En la web del Clay Mathematics Institute se encuentra el desafío de los Millenium Prizes, unos premios millonarios para quienes resuelvan los llamados problemas del milenio.

Me ha llamado la atención el apartado P vs NP (http://www.claymath.org/millenium-problems/p-vs-np-problem), donde se expone el siguiente ejemplo de problema tipo NP:

  Supongamos que estamos organizando el hospedaje de cuatrocientos estudiantes universitarios. Sólo contamos con cien plazas. Para complicar las cosas, hay una lista de estudiantes incompatibles que no quieren compartir hospedaje. Por tanto, debemos encontrar una lista de cien, de entre los cuatrocientos estudiantes, que no contenga ninguna de las parejas prohibidas.

No parece un problema difícil, puesto que, dada una lista de cien, es relativamente fácil comprobar si cumple o no los requisitos de incompatibilidad. Sin embargo, encontrar una lista de cien que cumpla los requisitos es bastante más complicado. Como punto de partida, el número de combinaciones posibles sería: 400 x 399 x 398 … x 301. Un número mayor que el total de átomos en el universo.

He aquí la definición de problema NP: verificar una solución propuesta es fácil; encontrar una solución válida es no computable.

Se me ocurre un algoritmo para tratar de resolver el problema concreto propuesto:

Definiciones:
I: lista de lista de incompatibilidades, formada por el par (I1, I2)
D: lista de estudiantes disponibles; se inicializa con los 400 estudiantes
S: solución provisional; es una lista de estudiantes compatibles; si llega a 100 elementos, el problema está resuelto


Algoritmo:
1. Ordenar los pares en I de forma creciente (I1 < I2)
2. Ordenar la propia lista I de forma creciente, primero por I1 y después por I2
3. Iniciar procedimiento recursivo por estudiante n = 1
4. Quitar n de D
5. Quitar de D todos los estudiantes incompatibles (> n) (coste lineal recorriendo I).
6. Si D está vacía, retroceder a la iteración anterior
7. Tomar el menor número de D, que será el nuevo n
8. Añadir n a S
9. Si cardinal(S) = 100, hemos encontrado una solución válida; salir de la recursión
10. Llamar a la función que empieza en 4 con el n actual
11. Si no hemos salido con éxito (punto 9), es que la recursión ha fallado; por tanto:
11.1. Quitar n de S
11.2. Volver a poner en D las incompatibilidaes de n (> n)
11.3. Ir al punto 7

El algoritmo es razonablemente eficaz para encontrar una única solución, y es fácilmente optimizable con algunas heurísticas. Sin embargo, es completamente inútil en caso de que se desee encontrar todas las posibles soluciones, especialmente si la lista de incompatibilidades es pequeña.

Anuncios