Término de CS para algoritmos de coincidencia de reglas en tuplas de condiciones obligatorias y opcionales

Question

Estoy tratando de investigar literatura sobre algoritmos para resolver un problema en particular, pero no creo que conozca bien el término de búsqueda correcto para describir lo que soy buscando.

El objetivo es tener una base de datos de reglas consultables, donde cada regla se especifica como condiciones de tupla — algunas obligatorias, algunas opcionales. Una consulta en el sistema consiste en una tupla de hechos sobre el mundo, y devuelve una lista de todas las reglas cuyas condiciones obligatorias coinciden con los hechos en la consulta. Cada regla se califica con el número × ponderado de las condiciones opcionales y la lista se ordena de ese modo.

Así, por ejemplo, si estuviera usando esto para escribir un servicio de compañero de piso de coincidencia, las normas serían algo así como

alice : { mandatory : { nightowl = no, smoker = no, pets < 2 }, 
      optional : { pets = 0 } } 
bob : { mandatory : { nightowl = yes, pets = 0 }, 
      optional : {smoker = no} } 
charlie : { mandatory : { musician = no }, 
      optional : {nightowl = yes, pets < 2 } } 

y la consulta sería

(nightowl = no, pets = 1, smoker = no, musician = no) 

regresar

(charlie : 1/1 mandatory matched, 1/2 optional matched, 
    alice : 3/3 mandatory matched, 0/1 optional matched) 

Sé que este es un problema que debe haberse resuelto muchas veces en la informática ya , pero no sé qué palabras clave buscar. No es una función de distancia , porque algunas condiciones son rechazos discretos verdadero/falso, mientras que otras son opcionales o tienen puntajes lineales. No es coincidencia de patrón o concordancia difusa, porque parece que se refieren principalmente a cadenas y gráficos. No es un sistema de producción o reglas motor como el Rete algorithm, porque no saca inferencias IF-THEN de las reglas, ni recuerda hechos de una llamada a la siguiente.

¿Qué es que se llama?

Solo necesito investigación o descripciones de algoritmos, no implementaciones reales. Nuestra aplicación tiene limitaciones tan severas en tiempo real y memoria que necesitaremos construir una implementación propia de todos modos, pero me gustaría saber qué más se ha hecho en el espacio antes de comenzar a inventar el código. También sería grandioso un documento de ACM del que pudiera buscar citas.

Answer 1

El término que diría que describe con más precisión el tipo de problema del que está hablando es un problema constraint satisfaction.

Más específicamente, usted está en el ámbito de ponderado satisfacción de la restricción.

Programación de restricción es el término habitual para un conjunto de herramientas y lenguajes que están diseñados específicamente para resolver este tipo de problemas.

Answer 2

Coincidencia de las condiciones obligatorias es range searching, específicamente la búsqueda de rango ortogonal. La literatura relevante pertenece a la geometría computacional. La clasificación por condiciones opcionales es una operación de clasificación.