Движок обратного вывода (найдите случайный X, для которого foo (X) истинно)

Question

Мне известно, что такие языки, как Prolog, позволяют писать такие вещи как:

mortal(X) :- man(X).    % All men are mortal
man(socrates).          % Socrates is a man

?- mortal(socrates).    % Is Socrates mortal?
yes

Я хочу что-то вроде этого, но в обратном направлении. Предположим, у меня есть это:

mortal(X) :- man(X).
man(socrates).
man(plato).
man(aristotle).

Затем я прошу дать мне случайный X, для которого смертный (X) истинен (таким образом, он должен дать мне один из «Сократ», «Платон» или «Аристотель» в соответствии с каким-то случайным семенем).

Мои вопросы:

• Имеет ли этот вид обратного вывода имя?
• Существуют ли языки или библиотеки, которые его поддерживают?

EDIT

Как заметил кто-то ниже, вы можете просто спросить смертного (X), и он вернет все X, из которых вы можете просто выбрать случайный из списка. Что если, однако, этот список будет очень большим, возможно, миллиардами? Очевидно, что в этом случае не нужно генерировать все возможные результаты, прежде чем выбрать один.

Чтобы увидеть, как это может быть практической проблемой, представьте простую грамматику, которая генерирует случайное предложение в форме «прилагательное1 существительное1 наречие transitive_verb прилагательное2 существительное2». Если списки прилагательных, существительных, глаголов и т. Д. Очень велики, вы можете увидеть, как комбинаторный взрыв является проблемой. Если бы в каждом списке было 1000 слов, у вас было бы 1000 ^ 6 возможных предложений.

Answer 1

Вместо глубокого поиска в Прологе можно легко реализовать рандомизированную стратегию глубокого поиска. Все, что требуется, - это рандомизировать поток программы в точках выбора, чтобы при каждом достижении дизъюнкции случайный полюс в дереве поиска (= программа пролога) выбирался вместо первого.

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

Answer 2

Я не думаю, что вы можете рассчитать n-е решение напрямую, но вы можете рассчитать n первых решений (n случайным образом выбранных) и выбрать последнее.Конечно, это будет проблематично, если n = 10 ^ (big_number) ...

Вы также можете сделать что-то вроде

mortal(ID,X) :- man(ID,X).

man(X):- random(1,4,ID), man(ID,X).
man(1,socrates).
man(2,plato).
man(3,aristotle).

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

Я подозреваю, что не существует способа сделать это более эффективно: вы должны либо вычислитьнабор решений и выберите один или один элемент из набора всех решений, пока не найдете одно решение.Но не верьте мне на слово xd

Answer 3

Я никогда не использовал Пролог или что-то подобное, но, судя по , что Википедия говорит по этому вопросу , спрашивая

?- mortal(X).

должен перечислить все, для чего mortal верно. После этого просто выберите один из результатов.

Итак, чтобы ответить на ваши вопросы,

• Я бы пошел с «запросом с переменной в нем»
• Из того, что я могу сказать, сам Пролог должен поддерживать его вполне нормально.