Saltar a contenido

Conceptos básicos

Esta página define lo mínimo para leer el resto del sitio, con un ejemplo de cuatro filas. El ejemplo central para explicar cada propiedad de poda está en preparación (ver Metas).

De la tabla de datos a la matriz básica

Partimos de una tabla de decisión: filas son objetos, columnas son atributos, y una columna especial da la clase de cada objeto. Para cada par de objetos de clases distintas se anota en qué atributos difieren: 1 si difieren, 0 si coinciden. Esa es la matriz de discernibilidad.

Muchas de sus filas sobran. Si una fila tiene unos en todos los lugares donde otra los tiene (es un superconjunto de ella), cualquier conjunto de atributos que distinga el par de la fila pequeña también distingue el de la grande. Al quitar las filas vacías, las repetidas y las que son superconjunto de otra, queda la matriz básica. Todos los algoritmos de este sitio trabajan sobre ella.

Ejemplo

Matriz básica de 4 filas y 5 columnas (columnas \(c_1\) a \(c_5\)):

\(c_1\) \(c_2\) \(c_3\) \(c_4\) \(c_5\)
\(r_1\) 1 1 0 0 0
\(r_2\) 0 1 1 0 0
\(r_3\) 0 0 1 1 0
\(r_4\) 1 0 0 1 1

Ninguna fila contiene a otra, así que es básica.

Testor, testor típico y reducto

  • Un testor es un conjunto de columnas que tiene al menos un 1 en cada fila. En el ejemplo, \(\{c_1, c_2, c_3\}\) es testor: \(r_1\) tiene un 1 en \(c_1\), \(r_2\) y \(r_3\) en \(c_3\), y \(r_4\) en \(c_1\).
  • Un testor típico (o irreducible) es un testor del que no se puede quitar ninguna columna sin dejar de serlo. \(\{c_1, c_2, c_3\}\) no lo es: sin \(c_2\) sigue cubriendo todas las filas.
  • Sobre la matriz básica, reducto y testor típico son lo mismo.

Los testores típicos del ejemplo son tres: \(\{c_1, c_3\}\), \(\{c_2, c_4\}\) y \(\{c_2, c_3, c_5\}\). Los calculó la referencia independiente del proyecto (experiments/lib/bm.py).

Los reductos más cortos son los de menor tamaño: aquí \(\{c_1, c_3\}\) y \(\{c_2, c_4\}\).

El mismo problema con otros nombres

Si cada fila se lee como un conjunto de columnas (una hiperarista), la matriz es un hipergrafo. Un testor es un conjunto que toca todas las hiperaristas: un hitting set o transversal. Un testor típico es un minimal hitting set o transversal mínima Alba-Cabrera et al., 2019. Enumerarlos todos es dualizar el hipergrafo, el nombre que usa la escuela rusa Djukova y Prokofjev, 2015.

Testores típicos Minimal hitting sets Escuela rusa
matriz básica hipergrafo (filas = hiperaristas) matriz booleana
columna / atributo vértice columna
testor hitting set, transversal cubrimiento
testor típico, reducto minimal hitting set, transversal mínima cubrimiento irreducible («тупиковое покрытие»)
fila de compatibilidad (fila que solo cubre una columna del conjunto) arista crítica, crit compatibilidad de columnas

Fila crítica: la prueba que comparten casi todos

En un testor típico, cada columna tiene que ser imprescindible: debe haber al menos una fila que solo ella cubre dentro del conjunto. Esa fila es crítica para la columna. En \(\{c_2, c_3, c_5\}\): \(r_1\) es crítica para \(c_2\), \(r_3\) para \(c_3\) y \(r_4\) para \(c_5\). La fila \(r_2\) la cubren \(c_2\) y \(c_3\), así que no es crítica para ninguna.

Casi todos los algoritmos rápidos construyen el conjunto columna por columna y descartan una rama en cuanto alguna columna elegida se queda sin fila crítica. La comunidad de testores la llama exclusión o compatibilidad, Murakami y Uno la llaman crit Murakami y Uno, 2014, y Djukova la usa desde 1977 con el nombre de compatibilidad de columnas Djukova y Prokofjev, 2015. Las diferencias entre algoritmos están en qué columna se prueba después y qué candidatos se descartan antes: eso es lo que analiza Propiedades de poda.