Discussion :

[djepro]

Bonjour à tous !

Voilà j'ai une base de faits qui est une liste de tâches:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
task(a, _, [b, f], 4).
task(b, [a], [h], 13).
task(c, _, [d], 4).
task(d, [c], [h], 15).
task(e, _, [g], 12).
task(f, [a], [g], 4).
task(g, [e, f], [i], 2).
task(h, [b, d], [i], 2).
task(i, [g, h], _, 2).

Le prédicat a 4 argument, le premier est le nom de la tâche, le second la liste des prédécesseurs (tâches qui doivent être finies avant de pouvoir commencer celle-ci), le troisième la liste des successeurs (tâches pouvant être commencées quand celle-ci est finie), le quatrième représente la durée de la tâche.

J'ai également un prédicat project qui contient une liste de toutes les tâches, project([a, b, c, d, e, f, g, h, i])

Dans la base de fait actuelle, A, C et E sont des tâches initiales, elles ont donc le 2ème argument vide. I est la tâche finale, le 3ème argument est vide.

Je récupère la durée de chaque tâche via :

Code :

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

duree(A, D) :- activite(A, _, _, B), D is B.

Et via ce bout de code, j'arrive à afficher la liste des tâches, avec le début de chaque tâche le plus rapide.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
displayTaches :- taches(L), printListe(L).
printListe([]).
printListe([X|Liste]) :- debut(X, A), writeln(X: A), printListe(Liste).
 
sumListe([], 0).
sumListe([X|Liste], N) :-
	debut(X, Y),
	duree(X, Z), sumListe(Liste, Reste), N is Y + Z + Reste.
 
debut(A, X) :-
	activite(A, L1, _, _), L1=[], X is 0;
	activite(A, L1, _, _), sumListe(L1, Y), X is Y.

Le soucis, c'est que la récursivité comptabilise a 2 fois, une fois par f et une fois par b. Je voudrais donc pouvoir obtenir une liste de tous les prédecesseurs d'une tâche ainsi que de ses propres prédécesseurs. Par exemple, pre(i, N) doit renvoyer [a, b, c ,d ,e ,f , g, h], pour le moment mon bout de code debut fait bien ça mais il y a du doublon :/

Merci d'avance à quiconque pourra m'aiguiller !

[Trap D]

Une solution toute bête qui vient immédiatement à l'esprit, est de faire un sort sur la liste des prédécesseurs, qui éliminera les doublons. Pas forcément très satisfaisant je l'avoue. Sinon, peut-être faut-il t(orienter vers le tri topologique :

Petite remarque, ce bout de code

Code :

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

duree(A, D) :- activite(A, _, _, B), D is B.

s'écrit avantageusement en

Code :

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

duree(A, D) :- activite(A, _, _, D).

Si tu utilises SWI-Prolog, une bibliothèque existe et te permet de faire

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
:- use_module(library(ugraphs)).
 
task(a, [], [b, f], 4).
task(b, [a], [h], 13).
task(c, [], [d], 4).
task(d, [c], [h], 15).
task(e, [], [g], 12).
task(f, [a], [g], 4).
task(g, [e, f], [i], 2).
task(h, [b, d], [i], 2).
task(i, [g, h], _, 2).
 
duree(A, D) :- activite(A, _, _, D).
 
pre(Tache, Pred) :-
	% mise au format de la bibliotheque
	setof(X-Y, A^B^task(X, A, Y, B), Lst),
	% le tri topologique de l'enchainement des tâches
	top_sort( Lst, TTS),
	% l'obtention de la liste pour la tache donnée
	append(Pred, [Tache | _], TTS).

exemple :

?- pre(i, Pred).
Pred = [a, f, b, c, d, h, e, g] ;
false.

Maintenant, c'est mieux si c'est toi qui &crit le tri ...

[Trap D]

On peut faire un parcours en largeur, en charchant à chaque etape les prédecesseurs et construire les chemins avec leur durée; à la fin on selectrionne le parcours le plus court.

[Trap D]

A part le vocabulaire que je ne connaissait pas, tout me parait normal.

La durée du projet est mise à 23 alors qu'elle devrait être de 58.

Ben non, le chemin le plus long pour aller du debut à la fin est [c, d, h i] qui dure 23, les autres branches ([a,b,h,i] [a,f,g,ii] et [e,g,i]) sont plus courtes et peuvent donc démarrer après et ne durent pas plus longtemps

Pareil pour les taches initiales, on est d'accord qu'elles commencent à 0 et pas à 7 comme la tache E

Non, une tâche est initiale s'il elle n'est précédée par aucune autre tâche, mais ça ne veut pas dire qu'elle doit commencer à 0; pour ne pas retarder le projet elle doit commencer au plus tard à 7, mais entre 0 et 7 c'est bon. Tu sembles oublier que les tâches s'effectuent en parallèles.