Похищение статей Пролога - PullRequest
Новая
       17

Похищение статей Пролога

0 голосов
/ 06 декабря 2018

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

Например:

Каждый узел A должен быть подключен к узлу B с типом ребра B, который связан любым типом ребра с узлом D, а корень должен иметь путьпо крайней мере к 2 другим узлам. 

followsSpec(Root) :- 
    edge(Root, _, A), 
    edge(Root, _, B), 
    A != B, 
    edge(A, edgeTypeB, C), 
    node(C, nodeTypeC), 
    edge(C, _, D),
    node(D, nodeTypeD).

Я хотел бы сказать 

node(root, typeA)
followsSpec(root)

и похитить другие возможные элементы графа, которые делают followsSpec true: 

node(b, typeB)
node(c, typeC)
edge(root, some_arbitrary_edge_type, b)
edge(root, some_other_arbitrary_edge_type, c)
edge(b, edge_type_b, c)

Есть ли способ сделать это в Прологе?

В частности, меня беспокоит эффективность, поскольку на самом деле спецификация более сложная и в ней будет не менее 100 узлов.

Редактировать: пытаться формализовать: приводимые предикаты edge/3(где три переменные соответствуют источнику, цели и типу преобразования) и node/2 (где две переменные соответствуют идентификатору узла и метке узла).
Я начну с одного факта node(root, rootLabel)).Мое наблюдение: следует за Спец (корень), где

followsSpec(X) :- "x is connected in a particular way to other nodes through edges"

Что я хочу заметить: что это за другие узлы и ребра, так что следует за Спец (корень) верно.

1 Ответ

0 голосов
/ 22 декабря 2018

Вы можете использовать гипотетические рассуждения, чтобы найти похищающие решения.Допустим, у вас есть теория T, и вы хотите найти объяснение E для некоторого наблюдения O: 

 T, E |- O

Гипотетическое рассуждение имеет специальный оператор, называемый вложенной импликацией (предположить, что).Вы можете проверить абдуктивное решение, используя это следствие, превратив похищение в дедукцию: 

 T |- assumez(E, O).

Простая реализация acceptz / 2 будет выглядеть так: 

assumez(E,O) :-
   assertz(E),
   O,
   retract(E).

Но вышесказанное не выживетразрез, так что вам нужна система Prolog, в которой есть трейлинг assertz / 1 и retract / 1.Если вы не хотите использовать CHR или ASP, вы можете использовать более простую библиотеку (minimal / hypo) из Jekejeke Prolog.

...