ALTERNATIVE SEARCH FORMULATIONS AND APPLICATIONS
Assignment Problems
Constraint Satisfaction Problem (CSP): Search can be made easier cases where the solution instead of corresponding, to an optimal path, is only required to satisfy local consistency condition. We call such problems Constraint satisfaction (CS) problems. For example, in across word puzzle it is only required that words that cross each other have the same letter in the location where they cross. It would be a general search problem if we require, say, that we use atmost 15 vowels.
C constraint satisfaction is a search procedure that operates on constraint Sets. The constraints that are given in the problem description will be taken as initial state and Goal state is that which has been constrained ‘satisfied’, where ‘satisfied’ is according to the problem.
In case of graph search problems which are imposed by specific conditions or constraints, it is difficult to find goal node by sequence of steps which leads to goal node, ‘An alternative solution involves assigning values to variables subject to constraints, These type of problems are known as assignment problems. Here goal node is defined by data structure that satisfies the constraints. Operators transform one data structure into another.
Example: Eight-Queens Problem.
In this problem, all eight queens are placed on a chess board in such a way that no queen will be killed by another queen i.e., only one queen can be in any single row, column or diagonal). This problem can be described as assignment problem because the variables q1, q2, ....... q8 are assigned with values from set {row1, row2, ...... row8}. Here q1, q2, ....... q8 represents position of queen in column 4, position of queen in column 2 and so on.
The data structure used to describe state of solution is 8 x 8 array where each cell contains either o (absence of queen) or 1 (presence of queen). The operators such as adding a queen to chess boarder move queen's position transforms state descriptions by changing one array to another.
Example: Crossword Puzzle
In crossword puzzle problem a 2D array of blank cells and blacked out cells is given.
We have to fill all blank cells with letters such that all rows and columns have English words based on hints provided to fill the blanks,
In this problem, any description is any array of letters (either all the blank cells filled or not). The goal state is an array with all the blank cells filled that satisfies the high (constraints) provided. An operators such as adding a word to row or column, or changing a letter transforms one problem state to another,
