Нахождение минимального набора свойств, которые описывают референт в наборе сущностей

Question

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

Проблема заключается в следующем. Предположим, у меня есть набор E сущностей E={car1, car2, bicycle} и набор свойств P ={red, blue, small}. У меня тоже есть база знаний такая, что red(bicycle), blue(car1), blue(car2), small(car2). Предположим, у меня также есть референт r, который принадлежит E.

Задача состоит в том, чтобы найти минимальный набор свойств P' \subseteq P, который однозначно выбирает r из E. Таким образом, если r равно car2, то P'={small}.

Есть идеи? Я думаю, что-то вроде проблемы покрытия множества или функциональных зависимостей (как в теории БД) может дать некоторое представление, но я подумал, что я хотел бы спросить, прежде чем углубляться в эту литературу. Еще одна возможность - построение графов и поиск алгоритмов для изоморфизмов подграфов ... возможно.

Спасибо.

Answer 1

Вы ищете минимальное покрытие набора множества E \ {r} с отрицаниями (дополнениями) тех свойств, которым принадлежит r (свойства могут рассматриваться как подмножества E).

Поскольку эти наборы могут быть любыми, это NP-сложный.

Точнее:

Наличие установленного экземпляра обложки (U, S), где U - это набор, который нужно покрыть, и S = {s1, s2, ..., sn } - это семейство покрывающих множеств, вы можете построить экземпляр вашей задачи так, чтобы ее решение давало покрытие множеств в исходной задаче:

E = U \ union {r}, где r является референтом, а r не принадлежит U. Набор свойств P = {p1, p2, ..., pn} составлен из S, так что для каждого e в U и каждого i так, что 1 <= <code>i <= n у нас есть <code>pi (e), если e не в si. Более того, каждое свойство верно для r. Другими словами, свойства являются дополнением к исходным наборам, если они ограничены U, а r имеет все свойства.

Теперь ясно, что каждый набор свойств, который выбирает r, является набором покрытия в исходной задаче - если r выбран набором S* свойств, то все остальные элементы (это означает, что все те в U) произойдет сбой хотя бы одного свойства в S*, поэтому каждый элемент U принадлежит хотя бы одному исходному набору (из конструирования свойств как дополнения к наборам). Это означает, что U является объединением тех множеств, из которых были построены свойства в S*.

Обратное также верно - набор обложек в U переводится в r -выборный набор в E.

Вышеприведенное сокращение, очевидно, является полиномиальным, поэтому проблема NP-трудна.

Answer 2

Сначала найдите набор всех свойств, которыми обладает r. Назовите его S. Для каждого свойства p в S найдите e (p), все сущности, которые имеют свойство p. Для каждого p в S ясно, что e (p) содержит r. Теперь возьмем пересечения e (p) для каждого p в S. Если пересечение содержит более одной сущности, решения не существует, и мы заканчиваем алгоритм.

Итак, у нас есть набор S свойств, которые однозначно определяют сущность r. Теперь нам нужно найти минимальное подмножество S, которое однозначно определяет r. Мы можем удалить любое свойство p из S, для которого существует свойство q в S, так что e (p) является надмножеством e (q). Если вы сделаете это исчерпывающе, вы в конечном итоге получите сокращенный набор свойств T, так что пересечение e (p) для всех p в T будет по-прежнему {r}, но никакое дополнительное свойство в T не может быть удалено. Этот набор T тогда минимален.

Я не думал о том, чтобы найти свойство, которое вы можете удалить, более эффективным, чем просто попробовать все комбинации, но мне кажется, что должен быть какой-то способ.