(13th-May-2020)
Instead of reasoning explicitly in terms of states, it is almost always much more efficient for an agent solving realistic problems to reason in terms of a set of features that characterize a state.
Many problems can be represented as a set of variables, corresponding to the set of features, domains of possible values for the variables, and a set of hard and/or soft constraints. A solution is an assignment of a value to each variable that satisfies a set of hard constraints or optimizes some function.
Arc consistency and search can often be combined to find assignments that satisfy some constraints or to show that there is no assignment.
Stochastic local search can be used to find satisfying assignments, but not to show there are no satisfying assignments. The efficiency depends on the trade-off between the time taken for each improvement and how much the value is improved at each step. Some method must be used to allow the search to escape local minima that are not solutions.
Optimization can use systematic methods when the constraint graph is sparse. Local search can also be used, but the added problem exists of not knowing when the search is at a global optimum.
Consider following question together.
What kind of application needs the Randomized Algorithms for search?
Constraint satisfaction problems on finite domains are typically solved using a form of search. Which recursive algorithm is used for search? Explain by the case.
Comments