TP Prolog - s07 - ISC IL 3a

###### tags: `prolog` # TP Prolog - s07 - ISC IL 3a ## Baudin Valentin et Braillard Simon ## Exercice 1 ```prolog= transition(jugs(contents(_,Vb), C, T), empty(a), jugs(contents(0, Vb),C, T)). transition(jugs(contents(Va,_), C, T), empty(b), jugs(contents(Va, 0),C, T)). transition(jugs(contents(_, Vb), capacity(A, B), T), fill(a), jugs(contents(A, Vb), capacity(A, B), T)). transition(jugs(contents(Va, _), capacity(A, B), T), fill(b), jugs(contents(Va, B), capacity(A, B), T)). transition(jugs(contents(Va, Vb), capacity(Ca, Cb), T), transfer(a, b), jugs(contents(A, B), capacity(Ca, Cb), T)) :- RemainingCapacity is Cb - Vb, A is max(Va - RemainingCapacity, 0), B is min(Va + Vb, Cb). transition(jugs(contents(Va, Vb), capacity(Ca, Cb), T), transfert(b, a), jugs(contents(A, B), capacity(Ca, Cb), T)) :- RemainingCapacity is Ca - Va, B is max(Vb - RemainingCapacity, 0), A is min(Va + Vb, Ca). ``` ### Output : La première solution est correcte mais n'est pas optimale étant donné qu'on remplis a pour le vider juste après. ```! | ?- > go(M). solveStateProblem(jugs(8,5,7),_279) M = [fill(a), fill(b), empty(a), transfert(b,a), fill(b), transfert(b,a), empty(a), transfert(b,a), fill(b), transfert(b,a)] ? ``` ## Exercice 2 ```prolog= initialState(cannibals(N, Cap), cannib(left, left(N,N), right(0,0), capacity(Cap))). finalState(cannib(right, left(0,0), _,_)). % M should not be less than C on a bank legalStateBank(0, _). legalStateBank(M, C) :- M >= C . legalState(cannib(_, left(LM, LC), right(RM, RC), _)) :- legalStateBank(LM, LC), legalStateBank(RM, RC). % Move left to right transition(cannib(left, left(LM, LC), right(RM, RC),capacity(Cap)), move(NM, NC), cannib(right, left(LM1, LC1), right(RM1, RC1), capacity(Cap))) :- nbBetween(0, LM, NM), NM =< Cap, nbBetween(0, LC, NC), NC =< Cap - NM, (NM + NC) > 0, LM1 is LM - NM, LC1 is LC - NC, RM1 is RM + NM, RC1 is RC + NC. % Move right to left transition(cannib(right, left(LM, LC), right(RM, RC),capacity(Cap)), move(NM, NC), cannib(left, left(LM1, LC1), right(RM1, RC1), capacity(Cap))) :- nbBetween(0, RM, NM), NM =< Cap, nbBetween(0, RC, NC), NC =< Cap - NM, (NM + NC) > 0, LM1 is LM + NM, LC1 is LC + NC, RM1 is RM - NM, RC1 is RC - NC. ``` ### Output : ```! | ?- > go(M). solveStateProblem(cannibals(3,2),_279) M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)] ? > a a M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)] M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)] M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)] M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)] M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)] M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)] M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)] (1 ms) no ``` ## Exercice 3 ```prolog= bfs(n(S,Ms), Queue, History, Moves) :- findall(n(S1,[M|Ms]), transition(S,M,S1), Ls), enqueueRelevantNodes(Ls, History, Queue, Queue1), fifo_apply(Queue1, dequeue(NextNode), Queue2), bfs(NextNode, Queue2, [S|History], Moves). enqueueRelevantNodes([], _, Queue, Queue). enqueueRelevantNodes([Node|Ls], History, Queue, Queue2) :- Node = n(S,_Ms), legalState(S), \+ member(S, History), !, fifo_apply(Queue, enqueue(Node), Queue1), enqueueRelevantNodes(Ls, History, Queue1, Queue2). ``` ### Output ex1 Si on relance maintenant l'exercice 1 en ajoutant le prédicat goBfs ainsi pour utiliser ce qui a été fait dans l'exercice 3 : ```prolog= goBfs(M) :- Goal=solveBfs(jugs(8,5,7), M), write(Goal), nl, Goal. ``` On obtient : ```! | ?- > goBfs(M). solveBfs(jugs(8,5,7),_279) M = [fill(b), transfert(b,a), fill(b), transfert(b,a), empty(a), transfert(b,a), fill(b), transfert(b,a)] ? ``` Ce qui est bien plus court que l'output de l'exercice 1. ### Output ex2 Si on relance maintenant l'exercice 2 en ajoutant le prédicat goBfs ainsi pour utiliser ce qui a été fait dans l'exercice 3 : ```prolog= goBfs(M) :- Goal=solveBfs(cannibals(3, 2), M), write(Goal), nl, Goal. ``` On obtient : ```! | ?- > goBfs(M). solveBfs(cannibals(3,2),_279) M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)] ? > a a M = [move(0,2),move(0,1),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)] M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(0,1),move(0,2)] M = [move(1,1),move(1,0),move(0,2),move(0,1),move(2,0),move(1,1),move(2,0),move(0,1),move(0,2),move(1,0),move(1,1)] (1 ms) no ``` On peut voir qu'il n'y a plus de doublon.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.