Как найти входные данные из списка, который дает максимальный результат по какому-либо запросу в SWI-Prolog? - PullRequest
Новая
       39

Как найти входные данные из списка, который дает максимальный результат по какому-либо запросу в SWI-Prolog?

3 голосов
/ 05 апреля 2011

Я сейчас просто беру Пролог, поэтому я не знаком с обычным способом выполнения большинства вещей.

По сути, у меня есть правило, которое дает значение из ввода: 

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.

Эточто я имею до сих пор, но я думаю, что есть гораздо более простой способ сделать это.Любая помощь приветствуется!Спасибо!

Ответы [ 2 ]

3 голосов
/ 05 апреля 2011

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

Здесь 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).
2 голосов
/ 05 апреля 2011

Простой способ заявить, что вход лучше, если нет лучшего входа: 

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).

И, пожалуйста, используйте_читаемые_имения вSteadOfUnreadableOnes.

...