#algorithm #prolog #idioms #logic-programming
#алгоритм #пролог #идиомы
Вопрос:
Я только сейчас начинаю изучать Prolog, поэтому я не знаком с обычным способом выполнения большинства задач.
По сути, у меня есть правило, которое выдает значение из входных данных:
ScoreFromInput(Input, Score) :- ...
И у меня есть список входных данных, которые являются просто числами. У меня возникли проблемы с выяснением, как найти входные данные, которые дают максимальный результат.
Это то, что у меня есть прямо сейчас, но я думаю, что это повторяется бесконечно:
bestInput(BestInput) :-
%#Bind the list of valid inputs
legalInputs(ValidInputs),
%# -1000 is a dummy score, it should get replaced on the first call to bestInputHelper
bestInputHelper(ValidInputs,-1000,BestInput).
%#I think this rule should work if the first input in the list is not the best one
bestInputHelper([Input|RestOfInputs],BestScore,BestInput):-
bestInputHelper(RestOfInputs,RestBestScore,BestInput),
ScoreFromInput(Input,BestScore),
RestBestScore > BestScore.
%#And this one if it is the best input
bestInputHelper([Input|RestOfInputs],BestScore,Input):-
bestInputHelper(RestOfInputs,RestBestScore,_RestBestInput),
ScoreFromInput(Input,BestScore),
RestBestScore =< BestScore.
Это то, что у меня есть на данный момент, но я полагаю, что есть гораздо более простой способ сделать это. Приветствуется любая помощь! Спасибо!
Комментарии:
1. Одна особенность именования в Prolog заключается в том, что предикаты должны начинаться со строчной буквы (имена переменных начинаются с верхнего регистра или подчеркивания). Итак, я изменил ScoreFromInput на scoreFromInput в своем ответе.
2. @hardmath: Ах да, спасибо, что указали на это. В моей реальной программе это так. Я просто переключил параметры на «ввод» и «оценка» здесь, чтобы их назначение было понятно кому-то, незнакомому с моей программой, и, думаю, я пропустил это.
Ответ №1:
Несмотря на недостаточное знакомство Криса с Prolog, описанный им подход может быть более эффективным способом поиска входных данных с максимальным результатом, чем у mat. Вместо выполнения квадратичного числа сравнений возможен подход, подобный подходу Криса, который линейно сканирует возможные входные данные.
Здесь maxScoreOfList /3 вернет лучший элемент Z и лучший результат B для списка допустимых входных данных в качестве третьего аргумента. Предикат завершится ошибкой в пустом списке.
maxScoreOfList(Z,B,[H|T]) :-
scoreFromInput(H,S),
maxScoreOfListAux(Z,B,H,S,T).
Необходима «вспомогательная» функция следующим образом, которая иллюстрирует «трюк» добавления некоторых дополнительных аргументов, чтобы при достижении конца входного списка выходные данные Z и B можно было привязать к лучшему элементу и баллу, найденному «на данный момент»:
maxScoreOfListAux(Z,B,Z,B,[ ]).
maxScoreOfListAux(Z,B,X,S,[H|T]) :-
scoreFromInput(H,Q),
( S >= Q
-> ( Y = X, R = S )
; ( Y = H, R = Q )
),
maxScoreOfListAux(Z,B,Y,R,T).
Комментарии:
1. Ааа, интересный способ делать вещи! Спасибо за альтернативный метод. К счастью, моя программа имеет дело с входными данными, достаточно маленькими для квадратичного алгоритма (максимум 24), но я, безусловно, вижу, что это более полезно для больших входных данных. Кроме того, я полагаю, что это правильный способ сделать то, для чего предназначался мой код. Спасибо!
Ответ №2:
Простой способ заявить, что входные данные являются лучшими, если нет лучшего ввода:
best_input(Best) :-
legal_inputs(Inputs),
member(Best, Inputs),
input_score(Best, Score),
( member(Better, Inputs), input_score(Better, S), S > Score).
Чтобы увидеть, что не так с вашим собственным кодом, попробуйте, например, графический трассировщик SWI-Prolog:
?- gtrace, best_input(Best).
И, пожалуйста, используйте_читаемые имена вместо нечитаемых.