KI-Glossar
Das vollständige Wörterbuch der Künstlichen Intelligenz
Programmation par Contraintes
Paradigme de programmation déclaratif où les relations entre les variables sont exprimées sous forme de contraintes, le système se chargeant automatiquement de trouver les solutions satisfaisantes.
CSP (Constraint Satisfaction Problem)
Problème mathématique défini par un ensemble de variables, leurs domaines respectifs et un ensemble de contraintes reliant ces variables, dont l'objectif est de trouver une assignation valide.
Domaine
Ensemble fini ou infini de valeurs possibles qu'une variable de décision peut prendre dans un problème de satisfaction de contraintes.
Contrainte
Relation logique ou mathématique restreignant les combinaisons de valeurs possibles pour un sous-ensemble de variables dans un problème CSP.
Consistance de nœud
Propriété selon laquelle chaque valeur dans le domaine d'une variable satisfait individuellement toutes les contraintes unaires associées à cette variable.
Consistance d'arc
Propriété garantissant que pour chaque valeur d'une variable, il existe au moins une valeur compatible dans le domaine de chaque variable voisine selon les contraintes binaires.
Consistance de chemin
Extension de la consistance d'arc assurant la compatibilité des assignations pour tout chemin de variables dans le graphe de contraintes.
Propagation de contraintes
Processus itératif de réduction automatique des domaines des variables en éliminant les valeurs qui violent localement les contraintes du problème.
Forward Checking
Technique d'élagage proactive qui, lors de l'assignation d'une variable, vérifie et ajuste immédiatement les domaines des variables non encore assignées.
Heuristique de variable
Stratégie ordonnant les variables selon des critères comme le plus petit domaine restant (MRV) ou le degré maximum pour optimiser la recherche.
Heuristique de valeur
Méthode sélectionnant l'ordre d'essai des valeurs pour une variable donnée, souvent basée sur le principe de moindre contrainte (LCV).
Recherche locale
Approche itérative améliorant progressivement une solution complète en modifiant localement les assignations pour réduire le nombre de contraintes violées.
Min-Conflicts
Algorithme de recherche locale sélectionnant aléatoirement une variable en conflit et lui assignant la valeur minimisant le nombre de contraintes violées.
AC-3 (Arc Consistency Algorithm 3)
Algorithme efficace établissant la consistance d'arc en utilisant une file d'attente pour propager les réductions de domaines entre les variables.
Contrainte globale
Contrainte de grande arité capturant une relation complexe entre de nombreuses variables, souvent traitée par des algorithmes de propagation spécialisés.
Optimisation par contraintes
Extension de la programmation par contraintes intégrant une fonction objectif à optimiser sous réserve du respect de toutes les contraintes.
Programmation logique avec contraintes
Paradigme combinant la programmation logique et la résolution de contraintes, permettant de résoudre des problèmes dans des domaines continus ou discrets.
Système de résolution de contraintes
Moteur algorithmique implémentant les mécanismes de propagation, de recherche et d'inférence nécessaires à la résolution automatique de problèmes CSP.