Search for a result obtained, and find the lowest value in prolog

Question

I'm new to prolog, so lets go, I made a rule that returns me several result, I want to go through those results and find the lowest value, but I do not know how to do it.

Path is a list.
Cost is variable.

Cost is not the length of the list, cost is a cumulative variable. I just want to find the variable cost of lesser value among the results obtained. Finding the variable cost of lowest value and get the list bound to it.

%graph non-directed
route(a,b,1).
route(a,d,1).
route(a,h,1).
route(b,c,1).
route(b,a,1).
route(b,e,1).
route(c,b,1).
route(c,f,1).
route(c,e,1).
route(d,e,1).
route(d,a,1).
route(d,g,1).
route(e,b,1).
route(e,c,1).
route(e,d,1).
route(f,c,1).
route(f,i,1).
route(f,h,1).
route(g,d,1).
route(g,j,1).
route(g,l,1).
route(h,a,1).
route(h,f,1).
route(h,k,1).
route(i,f,1).
route(i,l,1).
route(i,k,1).
route(j,g,1).
route(j,m,1).
route(j,o,1).
route(k,h,1).
route(k,i,1).
route(k,n,1).
route(l,i,1).
route(l,o,1).
route(l,m,1).
route(l,g,1).
route(m,j,1).
route(m,l,1).
route(m,n,1).
route(n,m,1).
route(n,o,1).
route(n,k,1).
route(o,l,1).
route(o,n,1).
route(o,j,1).

travessiaCusto(A, B, Visitados,[B|Visitados], Custo1) :-route(A, B, Custo1).
travessiaCusto(A, B, Visitados, Cam, Custo) :-route(A, C, Custo2),
                                            C \== B,
                                            \+ member(C, Visitados),
               travessiaCusto(C, B, [C|Visitados], Cam, CustoResto),
               Custo is Custo2 + CustoResto.


caminhoCusto(A, B, Path, Cost) :-travessiaCusto(A, B, [A], Path, Cost).

copy(L,R) :- accCp(L,R).
accCp([],[]).
accCp([H|T1],[H|T2]) :- accCp(T1,T2).

The rules above run through a graph from two points and find all the possible routes for them. I'd like to use the rule:

caminhoCusto(A, B, Path, Cost) :-travessiaCusto(A, B, [A], Path, Cost).

My first attempt to get only one result, but contains recursive errors for in the if condition.

caminhoCustoMinimo(A,B,Path,Cost):-Cost is 100000000,
              ,caminhoCusto(A,B,Path1,Cost1)
              ,Cost1 =< Cost -> 
              (Cost is Cost1,copy(Path1,Path)).

In the above rule I tried to compare the values of the results with a value that I set initially, but without success.

This is very unclear. You are describing a cost and a path, which is understood in general. Then you're showing a sample query with 4 variables, and results showing two variables. There's no code attempt shown, no information about what your given data looks like. A lot of information missing. If you've tried something, you should show that code. — lurker
The query you're showing cannot provide the results you're showing. What happened to A and B in that query? — lurker
A and B is the nodes, they are only using to search the paths, the important thing is to find the lowest cost in the obtained in the rule caminhoCusto(A,B,Path,Cost). — Chance
A query to route needs to appear somewhere in your code, but it doesn't. — lurker

Jim Ashworth Jim Ashworth · Accepted Answer · 2017-02-21T10:03:29

findall(Y,caminhoCusto(A,B,_,Y),Costs) finds every route, and places the cost in a list.

sort(Costs,[Cost|_]) sorts the costs from smallest to largest, then takes the first (ie. smallest) element - this is essentially a min function, so if efficiency is key this could be rewritten.

findall(X,caminhoCusto(A,B,X,Cost),[Path|_]) finds every route with the minimum cost, then takes the first - this is to satisfy the 'only one route' requirement.

caminhoCustoMinimo(A,B,Path,Cost) :-
    findall(Y,caminhoCusto(A,B,_,Y),Costs),
    sort(Costs,[Cost|_]),
    findall(X,caminhoCusto(A,B,X,Cost),[Path|_]).

If you would prefer it to return each route with the minimum cost, one at a time, we replace [Path|_] with Paths, then use member(Path,Paths) to find each route with the minimum cost:

caminhoCustoMinimo(A,B,Path,Cost) :-
    findall(Y,caminhoCusto(A,B,_,Y),Costs),
    sort(Costs,[Cost|_]),
    findall(X,caminhoCusto(A,B,X,Cost),Paths),
    member(Path,Paths).

Search for a result obtained, and find the lowest value in prolog

1 Answers