Errores encontrados en el código original¶
Fecha: 2026-11-16. Desde el 2026-11-17 hay un resumen en la página de los asesores, y los errores se publicarán como sección del artículo.
Resumen¶
| Programa | Síntoma | Causa | Estado |
|---|---|---|---|
GCreduct (gcReduct.jar) |
Cuenta menos reductos en algunas matrices | Lista de atributos repetidos termina en el primer 0, y 0 es un id válido | Corregido y verificado |
MinReduct (MinReduct.jar) |
Nsol de más o de menos cuando hay columnas repetidas |
El mismo terminador, más una suma duplicada | Corregido y verificado |
sRGA (sRGA.jar) |
Cuenta de más cuando el reducto más corto tiene longitud 1 | Comparación desplazada en uno | Corregido y verificado |
fast-BR (fastBR.jar y el código de CTBRES) |
Cuenta de menos cuando una columna llena está repetida | El reducto de una sola columna se cuenta una vez, sin sus copias | Corregido y verificado (hallado el 2026-11-16 por la noche) |
| GCreduct, MinReduct, fast-BR, fast-CT_EXT | Excepción o bucle sin fin en matrices degeneradas | Los generadores de candidatos vacían la pila | Corregido y verificado |
CAMARDF (Cpp1.cpp) |
Agota memoria; falla con muchas columnas | Fuga de memoria y atributos guardados como char |
No corregido; sustituido por java/src/shortest/Camardf.java |
| Artículo de Susmaga (1998) | Figuras 3 y 4 | Errata de signo | Solo documentado |
"Verificado" significa: 442 matrices pequeñas con referencia independiente, sin ningún conteo distinto y sin ninguna corrida sin respuesta (sección "Verificación"). No es una demostración.
Las versiones corregidas están en java/fixed/. Los originales en legacy/ no se tocaron.
1. Terminador de atributos repetidos (GCreduct y MinReduct)¶
BasicMatrix.reduceColumns() elimina columnas repetidas y guarda en repeatedAtts los ids de las columnas que representan a un grupo. El arreglo se crea lleno de ceros y los bucles que lo recorren paran en el primer cero:
while (BM.repeatedAtts[k] != 0) {
El id 0 es válido. Tras la rotación inicial, el id 0 corresponde a la última columna del archivo. Si esa columna pertenece a un grupo repetido, queda primera en la lista, el bucle para de inmediato y se pierden las multiplicidades de todos los grupos.
Evidencia: en experiments/preliminar/gcreduct-conteo/soy_1.txt y soy_9.txt el par repetido incluye la última columna (columnas 26 y 34, y 4 y 34). El JAR original reporta 535 reductos; fast-BR y fast-CT_EXT reportan 570. En el archivo original de soybean el par repetido es 32 y 33, y el JAR acierta.
Corrección: el arreglo se llena con -1 y los bucles paran en -1.
2. Suma duplicada en MinReduct¶
Esta parte se leyó del código descompilado de MinReduct.jar, porque el fuente incluido en Shortest_src.zip es anterior al JAR y no tiene la variable extras ni la clase MinCandGen.
Cuando aparece un reducto más corto que los anteriores, el código reinicia el resultado y suma count - 1 a extras. Luego, fuera de ese bloque, vuelve a sumar count - 1 para el mismo reducto. El primer reducto de cada nueva longitud mínima se cuenta con sus copias dos veces.
Evidencia: matriz de 3 filas y 4 columnas con filas 0 0 0 1, 1 0 0 0, 0 1 1 0. Hay 2 reductos más cortos; el JAR reporta 3.
Corrección: se eliminó la suma dentro del bloque de reinicio.
3. Comparación desplazada en sRGA¶
Leído del código descompilado de sRGA.jar. El bucle descarta un conjunto parcial con:
if (R.tope >= k) continue;
tope es el índice del último elemento, es decir, el tamaño menos uno. La condición deja pasar conjuntos de tamaño k y los extiende a k + 1. Como k empieza en 1, la primera pasada ya admite tamaño 2. Si el reducto más corto tiene longitud 1, el resultado mezcla reductos de longitud 1 y 2.
Evidencia: en 200 matrices aleatorias pequeñas falla en las 8 que tienen longitud mínima 1 y en ninguna otra. En arrhythmia reporta 3236; las demás herramientas reportan 5.
Corrección: if (R.tope + 1 >= k) continue;. También se cambió la condición del bucle exterior de k < numColumnas a k <= numColumnas.
4. CAMARDF¶
Cpp1.cpp es el fuente de los autores con modificaciones de Vladimir para contar todos los reductos más cortos; los cambios están marcados con comentarios en español. El original devolvía un solo reducto mínimo.
DelCharreserva una lista nueva en cada iteración y solo se libera la última. La memoria crece con los candidatos visitados. Es la explicación probable de las corridas sin memoria reportadas en el artículo de MinReduct; no se reprodujo.- Los atributos se guardan como
charcon valori + 1. Con más de 127 columnas se desborda, y la columna 256 vale'\0', que es el terminador de cadena. - La entrada es una tabla de decisión cuya última columna es la clase, no una matriz básica.
java/src/shortest/Camardf.java reproduce el algoritmo sin esos límites. Con la opción -faithful da la misma respuesta y el mismo número de candidatos que el fuente C en 211 de 213 matrices. Las dos diferencias: arrhythmia (279 columnas, 129 contra 130 candidatos, misma respuesta) y led24, cuyo archivo contiene una fila de ceros.
5. Errata en el artículo de Susmaga¶
En la Figura 1 (MRGA) la unión que define T_i recorre los R con R ∩ C_i = ∅. En las Figuras 3 (k-RGA) y 4 (S-RGA) aparece R ∩ C_i ≠ ∅. Lo correcto es = ∅: solo se extienden los conjuntos que todavía no cubren la cláusula. Ni el código original ni Srga.java arrastran la errata.
6. Reducto de una sola columna en fast-BR¶
Encontrado al verificar contra la referencia independiente. Hasta entonces fastBR.jar se usaba como referencia.
FastBR.extraerTT() trata aparte el caso en que una columna sola es reducto (columna llena de unos):
if (rasgo_X.cantValoresUnitarios() == numFilas) {
solucion[0] = 1;
solucion[1] = primero + 1;
contadorTestores++;
En el resto del código cada reducto encontrado sobre la matriz sin columnas repetidas se expande con la tabla contraidos. Aquí no: una columna llena con n copias cuenta 1 en vez de n.
Evidencia: matriz de 3 filas y 5 columnas con filas 1 0 0 1 1, 0 1 0 1 1, 0 0 1 1 1. Hay 3 reductos ({3}, {4} y {0, 1, 2}); el JAR reporta 2. El mismo código está en CTBRES/Algorithms/src/edu/tt/alghoritms/br_colums_CH/Fast_BR.java.
Corrección: contadorTestores += contraidos[0][rasgo_X.idTupla];.
Alcance: hace falta una columna llena y repetida. En los paquetes públicos solo ocurre en BMarrhythmia.txt.
7. Matrices degeneradas¶
Si la fila con menos unos tiene todas las columnas distintas, o todas menos una, los programas no terminan bien:
GapCandGen(GCreduct) yMinCandGen(MinReduct): el bucle que elimina brechas vacía la pila y lee la posición -1.ArrayIndexOutOfBoundsException.FastCandGen(fast-CT_EXT): la pila queda con tope negativo y el programa no termina.FastBR: leepMatriz[primero]antes de comprobar el fin, y saca de una pila vacía en la lista exterior. AdemástempMattiene una fila de menos cuando todas las columnas son iguales.
Ejemplos: matriz identidad de 2 por 2, matriz de una sola fila, y 1 1 0 1 / 1 0 1 1.
Corrección: guardas en los cuatro generadores (marcadas con FIX en java/fixed/). Ninguna matriz de los paquetes públicos cae en este caso, así que no afecta nada publicado.
Alcance sobre resultados publicados¶
Ver docs/reporte-2026-11-17.md y experiments/audit/results/. La auditoría revisa todas las matrices de los paquetes de GCreduct, MinReduct y CTBRES.
Datos con problemas¶
BMled24.txtdel paquete de MinReduct: 2459 filas y una de ellas es todo ceros. No es una matriz básica válida.
Verificación¶
experiments/shortest/verify_fixed.py compara originales, corregidos e implementaciones nuevas contra una referencia en Python (experiments/lib/bm.py) que no comparte código con ellos. La referencia se comprobó contra fuerza bruta en 300 matrices de hasta 14 columnas.
Grupos: 200 matrices aleatorias, 150 con columnas repetidas (la mitad con una repetida en la última posición), 40 con columnas vacías, 40 con una columna llena, 12 casos límite. Total 442.
| Programa | Original: conteo distinto | Original: sin respuesta | Corregido: conteo distinto | Corregido: sin respuesta |
|---|---|---|---|---|
| GCreduct | 122 | 32 | 0 | 0 |
| fast-BR | 25 | 19 | 0 | 0 |
| fast-CT_EXT | 0 | 7 | 0 | 0 |
| MinReduct | 176 | 23 | 0 | 0 |
| sRGA | 38 | 0 | 0 | 0 |
Actualización del 2026-11-17: GCreduct, fast-BR, fast-CT_EXT y MinReduct corregidos aceptan -list. Junto con Camardf, Srga, Mmcs, Rs y el SHD de Uno, coinciden por conjunto de reductos con la referencia en las 442 matrices y en 8 de UCI (experiments/shortest/results/verify_sets_uci.txt). La copia corregida de sRGA sigue comparándose solo por conteo.
Todos los fallos de los originales quedan explicados por cinco condiciones que se pueden leer de la matriz (experiments/audit/profile.py): ningún conteo distinto ocurrió fuera de ellas.
Salida completa: experiments/shortest/results/verify_small.txt y verify_uci.txt.
Pruebas de regresión, un comando: scripts/build.sh && python3 tests/run.py. Son 11 matrices pequeñas; los corregidos pasan las 11 y los JAR originales ninguna (python3 tests/run.py --original).