Я пытаюсь изучить более совершенное логическое программирование, выполняя задачи, которые я уже решил на Java. В настоящее время я работаю над проблемой типа «Манкала», и мой код действительно дает правильный ответ, по большей части, по крайней мере ... Некоторые входы требуют трудного количества времени для решения, а в некоторых случаях компьютер заканчивается стека (например, начать ([111,111,111,111,111,45,45,111,45,111,111,111]).Оптимизация алгоритма Prolog
Интересно, как я могу оптимизировать свою программу так, что она работает на всех входах длины 12, и решает их достаточно быстро, по крайней мере.
Я попытался вставить некоторые разрезы, где, как я думал, они имели смысл в алгоритме минимизации, который, казалось, имел некоторые положительные эффекты. Возможно, есть другие вещи, которые я могу сделать, чтобы ускорить то, что я не знаю? помощь принимается.
% Facts.
empty(45). % "-"
occupied(111). % "o"
% Executes a move and updates the board.
executeMove([_, _, _ | R], 0, 1, 2, X, Y, Z, [X, Y, Z | R]).
executeMove([A, B, C | R], I, J, K, X, Y, Z, [A | T]) :- K1 is K - 1,
J1 is J - 1,
I1 is I - 1,
executeMove([B, C | R], I1, J1, K1, X, Y, Z, T).
% Tests if a move to the left can be made,
% i.e. there exists a substring "-oo".
tryLeft(L, I, J, K) :- I > 1,
nth0(I, L, X),
occupied(X),
nth0(J, L, Y),
occupied(Y),
nth0(K, L, Z),
empty(Z).
% Tests if a move to the right can be made,
% i.e. there exists a substring "oo-".
tryRight(L, I, J, K) :- I < 10,
nth0(I, L, X),
occupied(X),
nth0(J, L, Y),
occupied(Y),
nth0(K, L, Z),
empty(Z).
% Calculates the number of stones on the board.
stones([], 0).
stones([111|T], N) :- stones(T, N1),
N is N1 + 1,
!.
stones([_|T], N) :- stones(T, N).
% Algorithm for minimizing the number of stones
% on a board. Currently too inefficient.
tryMove(L, I) :- (
I < 12, % Iterate over the entire board
nth0(I, L, P), % Get the Ith character
( % If that character is a stone
occupied(P); % then we might be able to move
I1 is I + 1, % Otherwise, next iteration
tryMove(L, I1)
),
(
J is I + 1,
K is J + 1,
tryRight(L, I, J, K), % Test if a move can be made
executeMove(L, I, J, K, 45, 45, 111, Y), % Update the board
tryMove(Y, 0), % Test algorithm using the new board
calculate(Y); % Possibly update the minimum
true
), % Reset to the previous board
(
J is I - 1,
K is J - 1,
tryLeft(L, I, J, K), % Test if a move can be made
executeMove(L, K, J, I, 111, 45, 45, Y), % Update the board
tryMove(Y, 0), % Test algorithm using the new board
calculate(Y); % Possibly update the minimum
true
), % Reset to the previous board
I2 is I + 1,
tryMove(L, I2); % Iterate
true % Guarantees true output
).
% Reduces code duplication.
calculate(Y) :- stones(Y, F),
(nb_getval(min, M),
F < M,
nb_setval(min, F),
;
true).
% Game predicate.
start(L) :- stones(L, E),
nb_setval(min, E),
tryMove(L, 0),
nb_getval(min, M),
write(M),
nl.
Пожалуйста, задать новый вопрос, если вы измените предмет! – false