Mapa de algoritmos¶
Todos los algoritmos de esta página calculan lo mismo: los testores típicos de una matriz básica, o sea, sus minimal hitting sets (ver Conceptos básicos). Los que buscan solo los más cortos están en una tabla aparte.
«En el marco» es el nombre con que se corre en experiments/framework/runner.py. Todos están validados por conjunto de reductos contra la referencia independiente.
Todos los reductos¶
| Algoritmo | Familia | Publicación | En el marco | Implementación |
|---|---|---|---|---|
| BR | Testores | Lias-Rodríguez y Pons-Porrata, 2009BR: A New Method for Computing All Typical Testors Alberto Lias-Rodríguez; Aurora Pons-Porrata Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications (CIARP 2009), 5856, 433–440, 2009 Resumen: Resumen pendiente.Nuestra nota: BR original. Reordena filas y columnas una sola vez, en la raíz. Compara solo con LEX y CT-EXT.Ficha completa → |
(a través de fast-BR) | — |
| fast-BR | Testores | Lias-Rodríguez y Sanchez-Diaz, 2013An Algorithm for Computing Typical Testors Based on Elimination of Gaps and Reduction of Columns Alberto Lias-Rodríguez; Guillermo Sanchez-Diaz International Journal of Pattern Recognition and Artificial Intelligence, 27(8), 2013 https://doi.org/10.1142/S0218001413500225 Resumen: Resumen pendiente.Nuestra nota: fast-BR. Fila pivote solo en la raíz; fusiona columnas iguales y elimina huecos. Leído por las partes de preproceso e ideas centrales.Ficha completa → |
fastbr |
Copia corregida del Java original |
| fast-BR reescrito, 3 modos | Ablación propia | — | br, br-pivot |
mhs.Br (nuevo) |
| fast-CT_EXT | Testores | ver Revisión de testores | fastctext |
Copia corregida del Java original |
| GCreduct | Testores | Rodríguez-Diez et al., 2018 (GCreduct)A fast hill-climbing algorithm for computing all reducts of a decision system (GCreduct) Vladímir Rodríguez-Diez; José Fco. Martínez-Trinidad; Jesús A. Carrasco-Ochoa; Manuel S. Lazo-Cortés Information Sciences, 2018 https://doi.org/10.1016/j.ins.2017.12.027 Resumen: Resumen pendiente.Nuestra nota: Artículo propio. Título provisional en esta ficha: falta copiar el título, volumen y páginas de la versión publicada.Ficha completa → |
gcreduct |
Copia corregida del Java original |
| YYC | Testores | ver Lefebre-Lobaina y Ruiz-Shulcloper, 2023RegularSearch Jairo A. Lefebre-Lobaina; José Ruiz-Shulcloper Information Sciences, 649, 119665, 2023 Resumen: Resumen pendiente.Nuestra nota: Título provisional en esta ficha: falta copiar el título completo. Leído completo salvo figuras. Código MIT en github.com/J41R0/RegularSearch.Ficha completa → |
yyc |
Código de Lefebre (MIT) |
| RegularSearch | Testores | Lefebre-Lobaina y Ruiz-Shulcloper, 2023RegularSearch Jairo A. Lefebre-Lobaina; José Ruiz-Shulcloper Information Sciences, 649, 119665, 2023 Resumen: Resumen pendiente.Nuestra nota: Título provisional en esta ficha: falta copiar el título completo. Leído completo salvo figuras. Código MIT en github.com/J41R0/RegularSearch.Ficha completa → |
regsearch, regsearch-java |
Código de Lefebre (MIT) y reescritura mhs.RegSearch |
| RCC-MAS (constructos) | Testores | González-Díaz et al., 2025 (RCC-MAS)RCC-MAS Y. González-Díaz; others Machine Learning, 114, 168, 2025 https://mlanthology.org/mlj/2025/gonzalezdiaz2025mlj-rccmas Resumen: Resumen pendiente.Nuestra nota: Título y autores provisionales en esta ficha. Seguimos los Algoritmos 1-5; el Algoritmo 3 impreso pierde constructos.Ficha completa → |
rccmas, rccmas-printed |
mhs.RccMas, desde el pseudocódigo |
| RUNC, RUNC-M | Escuela rusa | Djukova y Prokofjev, 2014Построение и исследование новых асимптотически оптимальных алгоритмов дуализации E. V. Djukova; P. A. Prokofjev Machine Learning and Data Analysis, 1(8), 2014 Resumen: Resumen pendiente.Nuestra nota: Primera publicación de RUNC, RUNC-M y PUNC. Copia tomada del repositorio github.com/ppprok/dual. Leído por el resumen en inglés, referencias y tablas.Ficha completa →; Djukova y Prokofjev, 2015Asymptotically optimal dualization algorithms E. V. Djukova; P. A. Prokofjev Computational Mathematics and Mathematical Physics, 55(5), 891–905, 2015 https://doi.org/10.1134/S0965542515050103 Resumen: Resumen pendiente.Nuestra nota: Leído completo (traducción al inglés). Es la traducción del artículo de 2014 en Mach. Learn. Data Anal.; no son dos conjuntos de experimentos.Ficha completa → |
ppdual, ppdual-runc, runcm |
C++ de Prokofyev (MIT); C++ de Nikiforov (sin licencia) |
| MMCS | Minimal hitting sets | Murakami y Uno, 2014Efficient algorithms for dualizing large-scale hypergraphs Keisuke Murakami; Takeaki Uno Discrete Applied Mathematics, 170, 83–94, 2014 https://doi.org/10.1016/j.dam.2014.01.012 https://arxiv.org/abs/1102.3813 Resumen: Resumen pendiente.Nuestra nota: Leída la versión final (DAM) y arXiv 1102.3813v2. La numeración de secciones cambia: en DAM la elección de la hiperarista mínima es §3.5 y la poda es §3.6.Ficha completa → |
mmcs, shd-mmcs |
mhs.Mmcs (nuevo, desde el artículo); SHD de Uno |
| RS | Minimal hitting sets | Murakami y Uno, 2014Efficient algorithms for dualizing large-scale hypergraphs Keisuke Murakami; Takeaki Uno Discrete Applied Mathematics, 170, 83–94, 2014 https://doi.org/10.1016/j.dam.2014.01.012 https://arxiv.org/abs/1102.3813 Resumen: Resumen pendiente.Nuestra nota: Leída la versión final (DAM) y arXiv 1102.3813v2. La numeración de secciones cambia: en DAM la elección de la hiperarista mínima es §3.5 y la poda es §3.6.Ficha completa → |
rs, shd-rs |
mhs.Rs (nuevo); SHD de Uno |
| Motor único | Propio | — | core-<rep>-<row>-<cand> |
mhs.core, 8 configuraciones (D4) |
Fuera de la primera versión: HTC-BDD (Toda), RoPM Pino Gómez et al., 2021 (RoPM)RoPM
J. Pino Gómez; Yenny Villuendas-Rey; others
IEEE Access, 9, 128220–128231, 2021
https://doi.org/10.1109/ACCESS.2021.3112385
Resumen: Resumen pendiente.Nuestra nota: Título y autores provisionales en esta ficha. Compara solo con fast-BR y GCreduct. Parece usar la fila de menos unos como pivote (inferencia, sin código).Ficha completa → (sin código), MiLIT (sin licencia), FastRS (Lefebre, sin publicar).
Reductos más cortos¶
| Algoritmo | Publicación | En el marco | Implementación |
|---|---|---|---|
| MinReduct | ver Rodríguez-Diez et al., 2018 (GCreduct)A fast hill-climbing algorithm for computing all reducts of a decision system (GCreduct) Vladímir Rodríguez-Diez; José Fco. Martínez-Trinidad; Jesús A. Carrasco-Ochoa; Manuel S. Lazo-Cortés Information Sciences, 2018 https://doi.org/10.1016/j.ins.2017.12.027 Resumen: Resumen pendiente.Nuestra nota: Artículo propio. Título provisional en esta ficha: falta copiar el título, volumen y páginas de la versión publicada.Ficha completa → (mismo grupo) |
minreduct |
Copia corregida |
| sRGA | Susmaga (1998), ficha pendiente | srga |
Copia corregida y Srga nuevo |
| CAMARDF | Zhou et al., 2009 (CAMARDF)CAMARDF J. Zhou; D. Miao; Q. Feng; L. Sun Rough Sets and Knowledge Technology (RSKT 2009), 2009 Resumen: Resumen pendiente.Nuestra nota: Título provisional en esta ficha. Del artículo solo se vio la portada; el algoritmo se reimplementó leyendo el C++.Ficha completa → |
camardf |
Camardf en Java |
| MMCS acotado | — | mmcs-shortest |
mhs.Mmcs |
Cómo se relacionan¶
Las tres familias comparten la prueba de fila crítica. Lo que las separa es dónde ramifican y cuándo descartan candidatos. La tabla completa algoritmo × propiedad está en Propiedades de poda, y las equivalencias demostradas en Descubrimientos, D2.