发帖
雷达卡
- CSPs are composed of variables with possible values that fall into ranges known as domains. Constraints between the variables must be satisfied in order for constraint-satisfaction problems to be solved. Those three core concepts - variables, domains, and constraints are simple to understand, and their generality underlies the wide applicability of constraint-satisfaction problem solving.
- example problem - Suppose you are trying to schedule a Friday meeting for Joe, Mary, and Sue. Sue has to be at the meeting with at least one other person. For this scheduling problem, the three people - Joe, Mary, and Sue - may be the variables. The domain for each variable may be their respective hours of availability. This problem also has two constraints:
- One is that Sue has to be at the meeting.
- The other is that at least two people must attend the meeting.
- A constraint-satisfaction problem solver will be provided with the three variables, three domains, and two constraints, and it will then solve the problem without having the user explain exactly how.
- The usual technique to solve CSP is to build a framework that incorporates a backtracking search and several heuristics to improve the performance of that search.
#1 - Building a constraint-satisfaction problem framework
Constraints will be defined using a Constraint class. Each Constraint consists of the variables it constrains and a method that checks whether it is satisfied() . The determination of whether a constraint is satisfied is the main logic that goes into defining a specific constraint-satisfaction problem. The default implementation should be overridden. In fact, it must be, because we are defining our Constraint class as an abstract base class. Abstract base classes are not meant to be instantiated. Instead, only their subclasses that override and implement their @abstractmethods are for actual use.
This constraint-satisfaction framework will use a simple backtracking search to find solutions to problems. Backtracking is the idea that once you hit a wall in your search, you go back to the last known point where you made a decision before the wall, and choose a different path. If you think that sounds like depth-first search, you are perceptive. The backtracking search implemented in the following backtracking_search() function is a kind of recursive depth-first search, combining ideas you saw in chapters 1 and 2. This function is added as a method to the CSP class.
Real-world applications
Constraint-satisfaction problem solvers are commonly used in scheduling. Several people need to be at a meeting, and they are the variables. The domains consist of the open times on their calendars. The constraints may involve what combinations of people are required at the meeting.
Constraint-satisfaction problem solvers are also used in motion planning. Imagine a robot arm that needs to fit inside of a tube. It has constraints (the walls of the tube), variables (the joints), and domains (possible movements of the joints).
There are also applications in computational biology. You can imagine constraints between molecules required for a chemical reaction. And, of course, as is common with AI, there are applications in games. Writing a Sudoku solver is one of the following exercises, but many logic puzzles can be solved using constraint-satisfaction problem solving.
In this chapter, we built a simple backtracking, depth-first search, problem-solving framework. But it can be greatly improved by adding heuristics (A*?) - intuitions that can aid the search process. A newer technique than backtracking, known as constraint propagation, is also an efficient avenue for real-world applications.
京公网安备 11010802022788号
