Algorithme de recherche d'union dynamique dans Prolog

Question

Supposons que j'ai des ensembles S1, .., Sn et que nous voulons trouver les plus petites couvertures C1, .., Cm de sorte que dans chaque couverture il n'y ait jamais de composants connectés disjoints.

par exemple avec les ensembles S1 = [X, Y], S2 = [Y, Z], S3 = [T] je trouverais les couvertures C1 = [X, Y, Z] et C2 = [T]. Qu'en est-il d'un algorithme dynamique capable de fractionner les couvertures de manière dynamique?

Supposons que l'élément Y meurt, alors nous nous retrouvons avec S1 '= [X], S2' = [Z] et S3 '= [T]. Les couvertures sont maintenant C1 '= [X], C2' = [Z] et C3 '= [T]. Le nombre de couvertures a donc augmenté.

L'algorithme de recherche d'union peut déterminer une couverture pour une collection donnée d'ensembles, mais j'ai peur que recalculer la collection complète chaque fois qu'un élément meurt ne soit pas efficace.

Answer 1

Pour exploiter les ressources d'un système Prolog, j'ai créé un petit algorithme de recherche d'union basé sur copy_term / 2 et keysort / 2. Le point d'entrée principal de l'algorithme ici fait ce qui suit:

covers(L, S) :-
   vars_list(L, K),
   copy_term(K, R),
   make_keys(L, R, H),
   keysort(H, J),
   collect_keys(J, S).

Voici un exemple d'exécution:

?- covers([X+Y,Y+Z,T], C).
C = [[X+Y, Y+Z], [T]]

Pour obtenir un algorithme dynamique, nous pourrions essayer ce qui suit. Maintenez une structure rétrocontrôlable qui permet de trouver des couvertures à partir d'éléments. Ensuite, si un élément meurt, ne recalculez que la couverture qui appartient à l'élément mort.

Cela réduirait un peu la complexité. Sinon, je n'ai pas de meilleure idée ici, sauf l'observation qu'un élément mort ne divise que sa propre couverture en couvertures plus petites.

Answer 2

Je pense qu'il y a deux parties difficiles à cela:

• une structure de données cartographiques très efficace
• une structure de données efficace pour garder une trace de ce qu'il faut recalculer

La structure de données union-find elle-même est déjà implémentée dans Prolog mais cachée derrière le nom quelque peu obscur de "variables". Si vous avez un moyen d'associer des termes à des variables représentant leurs classes d'équivalence de recherche d'union, alors:

• l' findopération est la recherche de la variable de classe
• le test pour savoir si deux classes sont identiques est Class1 == Class2
• l' unionopération estClass1 = Class2

Il en findva de même pour un goulot d'étranglement. Dans les langages impératifs, la recherche est généralement en temps constant, en utilisant quelque chose comme foo.equivalence_classou equivalence_classes[foo.id]. Dans Prolog, nous n'avons pas de mappage équivalent en temps constant (presque), en général. Mais comme vous ne semblez s'intéresser qu'aux variables, les variables attribuées par SWI-Prolog font l' affaire!

Nous pouvons calculer les classes d'équivalence union-find pour une liste de termes comme celui-ci:

compute_classes([]).
compute_classes([Term | Terms]) :-
    term_variables(Term, Variables),
    variables_class(Variables, _NewEquivalenceClass),
    compute_classes(Terms).

variables_class([], _EquivalenceClass).
variables_class([Var | Vars], EquivalenceClass) :-
    (   get_attr(Var, equivalence_class, ExistingEquivalenceClass)
    ->  ExistingEquivalenceClass = EquivalenceClass
    ;   put_attr(Var, equivalence_class, EquivalenceClass) ),
    variables_class(Vars, EquivalenceClass).

En utilisant votre exemple:

?- compute_classes([X+Y, Y+Z, T]).
put_attr(X, equivalence_class, _2772),
put_attr(Y, equivalence_class, _2772),
put_attr(Z, equivalence_class, _2772),
put_attr(T, equivalence_class, _2814).

Nous pouvons en quelque sorte voir cela X, Yet Ztous partagent une classe d'équivalence, et Tsont dans une classe séparée.

Quelques utilitaires:

var_class(Var, Class) :-
    get_attr(Var, equivalence_class, Class).

var_var_sameclass(Var1, Var2) :-
    var_class(Var1, Class1),
    var_class(Var2, Class2),
    Class1 == Class2.

var_var_union(Var1, Var2) :-
    var_class(Var1, Class1),
    var_class(Var2, Class2),
    Class1 = Class2.

Poursuivant l'exemple:

?- compute_classes([X+Y, Y+Z, T]), var_class(X, ClassX), var_class(Y, ClassY), var_class(T, ClassT).
ClassX = ClassY,
put_attr(X, equivalence_class, ClassY),
put_attr(Y, equivalence_class, ClassY),
put_attr(Z, equivalence_class, ClassY),
put_attr(T, equivalence_class, ClassT).

?- compute_classes([X+Y, Y+Z, T]), var_var_sameclass(X, Y).
put_attr(X, equivalence_class, _3436),
put_attr(Y, equivalence_class, _3436),
put_attr(Z, equivalence_class, _3436),
put_attr(T, equivalence_class, _3478).

?- compute_classes([X+Y, Y+Z, T]), var_var_sameclass(X, T).
false.

?- compute_classes([X+Y, Y+Z, T]), var_var_union(Z, T), var_var_sameclass(X, T). 
put_attr(X, equivalence_class, _3502),
put_attr(Y, equivalence_class, _3502),
put_attr(Z, equivalence_class, _3502),
put_attr(T, equivalence_class, _3502).

C'est, Xet Ysont vraiment dans la même classe, alors que Xet Tne le sont pas. Si nous réunissons les classes pour Zet T, alors soudainement Xet Tsont dans la même classe.

Tuer des variables est là où cela devient plus fastidieux. L'idée ici (comme vous l'avez suggéré dans la question) est de ne recalculer que les parties «affectées» de l'entrée. Je pense que cela peut être fait en associant un ensemble de termes affectés à chaque classe d'équivalence. J'utiliserai des listes ici, mais je ne suggère pas que les listes soient un bon choix dans la pratique.

Calcul des classes d'équivalence pour une liste de termes et une "liste de surveillance" pour chaque classe d'équivalence:

compute_classes_and_watchlists(Terms) :-
    compute_classes(Terms),
    maplist(compute_watchlist, Terms).

compute_watchlist(Term) :-
    term_variables(Term, [RepresentativeVariable | _OtherVars]),
    var_class(RepresentativeVariable, Class),
    (   get_attr(Class, class_watchlist, Watchlist)
    ->  true
    ;   Watchlist = [] ),
    put_attr(Class, class_watchlist, [Term | Watchlist]).

Par exemple:

?- compute_classes_and_watchlists([X+Y, Y+Z, T]).
put_attr(X, equivalence_class, _2932),
put_attr(_2932, class_watchlist, [Y+Z, X+Y]),
put_attr(Y, equivalence_class, _2932),
put_attr(Z, equivalence_class, _2932),
put_attr(T, equivalence_class, _3012),
put_attr(_3012, class_watchlist, [T]).

Donc, si vous supprimiez l'un des X, You Z, la liste de surveillance de leur classe _2932vous dirait que vous auriez besoin de recalculer les classes d'équivalence pour les termes Y+Zet X+Y(mais rien d'autre).

Killing itself grabs the killed variable's class and its watchlist (which it "returns") and clears the equivalence class for each variable in that class:

kill_var(Var, TermsToRecompute) :-
    var_class(Var, Class),
    get_attr(Class, class_watchlist, TermsToRecompute),
    del_attr(Class, class_watchlist),
    maplist(clear_class, TermsToRecompute).

clear_class(Term) :-
    term_variables(Term, [RepresentativeVariable | _OtherVars]),
    del_attr(RepresentativeVariable, equivalence_class).

Killing only makes sense if you immediately (a) bind the killed variable to a ground term, and (b) recompute the equivalence classes for the affected terms. In your example:

?- compute_classes_and_watchlists([X+Y, Y+Z, T]), kill_var(Y, TermsToRecompute), Y = y_is_now_bound, compute_classes_and_watchlists(TermsToRecompute).
Y = y_is_now_bound,
TermsToRecompute = [y_is_now_bound+Z, X+y_is_now_bound],
put_attr(X, equivalence_class, _4640),
put_attr(_4640, class_watchlist, [X+y_is_now_bound]),
put_attr(Z, equivalence_class, _4674),
put_attr(_4674, class_watchlist, [y_is_now_bound+Z]),
put_attr(T, equivalence_class, _4708),
put_attr(_4708, class_watchlist, [T]).

This is getting hard to read, but the point is that after killing and binding Y and recomputing the union-find structure over the affected terms, X and Z are now in separate equivalence classes. T is just sitting around unaffected.

All of this kind of assumes that you won't backtrack across a union, although my reading of SWI's attributed var docs is that this wouldn't even do anything terribly wrong. Since put_attr is backtrackable, with some more care this might turn out to be a fairly flexible implementation in which backtracking simply splits classes apart again. Backtracking across a kill could also be made to work, I think.

TODOs:

• in the watchlist case, the definition of var_var_union must be changed to merge the watchlists for the two classes (if they are distinct); for actual lists this would be append, but some actual set or more specialized data structure would be better, especially if you expect to have some sort of "stack-like" behavior where the next variable to be killed is most likely one on which you did a recent union operation
• especially with the watchlist approach, users must be prevented from accidentally unifying equivalence_class terms; this could be done by using some sort of class(<unique_id>, NakedClassVariable) instead of just the naked variable to represent an equivalence class
• the repeated calls to term_variables could probably be be optimized somehow -- in addition to a watchlist of terms, you could also keep a watchlist of the variables of interest

All in all, this is not quite production ready code, but it might give you some ideas.