Three-color classification problem of Constraint Satisfaction Problem

(22nd-March-2021)

• Three-color classification problemare following examples, the problem of dividing 6 prefectures in the Kanto region by three brown (Brown), Murasaki (Magenta), Light blue (Cyan) problems is called three color classification problem.

• A set of discrete values: D = {brown, violet, light blue} constraint set: the color of the adjacent region is Different thing

Answer by three colors is….

learned about constraint satisfaction problem

The problem formulation consists of

a set of variables V,

a set of discrete values D (area of variables),

a set of constraints (C or P)

• Goal: A set of variable value assignments that satisfy all constraints

• Solution:

1. Constraint propagation method

2. Backtracking method

3. Local search method (hill climbing method)