Есть много вещей, которые нужно сказать об этом вопросе, так что это будет долгий и бессвязный и в конечном счете неудовлетворительный ответ. Так что я мог бы также начать с домашней живописи: Пожалуйста, не используйте camelCaseIdentifiers для предикатов, вместо этого мы обычно используем underscore_separated_words. Я не уверен, почему это в основном вызывает ошибки в Prolog, но я подозреваю, что отчасти потому, что заглавные буквы синтаксически значимы.
Двигаясь дальше, ваш weakest/3 предикат нарушается:
?- weakest(Weakest, r2, r1).
false.
Я думаю, что вы имели это право в первой версии вашего вопроса, но тогда вы удалили третий пункт из weakest/3, потому что вы думали, что это вызвало лишние ответы , Излишне говорить, что «эффективность» бесполезна без правильности. (Кроме того, мы обычно ставим «выходные» аргументы последними, а не первыми.)
Часть причин, по которым вы получаете избыточные ответы, - это использование двух (косвенно) рекурсивных вызовов на isARelation/4 в isADerivedRelation/4. То, что вы вычисляете, похоже на переходное закрытие союза «прямых» отношений. Обычный способ выразить транзитивное замыкание в Прологе, как это:
transitive_closure(A, B) :-
base_relation(A, B).
transitive_closure(A, C) :-
base_relation(A, B),
transitive_closure(B, C).
То есть, мы первый «взять базовый шаг», то рекурсия. Если наше базовое соотношение имеет пары a-b, b-c, c-d, то это решение найдет решение a-d ровно один раз, как состав базовой пары a-b и производной транзитивной пары b-d. Напротив, если бы мы структурировали второе предложение так же, как и вы, с двумя рекурсивными вызовами до transitive_closure/2, мы получили бы решение a-d дважды: один раз, как указано выше, но также один раз, потому что мы бы вывели транзитивную пару a-c и составили ее с c-d дать a-d.
Вы можете исправить это, изменив первый звонок isARelation/4 в isADerivedRelation/4 в звонок isADirectRelation/3.
Другая проблема заключается в том, что вы используете Visited неправильно: вы отмечаете пару Source-Target как посетили, прежде чем доказали, что такое решение даже существует! Вероятно, вы должны пометить Source-Intermediate как посещенный.
Несмотря на это, вы все равно получите избыточные решения для пары элементов, если между этими элементами графика есть несколько разных путей. Это то, как работает логика Prolog: Prolog находит индивидуальные ответы на ваш запрос, но не позволяет вам напрямую говорить об отношениях между этими ответами. Если мы хотим заставить его перечислить все ровно один раз, мы должны оставить чистую логику.
Некоторые системы Prolog предлагают функцию, называемую «табуляция», которая в основном кэширует все решения для предиката «набросок» и позволяет избежать повторных вычислений. Это должно избегать избыточных ответов и даже упростить ваше определение: если ваше отношение закрытия указано, вам больше не нужно отслеживать список Visited, потому что циклическая рекомпиментация будет предотвращена таблицей. Я не могу дать вам проверенный код, потому что у меня нет Prolog с таблицей, лежащей вокруг. Даже без табуляции, предлагаемой вашей системой, теоретическая возможность «мнимая» решений сама по себе, используя нечистую базу данных Prolog. Трудно получить это точно, без каких-либо избыточных решений.
В качестве альтернативы нечистому прологу ваша проблема кажется более подходящей для datalog или answer-set-programming. Это модели программирования, которые используют синтаксис типа Prolog, но с установленной семантикой, которая, кажется, именно то, что вы хотите: предложение является либо решением, либо нет, нет концепции избыточных решений. Весь набор решений вычисляется за один раз. Удаление цикла также автоматическое, поэтому вам не нужно (фактически, из-за ограниченного языка ввода, не может использовать) список Visited. Если бы я был вами, я попытался бы сделать это в Datalog.
В качестве дополнительного расширения Prolog может быть расширенное решение, основанное на правилах ограничения прав (CHR). Но действительно, попробуйте Datalog.
И наконец, я не понимаю, почему вы считаете, что e2,r2,e2 является недостающим решением. Единственный путь от e2 до e2, который я вижу, проходит через e3 и обратно до e2 через отношение r1, которое является самым слабым, поэтому решение должно быть e2,r1,e2.
Вы уверены, что Prolog является языком \ инструментом для использования? –
Одно небольшое наблюдение: элемент '\ + ([Source, Relation, Target], Посещенные)' call в начале 'isADerivedRelation/4' является избыточным с именем в' isARelation/4', предполагая 'isADerivedRelation/4' в противном случае вызывается только из мест, которые уже проверяют его. Мне также интересно узнать, почему вы пишете '= (X, Y)', а не 'X = Y', или, что еще проще,' самый слабый (X, X, X) .' вместо 'слабый (Weakest, X, Y): - = (Слабый, X), = (X, Y) .' и 'слабый (X, X, Y): - слабее (X, Y).'вместо' слабых (слабых, X, Y): - = (слабый, X), слабее (X, Y) .'. – lurker
Вызов \ + члена в начале isARelation/4 был удален, он блокировал действительный результат e1, r1, e3. Я пишу это так, как я неопытен ... Я не уверен, что Prolog - правильный инструмент, но я пытаюсь это выяснить. Если это сработает, было бы намного легче поддерживать, поскольку мне просто нужно написать правила. – gctwnl