使用失败查找列表的最小值，回溯Prolog [英] Find min of list using fail, backtracking Prolog

问题描述

我想使用失败导致回溯的方式来计算列表的最小值.如何更改最小值(最小值，最小值，最小值)以使其正常工作.

I want to calculate the minimum of list, using fail which causes to backtrack. How do i change min(Min, X, Min), to make it work.

%min(X, A, B) X is the min of A, B
min(X, X, Y) :- X =< Y.
min(Y, X, Y) :- Y < X.

member(X, [X|_]).
member(X, [_|Ys]) :-
  member(X,Ys).

program :-
  Min is 1000,
  (member(X, [1, 2, 3, 4]),
  writeln(X),
  min(Min, X, Min), %This is wrong !
  fail;
  writeln(Min),
  true).

我以前的用于计算最小值的工作代码

My previous working code for calculating min

solve([Head|Rest], Ans) :-
   solve(Rest, Till),
   min(Ans, Head, Till). 

但是我不想这样做，至于调用solve，我正在做类似的事情

But i do not want to do this, as for calling solve, i am doing something like this

program :-
   findall(X, solve(List, X), Z).

导致找到X的所有解并存储在内存中.此方法不适用于大量输入，因此会被杀死.

which is causing to find all solutions of X and storing in memory. This method is not working for large inputs, getting killed.

因此，我想快速计算每个Solve调用的时间，而不是像使用findall那样进行存储.

Hence, i want to calculate the min of each solve call on fly and not store as did using findall.

推荐答案

如果您担心内存使用情况，则不应该使用猜测并检查的隐喻(使用失败意味着您正在使用).有一种O(n)算法完全不需要失败.

If you're worried about memory usage, you shouldn't be using a guess-and-check metaphor (which using failure implies you're using). There's an O(n) algorithm that doesn't require failure at all.

minlist(Min, [X|Xs]) :- minlist(X, Xs, Min).

minlist(Min, [], Min).
minlist(MinSoFar, [X|Xs], Min) :-
    min(NextMin, MinSoFar, X),
    minlist(NextMin, Xs, Min).

这篇关于使用失败查找列表的最小值，回溯Prolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！