Пролог, оптимизируй поколение

Question

Я написал прологическую программу, которая генерирует все возможные положения элементов в двумерной таблице.Указано количество элементов и размер таблицы.

Мой код:

geni(Min, Min, Max) :- Min =< Max.
geni(Min, X, Max) :- Max >= Min, MinInc is Min+1, geni(MinInc, X, Max).
generate(_, 0, []) :- !.
generate(TSize, N, [X|Tail]) :- X=k(X1,Y1), geni(1,X1,TSize), 
                                geni(1,Y1,TSize), NDec is N-1, 
                                generate(TSize,NDec, Tail), not(member(X, Tail)).

(где TSize - это размер таблицы, N - это количество элементов, а последний -является результатом)

Предикат 'geni' генерирует число X в интервале [A; B].

Пример (2 элемента в таблице 2x2):

?- generate(2, 2, R).
R = [k(1, 1), k(1, 2)] ;
R = [k(1, 1), k(2, 1)] ;
R = [k(1, 1), k(2, 2)] ;
R = [k(1, 2), k(1, 1)] ;
R = [k(1, 2), k(2, 1)] ;
R = [k(1, 2), k(2, 2)] ;
R = [k(2, 1), k(1, 1)] ;
R = [k(2, 1), k(1, 2)] ;
R = [k(2, 1), k(2, 2)] ;
R = [k(2, 2), k(1, 1)] ;
R = [k(2, 2), k(1, 2)] ;
R = [k(2, 2), k(2, 1)] ;
false.

Он работает правильно, но слишком медленно, когда я использую более высокие числа.Я думаю, что предикат «гени» хорош, но что-то не так с «генерировать».Как я мог оптимизировать это?

Answer 1

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

Хвостовая рекурсия обычно достигается введением дополнительного аргумента функции (здесь: предикат), который служит аккумулятором, в котором накапливается конечный результат во время выполнения рекурсии, а затем на последнем рекурсивном шаге аккумулятор содержит полный результат. , Затем он просто передается обратно через шаги рекурсии.

generate_new(TSize, N, Result) :- generate_new(TSize, N, [], Result).

generate_new(_, 0, Result, Result) :- !.

generate_new(TSize, N, Temp, Result) :-
                    geni(1, X1, TSize),
                    geni(1, Y1, TSize),
                    X = k(X1, Y1),
                    NDec is N - 1,
                    \+ member(X, Temp),
                    generate_new(TSize, NDec, [X|Temp], Result).

Answer 2

Давайте подробнее рассмотрим, как работает алогритм. Он состоит из 3 частей:

1) Генерировать X

X=k(X1,Y1), geni(1,X1,TSize), 
geni(1,Y1,TSize), 

2) Сформировать хвост

NDec is N-1, 
generate(TSize,NDec, Tail), 

3) Проверьте все совпадения

not(member(X, Tail)).

На каждом уровне рекурсии он будет выполняться примерно так:

1) Сгенерировать X, 2) сгенерировать хвост, 3) проверить не удалось, 2) сгенерировать еще один хвост, 3) проверить снова не удалось ...

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

Так что сначала сгенерируйте хвост, и найдите соответствующий X.

generate(TSize, N, [X|Tail]) :-
    NDec is N-1, generate(TSize,NDec, Tail),
    X=k(X1,Y1), geni(1,X1,TSize), geni(1,Y1,TSize), 
    not(member(X, Tail)).

Короче говоря: из-за подхода обратного отслеживания сначала делайте дорогие вещи (например, рекурсию).

Answer 3

Это не полный ответ, но если вы используете SWI-Prolog, то вместо geni/3 вы можете использовать between/3, что, вероятно, быстрее.