(12th-May-2020)
For optimization where the domains are continuous, a local search becomes more complicated because it is not obvious what the neighbors of a total assignment are. This problem does not arise with hard constraint satisfaction problems because the constraints implicitly discretize the space.
For optimization, gradient descent can be used to find a minimum value, and gradient ascent can be used to find a maximum value. Gradient descent is like walking downhill and always taking a step in the direction that goes down the most. The general idea is that the neighbor of a total assignment is to step downhill in proportion to the slope of the evaluation function h. Thus, gradient descent takes steps in each direction proportional to the negative of the partial derivative in that direction.
In one dimension, if X is a real-valued variable with the current value of v, the next value should be
v-η×(dh/dX)(v),
where
η, the step size, is the constant of proportionality that determines how fast gradient descent approaches the minimum. If η is too large, the algorithm can overshoot the minimum; if η is too small, progress becomes very slow.
(d h)/(d X), the derivative of h with respect to X, is a function of X and is evaluated for X=v.
The first is to represent the word positions (A1, A2, A3, D1, D2, and D3) as variables, with the set of words as possible values. The constraints are that the letter is the same where the words intersect.
The second is to represent the nine squares as variables. The domain of each variable is the set of letters of the alphabet, {a,b,...,z}. The constraints are that there is a word in the word list that contains the corresponding letters. For example, the top-left square and the center-top square cannot both have the value a, because there is no word starting with aa.
Give an example of pruning due to domain consistency using the first representation (if one exists).
Give an example of pruning due to arc consistency using the first representation (if one exists).
Are domain consistency plus arc consistency adequate to solve this problem using the first representation? Explain.
Give an example of pruning due to domain consistency using the second representation (if one exists).
Give an example of pruning due to arc consistency using the second representation (if one exists).
Are domain consistency plus arc consistency adequate to solve this problem using the second representation?
Which representation leads to a more efficient solution using consistency-based techniques? Give the evidence on which you are basing your answer.
Comentarios