Saltar a contenido

Propiedades de poda

Borrador

Esta matriz sale de lo que ya leímos en artículos y código. Las celdas con «?» no están verificadas. Cada propiedad tendrá su propia página con la definición, el paso del ejemplo central donde actúa, el contador del motor único que la mide y la ablación que estima su efecto (pasos 4 y 5 de la Meta 2).

Las propiedades

Todas se explican sobre la búsqueda en profundidad que arma un conjunto de columnas \(S\) agregando una columna a la vez.

Id Propiedad Qué hace
P1 Fila crítica Descarta \(S \cup \{v\}\) si alguna columna de \(S\) se queda sin fila que solo ella cubra.
P2 Contribución Solo agrega \(v\) si cubre alguna fila todavía no cubierta.
P3 Fila pivote en la raíz En el primer nivel, solo ramifica por las columnas de la fila con menos unos.
P4 Fila pivote en cada nodo En cada nodo, solo ramifica por las columnas candidatas de la fila no cubierta con menos candidatas.
P5 Fila pivote por profundidad (LV) Cota fija, calculada antes de la búsqueda, de hasta qué columna se puede ramificar según la profundidad.
P6 Filtrado completo Al bajar a un hijo, quita de toda la lista de candidatas las columnas que ya no pueden extender.
P7 Filtrado perezoso Solo prueba las columnas de la fila pivote; las demás se descartan cuando les toca.
P8 Fusión de columnas iguales Trabaja con una columna por grupo de columnas idénticas y multiplica al final.
P9 Eliminación de huecos Salta posiciones de la lista que no pueden dar testores (gaps).
P10 Núcleo Agrega de entrada las columnas de las filas con un solo 1.
P11 Sin repetición por exclusión de hermanos Al probar la i-ésima columna de la fila pivote, saca de las candidatas a las i−1 anteriores.

Algoritmo × propiedad

✓ tiene la propiedad, — no la tiene, ? sin verificar.

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11
BR Lias-Rodríguez y Pons-Porrata, 2009 ? ✓ ✓ — — ? — ? — — —
fast-BR Lias-Rodríguez y Sanchez-Diaz, 2013 ✓ ✓ ✓ — — ✓ — ✓ ✓ — —
GCreduct Rodríguez-Diez et al., 2018 (GCreduct) — ✓ ✓ — — — — ✓ ✓ — —
RegularSearch Lefebre-Lobaina y Ruiz-Shulcloper, 2023 ✓ ✓ ✓ — ✓ — — — — — —
RoPM Pino Gómez et al., 2021 (RoPM) ? ? ✓ ? — ? ? ? ? ? ?
RCC-MAS González-Díaz et al., 2025 (RCC-MAS) ✓ ✓ ✓ ✓ — — ✓ — — ✓ ✓
RUNC Djukova y Prokofjev, 2015 ✓ ✓ — — — ✓ — ? — — ✓
RUNC-M Djukova y Prokofjev, 2015 ✓ ✓ ✓ ✓ — ✓ — ? — — ✓
MMCS Murakami y Uno, 2014 ✓ ✓ ✓ ✓ — — ✓ — — — ✓
br-pivot (nuestro) ✓ ✓ ✓ ✓ — ✓ — ✓ ✓ — ?

Notas:

  • P1 en GCreduct. No poda por fila crítica durante la búsqueda: comprueba la tipicidad cuando ya encontró un testor.
  • P3 en RUNC. Toma la primera fila no cubierta en orden fijo, no la de menos unos.
  • P8 en MMCS. El algoritmo del artículo no fusiona columnas; el programa SHD de Uno hace reducción de datos, pero no sabemos si fusiona columnas iguales.
  • P11 en BR y fast-BR. No la necesitan: recorren la lista en orden creciente, así que cada conjunto aparece una sola vez.
  • RCC-MAS es MMCS más P10 (D3).

Qué dice la medición

  • P4 es la propiedad decisiva. Agregarla a fast-BR lo lleva de agotar el tiempo a menos de 2,6 veces de MMCS (D1).
  • P7 gana a P6 a igualdad de implementación, en las 20 matrices medidas (D4).
  • P1 sin P3 ni P4 no sirve: SHD sin fila pivote agota el límite en 10 de 12 matrices.
  • P5 poda menos que P4: RegularSearch, con la implementación corregida, queda en la clase de fast-BR (D5).