Discussion :

[Louka4]

Bonjour,


je cherche un peu d'aide pour un programme SWI-Prolog qui m'a été demandé de réaliser pour un cours sur la programmation déclarative. Il s'avère que j'ai déjà une solution au problème demandé mais lorsque j'augmente la taille du problème, sa résolution prend trop de temps. Je vais donc exposer le problème et ce que j'ai déjà réalisé.


Problème :

Je possède deux containers de taille 10x10 ainsi que des objets, situés dans un fichier, exprimés comme ceci "object(Id, size(Height,Length,1))." (comme ajout, on peut s'intéresser à des containers en 3D d'où le 1 mais ce n'est pas mon but actuel)

Il faut pouvoir insérer le maximum d'objets dans ces deux containers sans que les objets ne flottent dans les airs, qu'ils ne soient pas scindés en plusieurs morceaux, qu'ils ne soient contenus que dans un des deux containers. Pour ce nombre maximal d'objets, je dois pouvoir donner tous les arrangements possibles.


Procédé :

Je travaille sur un seul container pour l'instant mais passer à deux ne me semble pas être un problème vu la façon dont j'ai défini ma résolution. C'est juste plus simple à tester!

Donc, je cherche une solution valide pour tous les objets, N objets. Si je ne trouve aucune solution, je passe à N-1 objets que je dois au pire tester N fois. Et ainsi de suite jusqu'à trouver une solution valide.
Dès que j'ai une solution valide, je conserve le nombre d'objets et je cherche toutes les solutions valides pour ce nombre.

Chercher une solution valide pour une liste de N objets revient à tester chaque placement valide des N objets dans le container (= contrainte d'objets non scindés) et ensuite, éliminer les placements qui ne respectent pas les contraintes d'objets flottant dans les airs. J'ai simplifié le fait de ne pas flotter dans les airs comme étant le fait que la partie inférieure de l'objet doit avoir un objet en dessous de lui ou alors, il s'agit du fond du container. Dans la réalité, il existe plus de cas valides.

Placer un objet revient à placer le composant en haut à gauche et ce dernier s'occupe de placer les composants sur la même ligne et la même colonne que lui. Il place également l'élément dans sa "diagonale" et entraine un appel récursif. Sa "diagonale" n'en est pas toujours si l'objet n'est pas carré.


Code :

Ci-dessous se trouve mon code brièvement commenté.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
height(3).
length(8).
 
 
test(File) :-
	getObjects(Objects,File),
	write('Objects = '),write(Objects), nl,
	nbObjects(NO,Objects),
	write('Nb objects = '),write(NO),nl,
	container(NO,Objects).
 
% recuperer les objets
getObjects(Objects,File) :-
	open(File,read,Str),
	read_file(Str,Objects),
	close(Str).
 
% transforme un objet en un composant de taille 1x1 avec une position
initComponents([],[]) :- !.
initComponents(O,[object(Id,size(H,L,_))|List]) :-
	initComponents(S,List),
	append([component(Id,pos(H,L))],S,O).
 
%-----------------------------
 
% renvoie le nombre d'objets maximal NO pour la liste d'objets Objects
nbObjects(NO, Objects) :-
	length(Objects, All),
	getValue(All,Objects,NO).
 
% recherche une solution valide pour N objets
getValue(N,Objects,Res) :-
	height(H),
	length(Ln),
	Size is H*Ln,
	length(L,Size),
	sol(N,Objects,R,_),
	initComponents(Components,R),
	cont(L,Components),
	Res is N,
	!.
getValue(N,Objects,Res) :-
	NewN is N-1,
	getValue(NewN,Objects,Res).
 
split(L, [], L).
 
split([T|Q], [T|L1], L2) :-
  split(Q, L1, L2).
 
% renvoie toutes les combinaisons possibles de prendre N objets
% dans X objets de la liste L (sans repetition)
% sol(2, [1,2,3,4],Res,_).
% Res = [1, 2] ;
% Res = [1, 3] ;
% Res = [1, 4] ;
% Res = [2, 3] ;
% Res = [2, 4] ;
% Res = [3, 4]
sol(0,L,[], L).
sol(N,L,[T|L3],R) :-
  N>0,
  split(L, L1, [T|L2]),
  N1 is N-1,
  sol(N1,L2,L3,L4),
  append(L1,L4,R).
 
% renvoie toutes les solutions valides pour N objets
container(N,Objects) :-
	sol(N,Objects,R,_),
	initComponents(Components,R),
	getSolution(Components), !.
 
% need cut because of counter (see getSolution)
 
% renvoie toutes les solutions valides pour une liste d'objets precise
getSolution(Components) :-
	height(H),
	length(Ln),
	Size is H*Ln,
	length(L,Size),
	flag(counter,_,0),
	cont(L,Components),
	verifyEmpty(L),
	print(L), nl,
	flag(counter,C,C+1),
	fail.
 
getSolution(_) :-
	flag(counter,C,C), nl,
	printCounter(C).
 
%-----------------------------
 
cont(_,[]).
cont(L,[X|O]) :-
	length(Ln),
	cont(L,O),
	cont_components(X,L,Ln).
 
cont_components(X,[Y|L],Ln) :- cond(X,Y), updateLn(Ln,NewLn), cont_components(X,L,NewLn).
cont_components(component(Id,pos(NRow,NCol)),[component(Id,pos(NRow,NCol))|L],Ln) :-
	Ln >= NCol,
	insertComponents(component(Id,pos(NRow,NCol)), L).
 
% evite des cas d'objets scindes en deux
% Exemple avec 3 lignes et 2 colonnes :
% 1 | 2
% -----
% 2 | 2
% -----
% 2 | 3
%
% Vision du container sous forme de liste :
% [component(1, pos(1,1)), component(2, pos(2,2)), component(2,
% pos(2,1)), component(2, pos(1,2)), component(2, pos(1,1)),
% component(3, pos(1,1))]
updateLn(1,NewLn) :- length(NewLn).
updateLn(Ln,NewLn) :- Ln \= 1, NewLn is Ln-1.
 
% insere un composant
insertComponents(component(Id,pos(NRow,NCol)),L) :-
	diagoComponent(component(Id,pos(NRow,NCol)),L),
	nextComponents(component(Id,pos(NRow,NCol)),L),
	subComponents(component(Id,pos(NRow,NCol)),L).
 
diagoCond(NRow,_) :- NRow \= 1, !.
diagoCond(_,NCol) :- NCol \= 1, !.
 
% place l'element dans la diagonale
diagoComponent(component(_,pos(1,1)),_).
diagoComponent(component(Id,pos(NRow,NCol)),L) :-
	diagoCond(NRow,NCol),
	diago(component(Id,pos(NRow,NCol)),Y,Size),
	skip(L,Size,[Y|L1]),
	insertComponents(Y,L1).
 
diago(component(Id,pos(1,XCol)),component(Id,pos(1,YCol)),0) :-
	YCol is XCol-1.
diago(component(Id,pos(XRow,1)),component(Id,pos(YRow,1)),Size) :-
	length(Length),
	Size is Length-1,
	YRow is XRow-1.
diago(component(Id,pos(XRow,XCol)),component(Id,pos(YRow,YCol)),Size) :-
	length(Size),
	YRow is XRow-1,
	YCol is XCol-1.
 
% place les composants avec le meme numero de colonne
subComponents(component(Id,pos(NRow,NCol)),L) :-
	length(Length),
	Size is Length-1,
	skip(L,Size,L1),
	subComp(component(Id,pos(NRow,NCol)),L1).
 
subComp(component(_,pos(1,_)),_).
subComp(component(Id,pos(XRow,XCol)),[component(Id,pos(YRow,XCol))|L]) :-
	XRow \= 1,
	YRow is XRow-1,
	subComponents(component(Id,pos(YRow,XCol)),L).
 
% place les composants avec le meme numero de ligne
nextComponents(component(_,pos(_,1)),_).
nextComponents(component(Id,pos(XRow,XCol)),[component(Id,pos(XRow,YCol))|L]) :-
	YCol is XCol-1,
	nextComponents(component(Id,pos(XRow,YCol)),L).
 
 
cond(_,Y) :- var(Y), !.
cond(X,Y) :- X \= Y.
 
% verifie si chaque composant ne flotte pas dans les airs
verifyEmpty([]) :- !.
verifyEmpty([X|L]) :- verifyEmptyCond(X), verifyEmpty(L), !.
verifyEmpty([component(_,pos(1,_))|L]) :-
	length(Length),
	Size is Length-1,
	skip(L,Size,L1),
	emp(L1),
	verifyEmpty(L).
 
verifyEmptyCond(X) :- var(X).
verifyEmptyCond(component(_,pos(NRow,_))) :- NRow \= 1.
 
emp([]) :- !.
emp([component(Id,pos(NRow,NCol))|_]) :- nonvar(Id),nonvar(NRow), nonvar(NCol).
 
%-----------------------------
% permet de se balader dans la liste
%
skip([],_,[]) :- !.
skip(Xs,0,Xs) :- !.
skip([_|Xs],K,Zs) :- K > 0, K1 is K-1, skip(Xs,K1,Zs).
 
%-----------------------------
 
% Affiche du container
 
print([]).
print(Xs) :- nl,
	printRow(Xs,Xs1),
	write('--------------------------------------'), nl,
	printRow(Xs1,Xs2),
	write('--------------------------------------'), nl,
	printRow(Xs2,_).
%	write('--------------------------------------'), nl,
%	printRow(Xs3,Xs4),
%	write('--------------------------------------'), nl,
%	printRow(Xs4,Xs5),
%	write('--------------------------------------'), nl,
%	printRow(Xs5,Xs6),
%	write('--------------------------------------'), nl,
%	printRow(Xs6,Xs7),
%	write('--------------------------------------'), nl,
%	printRow(Xs7,Xs8),
%	write('--------------------------------------'), nl,
%	printRow(Xs8,Xs9),
%	write('--------------------------------------'), nl,
%	printRow(Xs9,_).
 
printRow(Xs,Xs8) :-
	printElement(Xs,Xs1), write(' | '),
	printElement(Xs1,Xs2), write(' | '),
	printElement(Xs2,Xs3), write(' | '),
	printElement(Xs3,Xs4), write(' | '),
	printElement(Xs4,Xs5), write(' | '),
	printElement(Xs5,Xs6), write(' | '),
	printElement(Xs6,Xs7), write(' | '),
	printElement(Xs7,Xs8), nl.% write(' | '),
%	printElement(Xs8,Xs9), write(' | '),
%	printElement(Xs9,Xs10), nl.
 
printElement([X|Xs], Xs) :- var(X), !, write('.').
printElement([component(Id,_)|Xs], Xs) :- write(Id).
 
printCounter(0) :- !, write('No solution'), nl.
printCounter(1) :- !, write('1 solution'), nl.
printCounter(K) :- write(K), write(' solutions'), nl.
 
%-----------------------------
% Lecture du fichier
 
read_file(Stream,[]) :-
	at_end_of_stream(Stream), !.
 
read_file(Stream, [X|List]) :-
	\+ at_end_of_stream(Stream),
	read(Stream, X),
	read_file(Stream, List).

À savoir :

Alors, j'ai exécuté pas mal de tests sur un container de dimensions 3x8 avec un fichier "test.txt" comprenant ces 3 lignes :

object(1,size(1,2)).
object(2,size(2,3)).
object(3,size(2,3)).

J'obtiens bien 60 solutions différentes et dans un temps "rapide". Mais lorsque je passe à un container de dimensions 10x10, SWI-Prolog part dans les choux! Je sais qu'il va tester chaque placement et que donc, je dépend de la factorielle de positions dans mon container. Je ne vois pas trop ce que je peux faire pour ne plus en dépendre. J'avais voulu mettre un premier objet dans le fond du container et ensuite, placer le second mais là, il s'avère que l'ordre dans lequel je passe mes objets à une importance. De plus, tester tous les ordres entrainent une répétition de certaines solutions.


Toute idée d'accélération de la résolution ou amélioration du code est la bienvenue. Je ne suis pas un expert de Prolog et je ne cherche qu'à apprendre!


Merci d'avoir prêté attention à ma demande et bonne journée!


Louka4

[Trap D]

Bonjour

Projet très intéressant.
J'ai testé avec le code et le fichier contenant

object(1,size(1,2)).
object(2,size(2,3)).
object(3,size(2,3)).

et voici ce que j'ai obtenu :

1 ?- t.
Objects = [object(1,size(1,2)),object(2,size(2,3)),object(3,size(2,3))]
Nb objects = 0

. | . | . | . | . | . | . | .
--------------------------------------
. | . | . | . | . | . | . | .
--------------------------------------
. | . | . | . | . | . | . | .


1 solution
true.

Est-ce correct ?

[Louka4]

Il faut passer le chemin relatif ou absolu vers le fichier comme paramètre à test().

Donc, je suppose que tu as ajouté un prédicat t comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

t :- test('test.txt').

[Trap D]

J'ai fait ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
t :-
	test('C:/Users/Utilisateur/Documents/Prolog/test.txt').

[Louka4]

Je viens de reprendre le code sur le forum, j'y ai ajouté la même ligne de code avec le chemin absolu. J'obtiens bien les 60 solutions souhaitées. Je ne comprends donc pas pourquoi le programme ne s'arrête pas à 3 objets.

test.txt contient bien les 3 lignes suivantes?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
object(1,size(1,2)).
object(2,size(2,3)).
object(3,size(2,3)).

[Trap D]

Oui, j'utilise SWI-Prolog version 6.5.3

[Louka4]

Ah ok, je vois d'où vient le problème, c'est ridicule!

À force de travailler sur des containers en 2D, j'oublie que les données du fichier sont en 3D.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
object(1,size(1,2,1)).
object(2,size(2,3,1)).
object(3,size(2,3,1)).

Désolé.

[Trap D]

Ça marche déjà beaucoup mieux !

En mettant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
height(10).
length(10).

dans le programme et en gardant le même fichier j'ai obtenu 306 solutions en 90 secondes.

[Louka4]

Oui, j'obtiens le même résultat avec à peu près le même temps, même si celui-ci varie en fonction du cpu.

Il n'est pas encore trop lent car Prolog trouve rapidement une solution valide et peut ainsi passer à la recherche de toutes les solutions valides pour ce même nombre d'objets. De plus, le nombre de placements possibles via le prédicat cont dépend du nombre d'objets et de la taille du container.

En fait, je souhaite améliorer mon prédicat cont car pour l'instant, il cherche juste à placer mes objets sans se préoccuper s'ils reposent sur un autre objet ou bien le fond du container. Partons de cet exemple ci-dessous :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
object(1,size(1,1,1)).
object(2,size(1,1,1)).
object(3,size(1,1,1)).

cont trouvera 120 solutions et parmi ces 120 solutions, après avoir testé verifyEmpty, il restera 42 solutions.
De manière générale, cont trouvera N!/(N-O)! solutions pour une liste L d'objets où N est la taille du container et O est le nombre d'objets dans la liste L.
En fonction du nombre d'objets et s'ils n'entrent pas tous dans le container, je risque d'appeller très souvent cont, ce serait bien de pouvoir imbriquer verifyEmpty dans cont mais je n'arrive pas à l'exprimer.

Je me demandais aussi si, en déplaçant mon "cut" dans getValue et/ou en ajoutant un prédicat, je pouvais arrêter la recherche à un nombre d'objets N précis tout en ayant toutes les solutions valides pour toutes les combinaisons N objets.
En effet, dans le pire cas, si je trouve une solution valide pour N objets mais que c'était la dernière combinaison possible de N objets, alors je suis reparti dans getSolution pour retester toutes les autres combinaisons sans trouver la moindre nouvelle solution.

[Trap D]

Je n'ai pas encore etudié de manière approfondie ton code, j'ai simplement réécrit le code de sol :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
sol(N, Conteneur, R) :-
	sol(N, Conteneur, [], R).
 
sol(0, _, R, R).
sol(N, Cont, T, R) :-
	N > 0,
	select(Elem, Cont, Cont1),
	N1 is N - 1,
	sol(N1, Cont1, [Elem | T], R).

Je ne pense pas avoir changé la sémantique de sol/3 !

[Louka4]

Ah oui, ça conserve l'idée et le code est amélioré! Merci.

[Louka4]

Une idée qui m'a été proposée par un ami et que je vais réexpliquer avec mes mots :

Si je place un objet et qu'il y a du vide en-dessous, alors je regarde la liste des objets restants, j'élimine ceux dont la hauteur est plus grande que celle de cet espace vide. Avec les objets restants suite à ce filtrage, je vérifie si la somme de leur longueur est au moins égale à celle de mon objet flottant dans les airs.

S'il y a un moyen d'être encore plus précis que ça, je veux bien qu'on me le propose. Car cette solution n'est pas parfaite mais évite déjà d'inspecter pas mal de branches dans le backtracking.