La première étape du problème de réalisation des contraintes en Python
TL;DR
- Apprenez la définition de base de ce qu'est un problème de réalisation de contraintes. ――Je vais essayer de résoudre un problème très simple en écrivant du code en Python.
Quel est le problème de satisfaction des contraintes?
En anglais, c'est un problème de satisfaction de contraintes. Il est également écrit comme CSP en prenant l'acronyme.
Le problème est de trouver une condition dans une variable et une contrainte données qui peuvent éviter la contrainte dans la plage que la variable peut sélectionner.
Il se compose principalement des trois éléments suivants.
--variables: variables / éléments donnés --domains: gamme de choix que chaque variable peut prendre --constraints: contraintes données
Par exemple, supposons que vous vouliez mettre en place trois MTG, M. A, M. B et M. C, comme exemple d'un CSP très simple.
M. A a un horaire de 11 heures à 16 heures, M. B de 12 heures à 15 heures et M. C de 14 heures à 18 heures.
De plus, M. A occupe une excellente position à MTG et M. A doit fréquenter MTG. Si M. A participe, M. B et M. C peuvent participer à MTG individuellement, ou M. B et M. C peuvent participer à MTG en même temps (cependant, puisqu'il s'agit de MTG, au moins Un total de 2 personnes est requis).
Si vous affectez ce problème à des variables, des domaines et des contraintes, A, B et C seront des variables.
En outre, la plage horaire que chaque personne peut sélectionner (11 h 00 à 16 h 00 pour M. A) est des domaines, et les restrictions sont que M. A doit participer ou qu'au moins deux personnes sont requises pour MTG.
Préparez-vous au problème de satisfaction des contraintes et essayez de résoudre le problème avec Python
Le problème à résoudre avec Python cette fois
Comme c'est le tout premier, nous allons résoudre un problème très simple.
Utilisez 5 blocs adjacents comme indiqué ci-dessous.
Supposons que chacun de ces cinq blocs puisse prendre l'une des couleurs «rouge», «vert» et «bleu». Cependant, il existe une restriction selon laquelle la même couleur ne doit pas être adjacente.
Dans ce problème,
--variables: chaque bloc de ① à ⑤. --domaines: Cette fois, tous les blocs ont la même valeur, et vous pouvez sélectionner trois valeurs, "rouge", "vert" et "bleu". --constraints: Contraintes selon lesquelles la même couleur ne doit pas être adjacente.
Etc. Par exemple, il peut être résolu en attribuant les couleurs suivantes (il existe de nombreuses combinaisons qui remplissent les conditions).
(C'est un problème très simple, et il est facile à résoudre de manière intuitive, il n'est donc pas nécessaire d'écrire du code, mais comme mentionné ci-dessus, c'est la première fois, je vais donc procéder tel quel.)
Quoi utiliser
- Python 3.8.5
Ajouter des constantes pour les importations et les variables requises (noms de bloc) et les domaines (couleurs)
Pour le moment, nous préparerons les importations et les constantes nécessaires.
Puisque nous utiliserons des annotations de type, importez ce dont vous avez besoin depuis le module de saisie.
from typing import Dict, List, Optional
De plus, puisque les variables sont des blocs cette fois, chaque nom de bloc est défini comme une constante entre (1) à (5).
BLOCK_NAME_1: str = '①'
BLOCK_NAME_2: str = '②'
BLOCK_NAME_3: str = '③'
BLOCK_NAME_4: str = '④'
BLOCK_NAME_5: str = '⑤'
Puisque le domaine est la couleur que chaque bloc peut prendre, il est également défini comme rouge, vert et bleu avec une constante.
COLOR_RED: str = 'Red'
COLOR_GREEN: str = 'Green'
COLOR_BLUE: str = 'Blue'
Ajouter une classe pour la contrainte
Créez une classe unique de conditions de contrainte.
La contrainte est une phrase selon laquelle "la même couleur ne peut pas être définie entre des blocs adjacents", mais lors de sa manipulation dans le code, "les blocs ① et ② ne doivent pas être de la même couleur" "① Définissez les contraintes en instanciant des multiples de cette classe, tels que «les blocs ④ et ③ ne doivent pas avoir la même couleur» et «les blocs ④ et ⑤ ne doivent pas avoir la même couleur».
class ColoringConstraint:
def __init__(self, block_name_1: str, block_name_2: str) -> None:
"""
Une classe qui gère une contrainte de réglage de couleur de bloc.
Parameters
----------
block_name_1 : str
Le nom du premier bloc entre les blocs adjacents (① à ⑤).
block_name_2 : str
Le nom du deuxième bloc entre les blocs adjacents (①-⑤).
"""
self.block_name_1: str = block_name_1
self.block_name_2: str = block_name_2
def satisfied(self, current_color_assignment: Dict[str, str]) -> bool:
"""
La valeur booléenne indiquant si l'état d'allocation actuel répond à cette contrainte
avoir.
Parameters
----------
current_color_assignment : dict
État d'allocation actuel à chaque bloc. Bloquer le nom sur la clé,
Une chaîne de caractères de constantes de couleur est définie pour chaque valeur.
Returns
-------
result_bool : bool
Vrai et satisfaisant la condition de contrainte. Vérifiez dans les conditions suivantes
Sera exécuté.
-Si dans le dictionnaire attribué le premier bloc ou le second
Si le bloc n'a pas encore été attribué (bloc cible)
True est défini si la couleur n'a pas encore été définie sur.
-Défini si deux blocs ont déjà reçu une couleur
Vrai si les couleurs ne sont pas les mêmes, sinon
False est défini (chacun des deux blocs adjacents
Vrai si différentes couleurs sont définies.
"""
block_1_color_assigned: bool = \
self.block_name_1 in current_color_assignment
block_2_color_assigned: bool = \
self.block_name_2 in current_color_assignment
if not block_1_color_assigned or not block_2_color_assigned:
return True
color_1: str = current_color_assignment[self.block_name_1]
color_2: str = current_color_assignment[self.block_name_2]
if color_1 != color_2:
return True
return False
Dans le constructeur, les constantes de deux noms de blocs adjacents sont spécifiées. Par exemple, ① et ②, ① et ③.
La méthode satisfaite est une interface qui fait référence à la valeur d'allocation de couleur actuelle pour chaque bloc pour obtenir la valeur booléenne indiquant si la condition de contrainte est satisfaite.
True est renvoyé si aucune couleur n'a encore été attribuée au bloc ou si les couleurs entre les deux blocs sont différentes. Il sera utilisé pour la recherche dans le suivi arrière, qui sera abordé plus tard.
Définition des constantes dans la liste des variables, domaines, contraintes
Préparez les constantes de la liste qui stocke chaque valeur en utilisant uniquement les constantes et les classes des valeurs préparées. Chaque nom de constante est VARIABLES, DOMAINS, CONSTRAINTS.
VARIABLES: List[str] = [
BLOCK_NAME_1,
BLOCK_NAME_2,
BLOCK_NAME_3,
BLOCK_NAME_4,
BLOCK_NAME_5,
]
DOMAINS: List[str] = [
COLOR_RED,
COLOR_GREEN,
COLOR_BLUE,
]
CONSTRAINTS: List[ColoringConstraint] = [
ColoringConstraint(
block_name_1=BLOCK_NAME_1,
block_name_2=BLOCK_NAME_2),
ColoringConstraint(
block_name_1=BLOCK_NAME_1,
block_name_2=BLOCK_NAME_3),
ColoringConstraint(
block_name_1=BLOCK_NAME_2,
block_name_2=BLOCK_NAME_3),
ColoringConstraint(
block_name_1=BLOCK_NAME_3,
block_name_2=BLOCK_NAME_4),
ColoringConstraint(
block_name_1=BLOCK_NAME_3,
block_name_2=BLOCK_NAME_5),
ColoringConstraint(
block_name_1=BLOCK_NAME_4,
block_name_2=BLOCK_NAME_5),
]
Chaque valeur incluse dans CONSTRAINTS est ajoutée par la combinaison de blocs adjacents.
Ajout du traitement de recherche de retour en arrière
Cette fois, nous utilisons une technique appelée retour arrière pour calculer la combinaison d'allocations de couleurs pour chaque bloc qui répond aux conditions de contrainte.
Le suivi arrière peut être résumé comme suit.
- Tant que les conditions de contrainte sont remplies, la combinaison de blocs suivante est vérifiée une par une.
- Si la condition de contrainte ne peut pas être remplie, revenez à la condition précédente et essayez de remplir la condition de contrainte avec la valeur (couleur) du domaine suivant. --Si l'allocation des couleurs à tous les blocs est terminée, le résultat de la combinaison (allocation) est renvoyé et le traitement est arrêté.
Le contenu est similaire à ce que l'on appelle l'algorithme de recherche en profondeur d'abord écrit.
def backtracking_search(
current_color_assignment: Optional[Dict[str, str]]=None
) -> Optional[Dict[str, str]]:
"""
Résolvez le problème de satisfaction des contraintes en faisant marche arrière.
Notes
-----
La recherche est effectuée de manière récursive jusqu'à ce que toutes les allocations soient terminées.
Parameters
----------
current_color_assignment : dict or None, default None
État d'allocation actuel à chaque bloc. Bloquer le nom sur la clé,
Une chaîne de caractères de constantes de couleur est définie pour chaque valeur.
* Si None est spécifié, il sera initialisé avec un dictionnaire vide.
Returns
-------
current_color_assignment : dict or None
Un dictionnaire qui stocke les valeurs d'allocation lorsque les conditions de contrainte sont effacées.
"""
if current_color_assignment is None:
current_color_assignment = {}
#Si vous avez déjà alloué le nombre de variables
#Renvoyez le dictionnaire et arrêtez le traitement.
if len(current_color_assignment) == len(VARIABLES):
return current_color_assignment
unassigned_variables: List[str] = get_unassigned_variables(
current_color_assignment=current_color_assignment)
first_variable: str = unassigned_variables[0]
for domain_value in DOMAINS:
copied_assignment: Dict[str, str] = current_color_assignment.copy()
copied_assignment[first_variable] = domain_value
if is_valid_assignment(assignment=copied_assignment):
#Si les contraintes sont toujours respectées, la recherche est effectuée de manière récursive.
#Essayez d'attribuer des couleurs.
recursive_result_assignment: Optional[Dict[str, str]] = \
backtracking_search(
current_color_assignment=copied_assignment)
#Si aucune condition d'allocation valide n'est trouvée dans les résultats de la recherche,
#Parmi les valeurs suivantes du domaine
if recursive_result_assignment is None:
continue
return recursive_result_assignment
return None
def is_valid_assignment(assignment: Dict[str, str]) -> bool:
"""
Si l'état d'allocation de couleur cible répond à toutes les contraintes
Obtenez la valeur booléenne.
Parameters
----------
assignment : dict
Statut d'allocation à chaque bloc. La clé est le nom du bloc et la valeur est la couleur
Une chaîne de caractères constante est définie pour chacun.
Returns
-------
result_bool : bool
True est défini si toutes les contraintes sont satisfaites.
"""
for constraint in CONSTRAINTS:
satisfied: bool = constraint.satisfied(
current_color_assignment=assignment)
if not satisfied:
return False
return True
def get_unassigned_variables(
current_color_assignment: Dict[str, str]) -> List[str]:
"""
Obtenez une liste des noms de variables non attribués.
Parameters
----------
current_color_assignment : dict or None, default None
État d'allocation actuel à chaque bloc. Bloquer le nom sur la clé,
Une chaîne de caractères de constantes de couleur est définie pour chaque valeur.
Returns
-------
unassigned_variables : list of str
Une liste contenant des noms de variables non attribués.
"""
unassigned_variables: List[str] = []
for block_name in VARIABLES:
if block_name in current_color_assignment:
continue
unassigned_variables.append(block_name)
return unassigned_variables
Je vais vraiment le déplacer
Essayez de revenir en arrière et de voir les résultats de l'allocation des couleurs.
if __name__ == '__main__':
assignment: Optional[Dict[str, str]] = backtracking_search()
print(assignment)
{'①': 'Red', '②': 'Green', '③': 'Blue', '④': 'Red', '⑤': 'Green'}
Vous pouvez voir que les 4 blocs aux deux extrémités sont affectés au rouge et au vert, et le bloc du milieu reçoit le bloc bleu. Pour le moment, il semble que cela a fonctionné sans problème.
Code final complet
from typing import Dict, List, Optional
BLOCK_NAME_1: str = '①'
BLOCK_NAME_2: str = '②'
BLOCK_NAME_3: str = '③'
BLOCK_NAME_4: str = '④'
BLOCK_NAME_5: str = '⑤'
COLOR_RED: str = 'Red'
COLOR_GREEN: str = 'Green'
COLOR_BLUE: str = 'Blue'
class ColoringConstraint:
def __init__(self, block_name_1: str, block_name_2: str) -> None:
"""
Une classe qui gère une contrainte de réglage de couleur de bloc.
Parameters
----------
block_name_1 : str
Le nom du premier bloc entre les blocs adjacents (① à ⑤).
block_name_2 : str
Le nom du deuxième bloc entre les blocs adjacents (①-⑤).
"""
self.block_name_1: str = block_name_1
self.block_name_2: str = block_name_2
def satisfied(self, current_color_assignment: Dict[str, str]) -> bool:
"""
La valeur booléenne indiquant si l'état d'allocation actuel répond à cette contrainte
avoir.
Parameters
----------
current_color_assignment : dict
État d'allocation actuel à chaque bloc. Bloquer le nom sur la clé,
Une chaîne de caractères de constantes de couleur est définie pour chaque valeur.
Returns
-------
result_bool : bool
Vrai et satisfaisant la condition de contrainte. Vérifiez dans les conditions suivantes
Sera exécuté.
-Si dans le dictionnaire attribué le premier bloc ou le second
Si le bloc n'a pas encore été attribué (bloc cible)
True est défini si la couleur n'a pas encore été définie sur.
-Défini si deux blocs ont déjà reçu une couleur
Vrai si les couleurs ne sont pas les mêmes, sinon
False est défini (chacun des deux blocs adjacents
Vrai si différentes couleurs sont définies.
"""
block_1_color_assigned: bool = \
self.block_name_1 in current_color_assignment
block_2_color_assigned: bool = \
self.block_name_2 in current_color_assignment
if not block_1_color_assigned or not block_2_color_assigned:
return True
color_1: str = current_color_assignment[self.block_name_1]
color_2: str = current_color_assignment[self.block_name_2]
if color_1 != color_2:
return True
return False
VARIABLES: List[str] = [
BLOCK_NAME_1,
BLOCK_NAME_2,
BLOCK_NAME_3,
BLOCK_NAME_4,
BLOCK_NAME_5,
]
DOMAINS: List[str] = [
COLOR_RED,
COLOR_GREEN,
COLOR_BLUE,
]
CONSTRAINTS: List[ColoringConstraint] = [
ColoringConstraint(
block_name_1=BLOCK_NAME_1,
block_name_2=BLOCK_NAME_2),
ColoringConstraint(
block_name_1=BLOCK_NAME_1,
block_name_2=BLOCK_NAME_3),
ColoringConstraint(
block_name_1=BLOCK_NAME_2,
block_name_2=BLOCK_NAME_3),
ColoringConstraint(
block_name_1=BLOCK_NAME_3,
block_name_2=BLOCK_NAME_4),
ColoringConstraint(
block_name_1=BLOCK_NAME_3,
block_name_2=BLOCK_NAME_5),
ColoringConstraint(
block_name_1=BLOCK_NAME_4,
block_name_2=BLOCK_NAME_5),
]
def backtracking_search(
current_color_assignment: Optional[Dict[str, str]]=None
) -> Optional[Dict[str, str]]:
"""
Résolvez le problème de satisfaction des contraintes en faisant marche arrière.
Notes
-----
La recherche est effectuée de manière récursive jusqu'à ce que toutes les allocations soient terminées.
Parameters
----------
current_color_assignment : dict or None, default None
État d'allocation actuel à chaque bloc. Bloquer le nom sur la clé,
Une chaîne de caractères de constantes de couleur est définie pour chaque valeur.
* Si None est spécifié, il sera initialisé avec un dictionnaire vide.
Returns
-------
current_color_assignment : dict or None
Un dictionnaire qui stocke les valeurs d'allocation lorsque les conditions de contrainte sont effacées.
"""
if current_color_assignment is None:
current_color_assignment = {}
#Si vous avez déjà alloué le nombre de variables
#Renvoyez le dictionnaire et arrêtez le traitement.
if len(current_color_assignment) == len(VARIABLES):
return current_color_assignment
unassigned_variables: List[str] = get_unassigned_variables(
current_color_assignment=current_color_assignment)
first_variable: str = unassigned_variables[0]
for domain_value in DOMAINS:
copied_assignment: Dict[str, str] = current_color_assignment.copy()
copied_assignment[first_variable] = domain_value
if is_valid_assignment(assignment=copied_assignment):
#Si les contraintes sont toujours respectées, la recherche est effectuée de manière récursive.
#Essayez d'attribuer des couleurs.
recursive_result_assignment: Optional[Dict[str, str]] = \
backtracking_search(
current_color_assignment=copied_assignment)
#Si aucune condition d'allocation valide n'est trouvée dans les résultats de la recherche,
#Parmi les valeurs suivantes du domaine
if recursive_result_assignment is None:
continue
return recursive_result_assignment
return None
def is_valid_assignment(assignment: Dict[str, str]) -> bool:
"""
Si l'état d'allocation de couleur cible répond à toutes les contraintes
Obtenez la valeur booléenne.
Parameters
----------
assignment : dict
Statut d'allocation à chaque bloc. La clé est le nom du bloc et la valeur est la couleur
Une chaîne de caractères constante est définie pour chacun.
Returns
-------
result_bool : bool
True est défini si toutes les contraintes sont satisfaites.
"""
for constraint in CONSTRAINTS:
satisfied: bool = constraint.satisfied(
current_color_assignment=assignment)
if not satisfied:
return False
return True
def get_unassigned_variables(
current_color_assignment: Dict[str, str]) -> List[str]:
"""
Obtenez une liste des noms de variables non attribués.
Parameters
----------
current_color_assignment : dict or None, default None
État d'allocation actuel à chaque bloc. Bloquer le nom sur la clé,
Une chaîne de caractères de constantes de couleur est définie pour chaque valeur.
Returns
-------
unassigned_variables : list of str
Une liste contenant des noms de variables non attribués.
"""
unassigned_variables: List[str] = []
for block_name in VARIABLES:
if block_name in current_color_assignment:
continue
unassigned_variables.append(block_name)
return unassigned_variables
if __name__ == '__main__':
assignment: Optional[Dict[str, str]] = backtracking_search()
print(assignment)
De côté
――Parce que j'étais à l'origine diplômé d'une école dans le domaine du design, veuillez pardonner à Masakari qui a de solides connaissances dans le domaine de l'informatique.
Résumé du site de référence / référence
- Classic Computer Science Problems in Python
- [Problème de satisfaction des contraintes-Wikipedia](https://ja.wikipedia.org/wiki/%E5%88%B6%E7%B4%84%E5%85%85%E8%B6%B3%E5%95% 8F% E9% A1% 8C)
- [Back Tracking --Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AF%E3%83%88%E3%83%A9 % E3% 83% 83% E3% 82% AD% E3% 83% B3% E3% 82% B0)