Термин CS для алгоритмов сопоставления правил для кортежей обязательных и необязательных условий - PullRequest
Новая
       27

Термин CS для алгоритмов сопоставления правил для кортежей обязательных и необязательных условий

5 голосов
/ 17 августа 2011

Я пытаюсь исследовать литературу для алгоритмов, чтобы решить конкретную проблему, но я не думаю, что я точно знаю правильный поисковый термин, чтобы описать то, что я ищу.

Цель состоит в том, чтобы создать базу данных правил с запросами, где каждое правило указывается в качестве условий кортежа & mdash; некоторые обязательные, некоторые необязательные. Запрос в систему состоит из набора фактов о мире и возвращает список всех правил, обязательные условия которых соответствуют фактам в запросе. Каждое правило оценивается по количеству и разу сопоставленных значений дополнительных условий, и список сортируется таким образом.

Так, например, если бы я использовал это, чтобы написать сервис сопоставления соседей по комнате, правила были бы что-то вроде 

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 } }

и запрос будет 

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

возвращение 

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

Я знаю, что это проблема, которая уже много раз решалась в информатике, но я не знаю, какие ключевые слова искать. Это не функция расстояния , потому что некоторые условия являются дискретными истинными / ложными отклонителями, тогда как другие являются необязательными или имеют линейные оценки. Это не сопоставление с образцом или нечеткое сопоставление , потому что они, по-видимому, относятся в основном к строкам и графикам. Это не производственная система или механизм правил , подобный Rete алгоритму , потому что он не делает вывод IF-THEN из правил и не помнит факты из один звонок другому.

Что называется ? 1030 *

Мне нужны только исследования или описания алгоритмов, а не фактические реализации. Наше приложение имеет такие серьезные ограничения в реальном времени и памяти, что нам все равно нужно будет создать собственную реализацию, но я хотел бы знать, что еще было сделано в космосе, прежде чем я начну изобретать код. Также отлично подойдет бумага ACM, из которой я буду гоняться за цитатами.

Ответы [ 2 ]

2 голосов
/ 17 августа 2011

Соответствующим обязательным условиям является поиск диапазона , в частности поиск ортогонального диапазона.Соответствующая литература относится к вычислительной геометрии.Ранжирование по необязательным условиям является операцией сортировки.

2 голосов
/ 17 августа 2011

Термин, который я бы сказал наиболее точно, описывает тип проблемы, о которой вы говорите: удовлетворение ограничения проблема .

В частности, вы 'находятся в области взвешенного удовлетворения ограничения.

Ограниченное программирование - это обычный термин для набора инструментов и языков, специально разработанных для решения этих типов задач..

...