Constructive Methods of AI

Constructive Methods

    Constructive method is the direct approach which finds value to be assigned to variable by a calculating each and every step. The process starts at no assignments done. At each step we construct possible states by assigning all Possible values to variable which satisfies the constraints.

    Consider Four-Queens problem which required to place four queens on 4 x 4 chess board in such a way that no queen will be killed.

Fig: State Space for 4-Queen Problem Using Constructive Method

    The constructive method uses constraint graph to find a solution where each node in constraint graph is labeled with variable name and contains set of possible values for the variable. A directed arc (x, y) represents value of node x is constrained by value of node y.

A directed are (x, y) is said to be consistent if every value of the variable at the tail (arrow mark represents tall) of the arc has at least one value of the variable at head of the variable that does not violates the constraints.

Fig: A Constraint Graph for the Four_Queen Problem

    When. we assign values to one or more variables, come of the values from other variables are eliminated by arc consistency rule. The process iterates until no more values can be eliminated.

Initially,

    Q₁ ⟶   {1, 2, 3, 4}

    Q₂ ⟶   {1, 2, 3, 4}

    Q₃ ⟶  {1, 2, 3, 4}

    Q₄ ⟶   {1, 2, 3, 4}

Assign value 1 to Q, then by arc consistency rules, 

    Q₁ ⟶   {1}

    Q₂ ⟶  {3, 4}

    Q₃ ⟶   { 2, 4}

    Q₄ ⟶  {2, 3}

    Since arc (Q2, Q3) is consistent, we can eliminate 3 from Q2. Now Q2, has only one assign it. Then 4 from Q3, is eliminated because (O3, Q2) is consistent. Since arc (Q3, Q4) is consistent we can eliminate 2 from Q3. Because of Q3, have no values to be assigned, the process fails to find the solution at this iteration. The above process is represented using a constraint graph as shown below.

Fig: Constraint Graph with Q₁ = 1

    One of the solutions is obtained at Q₁ = 2 as shown below,

Fig: Constraint Graph with Q₂ =2