Saltar al contenido

Relajaciones semidefinidas en tableros de juguete: un resultado negativo

En tableros de juguete generados, una relajación semidefinida del emparejamiento de aristas queda certificada limpia en tres tableros 5x5, indecisa en uno e inexacta en otro; no cabe en 16x16 y no dio ninguna lectura en 6x6. Su forma de rango bajo sí encuentra soluciones, pero como una búsqueda aleatoria que el recocido simple supera en coste. Nada de esto es un avance en Eternity II.

por Raphaël Anjou

experimentocallejón sin salidamedidorefutadoMétodos exactosReducir la búsquedaBúsqueda localActualizado 2026-11-14
Reproducirestocástico: no se reproduce exactamente; el tablero es verificablerevalida un tablero guardadoPresupuesto: 5x5 convex solves 400 to 1,100 s each; 6x6 low-rank batches 30 CPU minutes per start
Hardware y ejecución
Ejecución nativaSolo CPU
0.28núcleos·hora
Núcleos
10
RAM
32 GiB
GPU
0
Máquina
10-core Apple M4 laptop, 32 GB; 14-core low-power x86 laptop; 8-core Apple M1 (annealing timings)
Presupuesto
5x5 convex solves 400 to 1,100 s each; 6x6 low-rank batches 30 CPU minutes per start
Inicio
toy boards from the project's painter, seeds 0 to 4; annealing and low-rank starts are random
Verificar el tablero guardado

estocástico: no se reproduce exactamente; el tablero es verificable

Esto verifica el tablero, no la búsqueda que lo produjo.

just experiments relaxation-small-boards

Solo pruebas de humo: una resolución convexa en 4x4, dos arranques de rango bajo en un juguete 5x5 y un recocido corto en un juguete 6x6, cada una en menos de dos minutos. El comando no reproduce ninguna tabla de esta página; los lotes 6x6 (30 minutos de CPU por arranque) y las resoluciones convexas 5x5 no están incluidos, y lo que debe reproducirse son los recuentos, no las trayectorias.

Seguir explorando

Citado por

Fuente de la páginaVer como Markdown