El motor detrás del estudio de reparación: un único bucle componible de destrucción-reparación donde una variante es un cambio declarado sobre un padre, la IO y el scorer que comparte con el estudio DFS, un mapa de desajustes mantenido de forma incremental, y las definiciones de cada estadística que el estudio pone de relieve.
por Raphaël Anjou
Esta página es el aparato que hay detrás del estudio de reparación:
cómo está construido el motor, por qué una nueva variante es barata de añadir, y
qué significa cada número de los resultados. Es el gemelo deliberado de la
página de método del estudio DFS,
y se apoya en la misma biblioteca compartida: el tablero, el conjunto de
piezas, el único scorer canónico y el contrato de IO provienen todos de un crate
e2-core / e2-io común que usa también el estudio de backtracking. Un tablero
reparado y un tablero obtenido por backtracking se puntúan, por tanto, con el
código idéntico, que es lo que permite que los números de ambos estudios se
sitúen sobre un mismo eje.
Cada algoritmo del estudio es el mismo bucle de destrucción-reparación, parametrizado por cinco elecciones independientes:
Una variante es un pequeño registro que nombra esas cinco elecciones, junto con el padre del que deriva y una descripción en una línea del único cambio que añade. Añadir una variante consiste en añadir un registro al registro, sin código de bucle nuevo salvo que la idea sea una estrategia genuinamente nueva. La matriz de «qué se apila sobre qué» de la página de resultados se genera a partir de esas descripciones, de modo que no puede divergir del código que realmente se ejecutó.
Un backtracker construye un tablero desde la nada; un bucle de reparación siempre sostiene un tablero completo y lo edita. Las celdas que merece la pena atacar son las que tocan una arista rota, así que el motor mantiene un recuento vivo, por celda, de las aristas interiores rotas incidentes a ella. Colocar o retirar una pieza actualiza solo las aristas alrededor de esa única celda, nunca el tablero entero, de modo que un operador de destrucción guiado por conflictos puede preguntar «¿qué celdas tocan un desajuste?» sin volver a recorrer todo. La puntuación en curso se mantiene del mismo modo: cada colocación la ajusta según el puñado de costuras que cambiaron. Un rebarrido completo ocurre exactamente una vez, cuando se construye el tablero inicial; a partir de ahí el bucle es incremental. Esto es lo que hace posibles cientos de miles de iteraciones en sesenta segundos, y es la misma disciplina que la página teórica sobre ALNS describe como mantener la destrucción a un coste proporcional al hueco, no al tablero.
No se confía en la puntuación autodeclarada de ningún motor. La puntuación incremental del bucle es un dispositivo de rendimiento; el número publicado es siempre una repuntuación canónica fresca del tablero de salida, a través del mismo scorer que usan el sitio y el estudio DFS (aristas apareadas, no bordurías, adyacencias interiores, contadas a la derecha y hacia abajo por celda). Un test comprueba que la puntuación incremental y la puntuación canónica coinciden tras miles de colocaciones-y-retiradas aleatorias, de modo que se pueda confiar en que el camino rápido sigue la verdad en vez de apartarse de ella.
Para cada ejecución el motor registra, y los resultados lo transportan hasta la página:
La página también traza una curva de convergencia para unas pocas variantes representativas: la mejor puntuación obtenida hasta el momento, muestreada cada doscientas iteraciones, a medida que avanza una ejecución típica. Es la imagen más clara del estancamiento: la curva sube con fuerza, luego se aplana mientras el recuento de iteraciones sigue trepando.
Como el motor MRV del estudio DFS, el bucle de reparación de aquí está escrito primero para la claridad. El relleno voraz vuelve a recorrer el reservorio de piezas restantes por cada celda que rellena, en vez de mantener listas de candidatos de forma incremental, así que sus iteraciones por segundo son las de este motor de código limpio, no lo mejor que un núcleo de reparación afinado podría alcanzar. La clasificación por puntuación no depende de ello, puesto que el rendimiento es un eje aparte nunca mezclado con la comparación de puntuaciones, pero las cadencias de iteración deben leerse como las de este motor, no como el techo de la destrucción-reparación.
Este es un estudio del bucle de reparación desnudo, una decisión a la vez, con un presupuesto fijo pequeño. No es el pipeline récord: los tableros que alcanzan mediados de los 450 y más allá combinan un productor constructivo potente, ejecuciones más largas, y la reparación como pulido final, y varias de las observaciones sobre los operadores que aparecen aquí se leerían de otro modo en un tablero cercano al récord que en el mediocre arranque voraz del que parte el bucle. Allí donde un resultado depende de la calidad del tablero inicial, la página de observaciones lo dice. El propio afinamiento de la comunidad halló, por ejemplo, que los operadores guiados por conflictos y por componentes son valiosos precisamente en tableros casi óptimos, donde los pocos desajustes restantes son lo único que queda por corregir, el régimen que las cortas ejecuciones de este estudio nunca alcanzan.
El motor, las diez variantes, los resultados por ejecución versionados y los
scripts de rejilla viven todos bajo el
directorio de soporte
del estudio. just experiments repair-study reconstruye el motor y vuelve a
lanzar toda la rejilla; la ejecución es determinista a una semilla fija, y la
disposición de las esquinas es el único eje de diversidad.