Tengo buenas y malas noticias para ti. La mala noticia es que su solución ya es óptima. ¡La buena noticia es que podemos probarlo, usando tecnología realmente genial!
En lugar de alimentar el problema al gran martillo de recocido simulado como lo hice la última vez, vamos a alimentarlo al martillo aún más grande de los solucionadores de restricciones pseudo-booleanos . Un solucionador PB es una generalización de un solucionador SAT; se necesita un conjunto de variables booleanas (por ejemplo, [matemáticas] x_1, x_2, x_3 \ in \ {0, 1 \} [/ matemáticas]) y un sistema lineal en estas variables con coeficientes enteros (por ejemplo, [matemáticas] x_1 – x_3 \ ge 0 [/ math], [math] x_2 – x_3 \ ge 0 [/ math], [math] x_1 + x_2 – x_3 \ le 1 [/ math]) e intenta optimizar una función lineal dada de las variables ( diga [math] 2 \ cdot x_1 – x_3 [/ math]) dadas estas restricciones.
Vamos a utilizar clasp, un solucionador PB gratuito y de código abierto:
http://www.cs.uni-potsdam.de/clasp/
(Este código debería funcionar con cualquier solucionador PB que acepte el formato OPB estándar; otro es MiniSat +).
- ¿Cómo es participar en el REU de verano de Matemáticas en Emory?
- ¿Existen problemas matemáticos en los que existe una o más soluciones probables, pero aún no se han encontrado?
- ¿Por qué los fractales son tan comunes en la naturaleza?
- ¿Es el sistema numérico chino realmente más lógico que el hindú-árabe? ¿Es posible que el sistema chino reemplace al hindú-árabe de la misma manera que el sistema hindú-árabe reemplazó al sistema romano?
- ¿Qué pasaría si las matemáticas nunca hubieran sido inventadas?
Aquí hay un script de Python que genera las variables y restricciones que representan este problema de programación de golf, ejecuta el cierre para calcular el horario óptimo e interpreta la salida en un formato que podamos leer. Funciona durante aproximadamente 8 segundos y calcula el siguiente horario óptimo, en el que 27 de los 36 pares de jugadores opuestos juegan juntos (como su primera solución):
AB12 CD34 EF56
AC26 DE13 BF45
AE35 BC16 DF24
#!/usr/bin/python from subprocess import Popen, PIPE from tempfile import NamedTemporaryFile # Define the variables we're going to use. num_vars = 0 def new_var(): global num_vars num_vars += 1 return 'x' + str(num_vars) plays = {(p, r, g): new_var() for p in xrange(12) for r in xrange(3) for g in xrange(3)} constraints = [] # together_game[p1, p2, r, g] = plays[p1, r, g] AND plays[p2, r, g]. together_game = {} for p1 in xrange(12): for p2 in xrange(p1 + 1, 12): for r in xrange(3): for g in xrange(3): together_game[p1, p2, r, g] = new_var() constraints += [ ([[1, plays[p1, r, g]], [-1, together_game[p1, p2, r, g]]], '>=', 0), ([[1, plays[p2, r, g]], [-1, together_game[p1, p2, r, g]]], '>=', 0), ([[-1, plays[p1, r, g]], [-1, plays[p2, r, g]], [1, together_game[p1, p2, r, g]]], '>=', -1), ] # together[p1, p2] = exists r, g: together_game[p1, p2, r, g]. together = {} for p1 in xrange(6): for p2 in xrange(6, 12): together[p1, p2] = new_var() for r in xrange(3): for g in xrange(3): constraints.append( ([[1, together[p1, p2]], [-1, together_game[p1, p2, r, g]]], '>=', 0)) constraints.append( ([[1, together_game[p1, p2, r, g]] for r in xrange(3) for g in xrange(3)] + [[-1, together[p1, p2]]], '>=', 0)) # Each player plays in one game per round. for r in xrange(3): for p in xrange(12): constraints.append( ([[1, plays[p, r, g]] for g in xrange(3)], '=', 1)) # Assume each game has two players from each team. for r in xrange(3): for g in xrange(3): for t in xrange(2): constraints.append( ([[1, plays[p, r, g]] for p in xrange(t*6, (t + 1)*6)], '=', 2)) # Team members shouldn't play with each other more than once. for t in xrange(2): for p1 in xrange(t*6, (t + 1)*6): for p2 in xrange(p1 + 1, (t + 1)*6): constraints.append( ([[-1, together_game[p1, p2, r, g]] for r in xrange(3) for g in xrange(3)], '>=', -1)) # No one should play anyone else in all three rounds. for p1 in xrange(6): for p2 in xrange(6, 12): constraints.append( ([[-1, together_game[p1, p2, r, g]] for r in xrange(3) for g in xrange(3)], '>=', -2)) # Without loss of generality, round 1 is AB12 CD34 EF56. for g in xrange(3): for t in xrange(2): for p in xrange(t*6 + g*2, t*6 + (g + 1)*2): constraints.append( ([[1, plays[p, 0, g]]], '=', 1)) # Maximize the number of pairs of opposing players that play with each other. opt = [[-1, together[p1, p2]] for p1 in xrange(6) for p2 in xrange(6, 12)] # Run PB solver. f = NamedTemporaryFile() print >>f, '* #variable=', num_vars, '#constraint=', len(constraints) print >>f, 'min:', ' '.join(' '.join(str(s) for s in c) for c in opt), ';' for lhs, op, rhs in constraints: print >>f, ' '.join(' '.join(str(s) for s in c) for c in lhs), op, rhs, ';' f.flush() pr = Popen(['clasp', f.name], stdout=PIPE) # Interpret the output. s = set() for l in iter(pr.stdout.readline, ''): print l, if l.startswith('v '): s.update(l.split()[1:]) pr.wait() for r in xrange(3): for g in xrange(3): print ''.join("ABCDEF123456"[p] for p in xrange(12) if plays[p, r, g] in s), print 