Home > Archive > Prolog > September 2006 > no backtrack
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| Trap D 2006-09-14, 7:01 pm |
| Hello
I'm trying to solve a problem : "How can you divide 8L of milk with
three cans of 3, 5 , and 8 L ?"
My code "works" but I get only one solution (and itsn't the best !).
Why don't I get all the solutions ?
Here is my code :
% lancement par
% separe([bidon(0,3), bidon(0,5), bidon(8, 8)], [[bidon(0,3),
bidon(0,5), bidon(8, 8)]], X).
separe([bidon(0,3), bidon(4,5), bidon(4,8)], X,X):-
writelist(X).
separe(L, M, N) :-
select(B1, L,L1),
select(B2, L1,L2),
separe(B1,B2, L2, M, N).
separe(B1,B2,L2,M,N) :-
transfert(B1, B2,B3,B4),
insert(B3,L2,L3),
insert(B4,L3,L4),
\+member(L4,M),
separe(L4,[L4|M],N).
% pour pouvoir transferer du liquide
% du bidon 1 au bidon 2
% Il faut que le volume VX soit plus grand que zero
% et que le bidon 2 ne soit pas plein (VY < CY)
transfert(bidon(VX, CX), bidon(VY, CY), bidon(VX1,CX),bidon(VY1,CY)) :-
VX > 0,
VY < CY,
DeltaV is CY-VY,
Verse is min(DeltaV, VX),
VX1 is VX - Verse,
VY1 is VY + Verse.
% I must insert to keep the order bidon(X,3), bidon(X,5), bidon(X,8)
insert(X, [], [X]).
insert(bidon(V1,C1), [bidon(V2, C2) | T],[bidon(V2, C2) | L2]) :-
C2 < C1, !,
insert(bidon(V1,C1), T, L2).
insert(X, Y, [X | Y]).
% edition de la liste solution
writelist([]):- nl.
writelist([H|T]):- writeln(H),writelist(T).
| |
| bart demoen 2006-09-14, 7:01 pm |
| On Thu, 14 Sep 2006 10:07:45 -0700, Trap D wrote:
> Hello
> I'm trying to solve a problem : "How can you divide 8L of milk with
> three cans of 3, 5 , and 8 L ?"
> My code "works" but I get only one solution (and itsn't the best !).
> Why don't I get all the solutions ?
For finding the best solution:
try reformulating the problem as a "find-shortest-path-in-a-graph"
problem: the nodes are the contents of the three cans, and two nodes
are connected when you can go from the contents described by the
first node to the contents described by the second node with just the
can manipulations that are allowed.
Once you have done that, you will see how to find all solutions (with or
without a cycle in the graph).
Cheers
Bart Demoen
| |
| Trap D 2006-09-15, 8:01 am |
|
bart demoen wrote:
> On Thu, 14 Sep 2006 10:07:45 -0700, Trap D wrote:
>
>
>
> For finding the best solution:
> try reformulating the problem as a "find-shortest-path-in-a-graph"
> problem: the nodes are the contents of the three cans, and two nodes
> are connected when you can go from the contents described by the
> first node to the contents described by the second node with just the
> can manipulations that are allowed.
> Once you have done that, you will see how to find all solutions (with or
> without a cycle in the graph).
>
> Cheers
>
> Bart Demoen
Thank you Bart for this advise, it's a good idea.
As I will have to build the graph without cycles, I can build it step
by step, finding all the nodes I can get with 1 step, then with 2 steps
..=2E, and when I find the solution, it's inevitably the best solution. Am
I right ?
Now, just for my curiosity, and also to understand Prolog mechanism,
why don't I have back-track ?
Cheers
Jo=EBl
| |
| bart demoen 2006-09-23, 7:00 pm |
| On Fri, 15 Sep 2006 07:55:03 -0700, Trap D wrote:
> As I will have to build the graph without cycles, I can build it step
> by step, finding all the nodes I can get with 1 step, then with 2 steps
> .., and when I find the solution, it's inevitably the best solution. Am
> I right ?
Yes. This technique falls under "breadth first".
> Now, just for my curiosity, and also to understand Prolog mechanism,
> why don't I have back-track ?
Not sure what yo mean by that: the query
?- separe([bidon(0,3), bidon(0,5), bidon(8, 8)], [[bidon(0,3),bidon(0,5),
bidon(8, 8)]], X).
surely has more than one solution in SWI.
Cheers
Bart Demoen
| |
| Trap D 2006-09-29, 7:01 pm |
| Hi
I think I have found the reason, it was the predicate insert that
didnot work.
Now I have change, I use a list of cans like that [bidon(5,x),
bidon(11,y), bidon(13,z), bidon(24, t)], and to insert cans in the good
order I just have to do
separe(B1,B2,L2,M,N) :-
transfert(B1, B2,B3,B4),
predsort(compare, [B3,B4 | L2], L3),
\+member(L3,M),
separe(L3,[L3|M],N).
instead of
separe(B1,B2,L2,M,N) :-
transfert(B1, B2,B3,B4),
insert(B3,L2,L3),
insert(B4,L3,L4),
\+member(L4,M),
separe(L4,[L4|M],N).
And it works well. backtrack gives me all the solutions. (should, for
that particular probleme because of the combinatory explosion
SWI-Prolog bugs, but for another simple probleme (divide 8L in 2 X 4
with cans of 3, 5 and 8L) it gives me all the solutions).
Cheers
Jo=EBl
|
|
|
|
|