Der erste Schritt im Problem der Erfüllung von Einschränkungen in Python

TL;DR

--Lernen Sie die grundlegende Definition eines Problems zur Erfüllung von Einschränkungen. ――Ich werde versuchen, ein sehr einfaches Problem zu lösen, indem ich Code in Python schreibe.

Was ist das Problem der Einschränkungszufriedenheit?

Auf Englisch handelt es sich um ein Problem der Einschränkungszufriedenheit. Es wird auch als CSP geschrieben, indem das Akronym verwendet wird.

Das Problem besteht darin, eine Bedingung in einer bestimmten Variablen und Einschränkung zu finden, die die Einschränkung innerhalb des Bereichs vermeiden kann, den die Variable auswählen kann.

Es besteht hauptsächlich aus den folgenden drei Elementen.

--variablen: Gegebene Variablen / Elemente --domains: Auswahlmöglichkeiten, die jede Variable treffen kann

• Einschränkungen: Gegebene Einschränkungen

Angenommen, Sie möchten drei MTGs einrichten, Mr. A, Mr. B und Mr. C, als Beispiel für einen sehr einfachen CSP.

Herr A hat einen Zeitplan von 11:00 bis 16:00 Uhr, Herr B von 12:00 bis 15:00 Uhr und Herr C von 14:00 bis 18:00 Uhr.

Außerdem ist Herr A bei MTG in einer großartigen Position, und Herr A muss an MTG teilnehmen. Wenn Herr A teilnimmt, können Herr B und Herr C einzeln an MTG teilnehmen, oder sowohl Herr B als auch Herr C können gleichzeitig an MTG teilnehmen (da es sich jedoch zumindest um MTG handelt Es sind insgesamt 2 Personen erforderlich.

Wenn Sie dieses Problem Variablen, Domänen und Einschränkungen zuweisen, sind A, B und C Variablen.

Darüber hinaus ist der Zeitbereich, den jede Person auswählen kann (11:00 bis 16:00 für Herrn A), Domänen, und Einschränkungen bestehen darin, dass Herr A teilnehmen muss oder mindestens zwei Personen für MTG erforderlich sind.

Bereiten Sie sich auf das Problem der Einschränkungszufriedenheit vor und versuchen Sie, das Problem mit Python zu lösen

Das Problem, das diesmal mit Python gelöst werden muss

Da es das allererste ist, werden wir ein sehr einfaches Problem lösen.

Verwenden Sie 5 benachbarte Blöcke wie unten gezeigt.

Angenommen, jeder dieser fünf Blöcke kann eine der Farben "rot", "grün" und "blau" annehmen. Es gibt jedoch eine Einschränkung, dass dieselbe Farbe nicht benachbart sein darf.

In diesem Problem

--variablen: Jeder Block von ① bis ⑤. --domains: Dieses Mal haben alle Blöcke den gleichen Wert und Sie können drei Werte auswählen: "rot", "grün" und "blau".

• Einschränkungen: Einschränkungen, dass dieselbe Farbe nicht benachbart sein darf.

Und so weiter. Zum Beispiel kann es gelöst werden, indem die folgenden Farben zugewiesen werden (es gibt viele Kombinationen, die die Bedingungen erfüllen).

(Es ist ein sehr einfaches Problem, und es ist leicht intuitiv zu lösen, daher ist es nicht erforderlich, Code zu schreiben, aber wie oben erwähnt, ist es das erste Mal, also werde ich so weitermachen, wie es ist.)

Was zu verwenden

• Python 3.8.5

Fügen Sie Konstanten für erforderliche Importe und Variablen (Blocknamen) und Domänen (Farben) hinzu.

Vorerst werden wir die notwendigen Importe und Konstanten vorbereiten.

Da wir Typanmerkungen verwenden, importieren Sie das, was Sie benötigen, aus dem Typisierungsmodul.

from typing import Dict, List, Optional

Da Variablen diesmal Blöcke sind, wird jeder Blockname in (1) bis (5) als Konstante definiert.

BLOCK_NAME_1: str = '①'
BLOCK_NAME_2: str = '②'
BLOCK_NAME_3: str = '③'
BLOCK_NAME_4: str = '④'
BLOCK_NAME_5: str = '⑤'

Da Domänen die Farbe sind, die jeder Block annehmen kann, wird dies auch als Rot, Grün und Blau mit einer Konstanten definiert.

COLOR_RED: str = 'Red'
COLOR_GREEN: str = 'Green'
COLOR_BLUE: str = 'Blue'

Klasse für Einschränkung hinzufügen

Erstellen Sie eine einzelne Klasse von Einschränkungsbedingungen.

Mit anderen Worten, die Einschränkung ist ein Satz, dass "dieselbe Farbe nicht zwischen benachbarten Blöcken festgelegt werden kann", aber wenn sie tatsächlich im Code behandelt wird, "dürfen die Blöcke ① und ② nicht dieselbe Farbe haben" "① Definieren Sie Einschränkungen, indem Sie mehrere dieser Klassen instanziieren, z. B. "Blöcke ④ und ③ dürfen nicht dieselbe Farbe haben" und "Blöcke ④ und ⑤ dürfen nicht dieselbe Farbe haben".

class ColoringConstraint:

    def __init__(self, block_name_1: str, block_name_2: str) -> None:
        """
Eine Klasse, die eine Einschränkung für die Blockfarbeneinstellung behandelt.

        Parameters
        ----------
        block_name_1 : str
Der Name des ersten Blocks zwischen benachbarten Blöcken (① bis ⑤).
        block_name_2 : str
Der Name des zweiten Blocks zwischen benachbarten Blöcken (① bis ⑤).
        """
        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:
        """
Der boolesche Wert, ob der aktuelle Zuordnungsstatus diese Einschränkung erfüllt
erhalten.

        Parameters
        ----------
        current_color_assignment : dict
Aktueller Zuordnungsstatus für jeden Block. Blockname auf dem Schlüssel,
Für jeden Wert wird eine Zeichenfolge mit Farbkonstanten festgelegt.

        Returns
        -------
        result_bool : bool
Richtig und erfüllt die Randbedingung. Überprüfen Sie unter den folgenden Bedingungen
Wird durchgeführt.
            -Wenn im zugewiesenen Wörterbuch der erste Block oder der zweite
Wenn der Block noch nicht zugeordnet wurde (Zielblock)
True wird gesetzt, wenn die Farbe noch nicht eingestellt wurde.
            -Legen Sie fest, ob zwei Blöcken bereits Farbe zugewiesen wurde
Richtig, wenn die Farben nicht gleich sind, sonst
False wird gesetzt (jeweils zwei benachbarte Blöcke
True, wenn unterschiedliche Farben eingestellt sind.
        """
        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

Im Konstruktor werden die Konstanten zweier benachbarter Blocknamen angegeben. Zum Beispiel ① und ②, ① und ③.

Die erfüllte Methode ist eine Schnittstelle, die sich auf den aktuellen Farbzuordnungswert für jeden Block bezieht und den booleschen Wert erhält, ob die Einschränkungsbedingung erfüllt ist.

True wird zurückgegeben, wenn dem Block noch keine Farbe zugewiesen wurde oder wenn die Farben zwischen den beiden Blöcken unterschiedlich sind. Es wird für die Suche in der Rückverfolgung verwendet, auf die später noch eingegangen wird.

Definition von Konstanten in der Liste der Variablen, Domänen, Einschränkungen

Bereiten Sie die Konstanten der Liste vor, in der jeder Wert gespeichert ist, indem Sie nur die Konstanten und Klassen der vorbereiteten Werte verwenden. Jeder konstante Name ist 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),
]

Jeder in CONSTRAINTS enthaltene Wert wird durch die Kombination benachbarter Blöcke addiert.

Hinzufügung der Backtracking-Suchverarbeitung

Dieses Mal verwenden wir eine Technik namens Backtracking, um die Kombination der Farbzuordnungen für jeden Block zu berechnen, der die Randbedingungen erfüllt.

Die Rückverfolgung kann wie folgt grob zusammengefasst werden.

• Solange die Randbedingungen erfüllt sind, wird die nächste Blockkombination einzeln überprüft. --Wenn die Einschränkungsbedingung nicht erfüllt werden kann, kehren Sie zur vorherigen Bedingung zurück und versuchen Sie, die Einschränkungsbedingung mit dem Wert (Farbe) der nächsten Domäne zu erfüllen. --Wenn die Farbzuordnung zu allen Blöcken abgeschlossen ist, wird das Kombinationsergebnis (Zuordnung) zurückgegeben und die Verarbeitung gestoppt.

Der Inhalt ähnelt dem sogenannten zuvor geschriebenen Tiefensuchalgorithmus.

def backtracking_search(
        current_color_assignment: Optional[Dict[str, str]]=None
        ) -> Optional[Dict[str, str]]:
    """
Lösen Sie das Problem der Einschränkungszufriedenheit durch Zurückverfolgen.

    Notes
    -----
Die Suche wird rekursiv durchgeführt, bis alle Zuordnungen abgeschlossen sind.

    Parameters
    ----------
    current_color_assignment : dict or None, default None
Aktueller Zuordnungsstatus für jeden Block. Blockname auf dem Schlüssel,
Für jeden Wert wird eine Zeichenfolge mit Farbkonstanten festgelegt.
* Wenn Keine angegeben ist, wird es mit einem leeren Wörterbuch initialisiert.

    Returns
    -------
    current_color_assignment : dict or None
Ein Wörterbuch, in dem die Zuordnungswerte gespeichert werden, wenn die Einschränkungsbedingungen gelöscht werden.
    """
    if current_color_assignment is None:
        current_color_assignment = {}

    #Wenn Sie die Anzahl der Variablen bereits zugewiesen haben
    #Geben Sie das Wörterbuch zurück und beenden Sie die Verarbeitung.
    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):

            #Wenn die Einschränkungen weiterhin erfüllt sind, wird die Suche rekursiv durchgeführt.
            #Versuchen Sie, Farben zuzuweisen.
            recursive_result_assignment: Optional[Dict[str, str]] = \
                backtracking_search(
                    current_color_assignment=copied_assignment)

            #Wenn in den Suchergebnissen keine gültige Zuordnungsbedingung gefunden wird,
            #Von den folgenden Werten in der Domäne
            if recursive_result_assignment is None:
                continue
            return recursive_result_assignment
    return None


def is_valid_assignment(assignment: Dict[str, str]) -> bool:
    """
Gibt an, ob der Zielfarbzuweisungsstatus alle Einschränkungen erfüllt
Holen Sie sich den booleschen Wert.

    Parameters
    ----------
    assignment : dict
Zuordnungsstatus für jeden Block. Der Schlüssel ist der Blockname und der Wert ist die Farbe
Für jede wird eine konstante Zeichenfolge festgelegt.

    Returns
    -------
    result_bool : bool
True wird gesetzt, wenn alle Einschränkungen erfüllt sind.
    """
    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]:
    """
Ruft eine Liste nicht zugewiesener Variablennamen ab.

    Parameters
    ----------
    current_color_assignment : dict or None, default None
Aktueller Zuordnungsstatus für jeden Block. Blockname auf dem Schlüssel,
Für jeden Wert wird eine Zeichenfolge mit Farbkonstanten festgelegt.

    Returns
    -------
    unassigned_variables : list of str
Eine Liste mit den Namen nicht zugewiesener Elemente (Variablen).
    """
    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

Ich werde es tatsächlich bewegen

Versuchen Sie, das Backtracking auszuführen, und sehen Sie sich die Ergebnisse der Farbzuweisung an.

if __name__ == '__main__':
    assignment: Optional[Dict[str, str]] = backtracking_search()
    print(assignment)

{'①': 'Red', '②': 'Green', '③': 'Blue', '④': 'Red', '⑤': 'Green'}

Sie können sehen, dass die 4 Blöcke an beiden Enden rot und grün zugewiesen sind und der mittlere Block dem blauen Block zugewiesen ist. Derzeit scheint es ohne Probleme funktioniert zu haben.

Ganzer endgültiger Code

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:
        """
Eine Klasse, die eine Einschränkung für die Blockfarbeneinstellung behandelt.

        Parameters
        ----------
        block_name_1 : str
Der Name des ersten Blocks zwischen benachbarten Blöcken (① bis ⑤).
        block_name_2 : str
Der Name des zweiten Blocks zwischen benachbarten Blöcken (① bis ⑤).
        """
        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:
        """
Der boolesche Wert, ob der aktuelle Zuordnungsstatus diese Einschränkung erfüllt
erhalten.

        Parameters
        ----------
        current_color_assignment : dict
Aktueller Zuordnungsstatus für jeden Block. Blockname auf dem Schlüssel,
Für jeden Wert wird eine Zeichenfolge mit Farbkonstanten festgelegt.

        Returns
        -------
        result_bool : bool
Richtig und erfüllt die Randbedingung. Überprüfen Sie unter den folgenden Bedingungen
Wird durchgeführt.
            -Wenn im zugewiesenen Wörterbuch der erste Block oder der zweite
Wenn der Block noch nicht zugeordnet wurde (Zielblock)
True wird gesetzt, wenn die Farbe noch nicht eingestellt wurde.
            -Legen Sie fest, ob zwei Blöcken bereits Farbe zugewiesen wurde
Richtig, wenn die Farben nicht gleich sind, sonst
False wird gesetzt (jeweils zwei benachbarte Blöcke
True, wenn unterschiedliche Farben eingestellt sind.
        """
        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]]:
    """
Lösen Sie das Problem der Einschränkungszufriedenheit durch Zurückverfolgen.

    Notes
    -----
Die Suche wird rekursiv durchgeführt, bis alle Zuordnungen abgeschlossen sind.

    Parameters
    ----------
    current_color_assignment : dict or None, default None
Aktueller Zuordnungsstatus für jeden Block. Blockname auf dem Schlüssel,
Für jeden Wert wird eine Zeichenfolge mit Farbkonstanten festgelegt.
* Wenn Keine angegeben ist, wird es mit einem leeren Wörterbuch initialisiert.

    Returns
    -------
    current_color_assignment : dict or None
Ein Wörterbuch, in dem die Zuordnungswerte gespeichert werden, wenn die Einschränkungsbedingungen gelöscht werden.
    """
    if current_color_assignment is None:
        current_color_assignment = {}

    #Wenn Sie die Anzahl der Variablen bereits zugewiesen haben
    #Geben Sie das Wörterbuch zurück und beenden Sie die Verarbeitung.
    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):

            #Wenn die Einschränkungen weiterhin erfüllt sind, wird die Suche rekursiv durchgeführt.
            #Versuchen Sie, Farben zuzuweisen.
            recursive_result_assignment: Optional[Dict[str, str]] = \
                backtracking_search(
                    current_color_assignment=copied_assignment)

            #Wenn in den Suchergebnissen keine gültige Zuordnungsbedingung gefunden wird,
            #Von den folgenden Werten in der Domäne
            if recursive_result_assignment is None:
                continue
            return recursive_result_assignment
    return None


def is_valid_assignment(assignment: Dict[str, str]) -> bool:
    """
Gibt an, ob der Zielfarbzuweisungsstatus alle Einschränkungen erfüllt
Holen Sie sich den booleschen Wert.

    Parameters
    ----------
    assignment : dict
Zuordnungsstatus für jeden Block. Der Schlüssel ist der Blockname und der Wert ist die Farbe
Für jede wird eine konstante Zeichenfolge festgelegt.

    Returns
    -------
    result_bool : bool
True wird gesetzt, wenn alle Einschränkungen erfüllt sind.
    """
    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]:
    """
Ruft eine Liste nicht zugewiesener Variablennamen ab.

    Parameters
    ----------
    current_color_assignment : dict or None, default None
Aktueller Zuordnungsstatus für jeden Block. Blockname auf dem Schlüssel,
Für jeden Wert wird eine Zeichenfolge mit Farbkonstanten festgelegt.

    Returns
    -------
    unassigned_variables : list of str
Eine Liste mit den Namen nicht zugewiesener Elemente (Variablen).
    """
    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)

Beiseite

――Wenn ich ursprünglich Absolvent einer Schule im Bereich Design war, verzeihen Sie bitte Masakari, der über fundierte Kenntnisse im Bereich Informatik verfügt.

Referenz / Zusammenfassung der Referenzseite

• Classic Computer Science Problems in Python
• [Restriction Satisfaction Problem-Wikipedia](https://ja.wikipedia.org/wiki/%E5%88%B6%E7%B4%84%E5%85%85%E8%B6%B3%E5%95% 8F% E9% A1% 8C)
• [Zurückverfolgung - 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)