Pythonでの制約充足問題の第一歩

TL;DR

• 制約充足問題とはどんなものなのかの基本的な定義などを学びます。
• 実際にごくごくシンプルな問題をPythonでコードを書いて解いてみます。

制約充足問題とは

英語だとconstraint satisfaction problem。頭文字を取ってCSPなどとも表記されます。

与えられたいくつかの変数と制約で、その変数が選択できる範囲の中で制約を回避できる条件を見つけるという問題です。

主に以下の3つの要素から成り立っています。

• variables : 与えられた変数・要素
• domains : 各変数が取れる選択肢の範囲
• constraints : 与えられた制約

たとえば、ごく簡単なCSPの例としてAさんとBさんとCさんという3人のMTGを設定したいとします。

Aさんは11時～16時、Bさんは12時から15時、Cさんは14時から18時の時間がスケジュールが空いている状態です。

また、MTGではAさんが偉い立場で、MTGにはAさんは必ず出席しないといけないとします。Aさんが参加していればBさんとCさんは個別に1人ずつMTGに参加しても、もしくはBさんとCさん同時に2人MTGに参加してもOKとします（ただしMTGなので最低でも合計で2人は必要です）。

この問題をvariables、domains、constraintsに割り振ると、AさんBさんCさんの3人が変数（variables）となります。

また、各人が選択できる時間の範囲（Aさんであれば11時～16時）がdomainsとなり、Aさんが参加しないといけないとか最低限2人はMTGに必要という制約がconstraintsとなります。

制約充足問題の準備とPythonで問題を解いてみる

今回Pythonで解く問題

一番最初なのでごくごく簡単な問題を解いていきます。

以下のように5つの隣接したブロックを使います。

この5つの各ブロックはそれぞれ「赤」「緑」「青」のいずれかの色を取れるとします。ただし、同じ色が隣接してはいけないという制約を設けます。

この問題では、

• variables : ①～⑤までの各ブロック。
• domains : 今回は全てのブロックで同一の値で、「赤」「緑」「青」の三つの値が選択できる。
• constraints : 同じ色が隣接してはいけないという制約。

といったようになります。例えば以下のような色の割り振りで解くことができます（条件を満たす組み合わせはいくつもあります）。

（非常にシンプルな問題で、直観でもさくっと解けるのでコードを書くまでもない感じではありますが、前述の通り最初なのでこのまま進めていきます）

使うもの

• Python 3.8.5

必要なimportとvariables（ブロック名）とdomains（色）のための定数の追加

とりあえず必要なimportや定数などを準備していきます。

型アノテーションを使っていくので、typingモジュールから必要なものをimportしていおきます。

from typing import Dict, List, Optional

また、今回はvariablesがブロックとなるため、各ブロック名を①～⑤で定数として定義しておきます。

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

domainsが各ブロックが取れる色となるので、こちらも赤緑青として定数で定義しておきます。

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

制約用のクラスの追加

制約条件の単体のクラスを作っておきます。

制約は言葉にすると「隣り合うブロック同士で同じ色は設定できない」という一文になりますが、実際にコード上で扱う際には「①と②のブロックが同じ色になってはいけない」「①と③のブロックが同じ色になってはいけない」「④と⑤のブロックは同じ色になってはいけない」といったようにこのクラスを何個もインスタンス化して制約（constraints）を定義します。

class ColoringConstraint:

    def __init__(self, block_name_1: str, block_name_2: str) -> None:
        """
        ブロックの色設定の制約1つ分を扱うクラス。

        Parameters
        ----------
        block_name_1 : str
            隣接するブロック間の1つ目のブロックの名称（①～⑤）。
        block_name_2 : str
            隣接するブロック間の2つ目のブロックの名称（①～⑤）。
        """
        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:
        """
        現在の割り当て状況が、この制約を満たすかどうかの真偽値を
        取得する。

        Parameters
        ----------
        current_color_assignment : dict
            現在の各ブロックへの割り振り状況。キーにはブロック名、
            値には色の定数の文字列がそれぞれ設定されている。

        Returns
        -------
        result_bool : bool
            Trueで制約条件を満たしている状態。以下の条件でチェックが
            実行される。
            - もし割り当ての辞書内に1つ目のブロックもしくは2つ目の
                ブロックがまだ割り振られていない場合（対象のブロック
                に色がまだ設定されていない場合）にはTrueが設定される。
            - 既に2つのブロックに色が割り振られている場合、設定
                されている色が同一ではない場合はTrue、それ以外では
                Falseが設定される（隣接している2つのブロックそれぞれ
                で異なる色が設定されていればTrue）。
        """
        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

コンストラクタでは2つの隣接するブロック名の定数を指定する形にしています。たとえば①と②、①と③といった具合です。

satisfied メソッドは、現在の各ブロックへの色の割り振り値を参照して、制約条件を満たしているかの真偽値を取得するインターフェイスです。

色がまだ割り振られていないブロックであったり、もしくは2つのブロック間の色が異なればTrueが返ります。のちのち触れるバックトラッキングでの探索で使います。

variables、domains、constraintsのリストの定数の定義

準備した値単体の定数やクラスなどを使う形で、それぞれの値を格納したリストの定数を用意していきます。各定数名は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),
]

CONSTRAINTSに含める各値は、隣接するブロック同士の組み合わせ分追加しています。

バックトラッキングの探索の処理の追加

制約条件を満たす各ブロックの色の割り振りの組み合わせの算出には、今回はバックトラッキングという手法を使います。

バックトラッキングでは、大まかにまとめると以下のような制御になります。

• 制約条件を満たす限り、1つ1つ次のブロックの組み合わせが検証される。
• もし制約の条件を満たせられない状態になった場合には、直前の条件に戻って次のドメインの値（色）で制約条件を満たすかどうかを試す。
• もし全てのブロックへの色の割り振りが完了した場合には組み合わせ（割り振り）結果を返却して処理を停止する。

いわゆる以前書いた深さ優先探索（depth-first search）の探索のアルゴリズムに近い内容になっています。

def backtracking_search(
        current_color_assignment: Optional[Dict[str, str]]=None
        ) -> Optional[Dict[str, str]]:
    """
    バックトラッキングによる制約充足問題の解決を行う。

    Notes
    -----
    全ての割り当てが完了するまでは再帰的に探索が実行される。

    Parameters
    ----------
    current_color_assignment : dict or None, default None
        現在の各ブロックへの割り振り状況。キーにはブロック名、
        値には色の定数の文字列がそれぞれ設定されている。
        ※Noneを指定した場合には空の辞書で初期化される。

    Returns
    -------
    current_color_assignment : dict or None
        制約条件をクリアした状態での割り振りの値を格納した辞書。
    """
    if current_color_assignment is None:
        current_color_assignment = {}

    # 一通りの variables の数だけ割り振りが既に済んでいる場合には
    # 辞書を返却して処理を停止する。
    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):

            # 制約条件をまだ満たしている場合には再帰的に探索を行い、
            # 色の割り振りを試みる。
            recursive_result_assignment: Optional[Dict[str, str]] = \
                backtracking_search(
                    current_color_assignment=copied_assignment)

            # 探索結果で有効な割り振り条件が見つからなくなった場合には、
            # ドメイン内の次の値の
            if recursive_result_assignment is None:
                continue
            return recursive_result_assignment
    return None


def is_valid_assignment(assignment: Dict[str, str]) -> bool:
    """
    対象の色の割り振り状況が、全ての制約を満たしているかどうかの
    真偽値を取得する。

    Parameters
    ----------
    assignment : dict
        各ブロックへの割り振り状況。キーにはブロック名、値には色の
        定数の文字列がそれぞれ設定されている。

    Returns
    -------
    result_bool : bool
        一通りの制約条件を満たしていればTrueが設定される。
    """
    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]:
    """
    割り当てのされていない要素（variables）名のリストを取得する。

    Parameters
    ----------
    current_color_assignment : dict or None, default None
        現在の各ブロックへの割り振り状況。キーにはブロック名、
        値には色の定数の文字列がそれぞれ設定されている。

    Returns
    -------
    unassigned_variables : list of str
        割り当てがされていない要素（variable）名を格納したリスト。
    """
    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)

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

両端の4ブロックに赤と緑が割り振られ、真ん中のブロックに青のブロックが割り振られていることが分かります。とりあえずは問題なく動いてくれたようです。

最終コード全体

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:
        """
        ブロックの色設定の制約1つ分を扱うクラス。

        Parameters
        ----------
        block_name_1 : str
            隣接するブロック間の1つ目のブロックの名称（①～⑤）。
        block_name_2 : str
            隣接するブロック間の2つ目のブロックの名称（①～⑤）。
        """
        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:
        """
        現在の割り当て状況が、この制約を満たすかどうかの真偽値を
        取得する。

        Parameters
        ----------
        current_color_assignment : dict
            現在の各ブロックへの割り振り状況。キーにはブロック名、
            値には色の定数の文字列がそれぞれ設定されている。

        Returns
        -------
        result_bool : bool
            Trueで制約条件を満たしている状態。以下の条件でチェックが
            実行される。
            - もし割り当ての辞書内に1つ目のブロックもしくは2つ目の
                ブロックがまだ割り振られていない場合（対象のブロック
                に色がまだ設定されていない場合）にはTrueが設定される。
            - 既に2つのブロックに色が割り振られている場合、設定
                されている色が同一ではない場合はTrue、それ以外では
                Falseが設定される（隣接している2つのブロックそれぞれ
                で異なる色が設定されていればTrue）。
        """
        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]]:
    """
    バックトラッキングによる制約充足問題の解決を行う。

    Notes
    -----
    全ての割り当てが完了するまでは再帰的に探索が実行される。

    Parameters
    ----------
    current_color_assignment : dict or None, default None
        現在の各ブロックへの割り振り状況。キーにはブロック名、
        値には色の定数の文字列がそれぞれ設定されている。
        ※Noneを指定した場合には空の辞書で初期化される。

    Returns
    -------
    current_color_assignment : dict or None
        制約条件をクリアした状態での割り振りの値を格納した辞書。
    """
    if current_color_assignment is None:
        current_color_assignment = {}

    # 一通りの variables の数だけ割り振りが既に済んでいる場合には
    # 辞書を返却して処理を停止する。
    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):

            # 制約条件をまだ満たしている場合には再帰的に探索を行い、
            # 色の割り振りを試みる。
            recursive_result_assignment: Optional[Dict[str, str]] = \
                backtracking_search(
                    current_color_assignment=copied_assignment)

            # 探索結果で有効な割り振り条件が見つからなくなった場合には、
            # ドメイン内の次の値の
            if recursive_result_assignment is None:
                continue
            return recursive_result_assignment
    return None


def is_valid_assignment(assignment: Dict[str, str]) -> bool:
    """
    対象の色の割り振り状況が、全ての制約を満たしているかどうかの
    真偽値を取得する。

    Parameters
    ----------
    assignment : dict
        各ブロックへの割り振り状況。キーにはブロック名、値には色の
        定数の文字列がそれぞれ設定されている。

    Returns
    -------
    result_bool : bool
        一通りの制約条件を満たしていればTrueが設定される。
    """
    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]:
    """
    割り当てのされていない要素（variables）名のリストを取得する。

    Parameters
    ----------
    current_color_assignment : dict or None, default None
        現在の各ブロックへの割り振り状況。キーにはブロック名、
        値には色の定数の文字列がそれぞれ設定されている。

    Returns
    -------
    unassigned_variables : list of str
        割り当てがされていない要素（variable）名を格納したリスト。
    """
    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)

余談

• 元々デザイン方面の学校卒なので、コンピューターサイエンス方面で知識的に雑な点などへの強めのマサカリはご容赦くださいmm

参考文献・参考サイトまとめ

• Classic Computer Science Problems in Python
• 制約充足問題 - Wikipedia
• バックトラッキング - Wikipedia