11
votes

Listes de commandes avec la programmation logique de contrainte

Je me demandais si quelqu'un pouvait m'aider avec ce problème: je dois commander une liste à l'aide de PRAGolog avec une programmation logique construite et je dois le faire avec la manière la plus efficace que je puisse.

donc le prédicat principal que j'ai défini. est la suivante: xxx

La mise en œuvre de chacun des précédents prédicats auxiliaires est la suivante: xxx

J'ai prouvé le programme que j'ai fait et ça marche! Mais je ne sais pas s'il est possible d'améliorer l'efficacité, et si c'est le cas, comment puis-je le faire (je lisais Cet ancien fil ici). Devrais-je ajouter ou modifier l'une des contraintes?

merci!

prolog list constraint-programming

2 commentaires

Votre approche consiste à essayer toutes les permutations d'une liste jusqu'à ce que vous en trouviez un trié dans l'ordre croissant. Nous pouvons faire quelque chose de plus efficace! Cependant, le peu de la programmation logique de contrainte semble être hors de propos. Bien que ce soit "programmation logique", aucune utilisation n'est faite (ou doit être faite) de contraintes telles que CLP < / a> les signifie habituellement. Êtes-vous obligé d'apporter des contraintes dans l'image en quelque sorte?

Oui. En effet, je dois essayer de contraindre, puis testez la solution, non seulement générer toutes les options possibles et vérifier. Pour cette raison, j'ai mis l'accent sur le CLP et pas seulement un simple prologiciel

3 Réponses :

11
votes

Votre définition de même_length / 2 code> ne se terminera pas très souvent. Au lieu de cela, considérons xxx pré>

de même, en utilisant bibliothèque (lambda) code> Utilisez p> xxx pré>

à la place de p> xxx pré>

Il semble que vous souhaitiez reformuler le tri en indiquant en premier, que la liste est commandée et que seule la recherche d'une permutation. Ci-dessous fonctionne dans Sicstus, SWI, YAP. P>

?- time(order([10,9,8,7,6,5,4,3,2,1],Xs)).
% 38,434,099 inferences, 10.655 CPU in 11.474 seconds (93% CPU, 3607101 Lips)

?- time(list_sorted2([10,9,8,7,6,5,4,3,2,1],Xs)).
% 50,139 inferences, 0.023 CPU in 0.032 seconds (72% CPU, 2205620 Lips)

7 commentaires

Merci beaucoup. Je l'ai testé et ça marche parfaitement. La seule chose que je n'ai pas comprise, c'est pourquoi vous m'avez dit que je devrais utiliser la bibliothèque de Lambda. Pourquoi c'est mieux que le prédicat 'idem_length'?

C'est mieux, car il est plus court. Maplist / 2,3 ... sont des prédicats très puissants, ils subsument la carte, Zip, ZipWith dans des langues fonctionnelles.


                                                
                                                                                            
                                                    Juste une autre question s'il vous plaît. Je n'ai jamais utilisé l'opérateur "quand" et je l'ai cherché sur Google mais je n'ai rien trouvé. Quelles sont les différences entre quand et faire un «si»                                                
                                                
                                                                                            
                                                    Un objectif  quand (cond, but)  signifie  but , mais il attendra pour exécuter  but  jusqu'à ce que  Cond  est satisfait . Je ne suis pas sûr que si vous vous référez à, il y a  (;) / 2  if-then-ele,  (->) / 2  et  si / 3  ou  (* ->) / 2 . Dans tous les cas, tous ceux-ci ne retardent pas l'exécution comme quand / 2 le fait.                                                

                                                
                                                                                            
                                                    À cause de  mappiste (\ _ _ _ ^ true, xs, ys) ,  Swish  augmente  procédure `(a, b, c) 'n'existe pas  pour la requête  heure (list_sorted2 ([10,9,8,7,6,5,4,3, 2,1], XS)). . Même lors de l'ajout  user_module (bibliothèque (Lambda)).  ou  user_module (bibliothèque (Appliquer)).  au début du programme.                                                

                                                
                                                                                            
                                                    @Maggero: semble être brisé.                                                
                                                
                                                                                            
                                                    Qu'est-ce que  \ _ ^ _ ^ true  signifie?


                            
                                
                                    3
 votes
                                
                            
                            
                                
                                     Voici  deux  em> les implémentations à l'aide de CLPFD. Les deux sont similaires aux variantes de «tri permutation» présentées dans des réponses antérieures. Cependant, les deux expressions "permutation" non pas en utilisant  permutation / 2  code>, mais par une combinaison de   élément / 3  code>  et   all_distinct / 1  code> . 
  Elément / 3  CODE> Les éléments de la liste triée sont tous membres de la liste d'origine.  all_distinct / 1  code> garantit que les indices d'élément sont tous différents les uns des autres les uns des autres.  p>  xxx  pré> 
 requête d'échantillon:  p>  xxx  Pré> 
 Que si l'argument  seconde  em> est connu et que le premier est inconnu?  p>  xxx  pré> 
 jusqu'à présent, si bon. Et si la liste à trier contient  Duplicats  em>?  P>  xxx  pré> 
 maintenant c'est beaucoup de réponses redondantes! Pouvons-nous faire mieux?  P> 
  Éliminer les réponses redondantes  H2> 
 Oui! Les réponses redondantes dans la requête ci-dessus peuvent être éliminées en ajoutant une contrainte relative aux éléments voisins de la liste triée et de leurs positions respectives dans la liste d'origine.  P> 
 la contrainte  z1 # = ==> N1 #  états: "Si deux éléments voisins de la liste triée sont égaux, leurs positions dans la liste d'origine doivent être commandées."  P> 
?- list_sorted2([5,4,4,3,3,2,2,1],Xs).
Xs = [1, 2, 2, 3, 3, 4, 4, 5] ;
false.

                                

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    4
 votes
                                
                            
                            
                                
                                     Comme je l'ai encore fonctionner un générateur réseau tri   pour la longueur  10  code> et porté le code (qui a été généré avec l'option "meilleur") à Prolog / clpfd. 
 vient ici  list_sorted__SN10 / 2  code> ( SN10  code> peuplements pour "tri taille du réseau 10"):  p> 
?- test_fdBitonicSort(before,9).
[before] testing length 1 (all permutations of [1]) ... DONE
% 27 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 334208 Lips)
[before] testing length 2 (all permutations of [1,2]) ... DONE
% 151 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 1824884 Lips)
[before] testing length 3 (all permutations of [1,2,3]) ... DONE
% 930 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 4308089 Lips)
[before] testing length 4 (all permutations of [1,2,3,4]) ... DONE
% 6,033 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 5124516 Lips)
[before] testing length 5 (all permutations of [1,2,3,4,5]) ... DONE
% 43,584 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 7722860 Lips)
[before] testing length 6 (all permutations of [1,2,3,4,5,6]) ... DONE
% 353,637 inferences, 0.033 CPU in 0.033 seconds (100% CPU, 10753040 Lips)
[before] testing length 7 (all permutations of [1,2,3,4,5,6,7]) ... DONE
% 3,201,186 inferences, 0.249 CPU in 0.249 seconds (100% CPU, 12844003 Lips)
[before] testing length 8 (all permutations of [1,2,3,4,5,6,7,8]) ... DONE
% 32,060,649 inferences, 2.595 CPU in 2.594 seconds (100% CPU, 12355290 Lips)
[before] testing length 9 (all permutations of [1,2,3,4,5,6,7,8,9]) ... DONE
% 340,437,636 inferences, 27.549 CPU in 27.541 seconds (100% CPU, 12357591 Lips)
true.

                                

                                                                    
                                    
                                    
                                        2 commentaires
                                        
                                                                                            
                                                    Une graine est nécessaire pour les résultats reproductibles.                                                
                                                
                                                                                            
                                                    @tapis. Par coïncidence, je cherchais dans le code de  Swi-prolog.org / PLDOC / DOC_FOR? Object = sicstus% 3AGET_Mutable / 2  ... J'avais oublié que l'API existait même (j'avais sûrement utilisé auparavant, dans Sicstus3 jours)! J'ai donc été "forcé" de demander la plus grande question ...