Understanding Constraint Satisfaction Problems in Search Algorithms
Explore the world of Constraint Satisfaction Problems (CSPs) in search algorithms, where the goal is implicit. Learn about solving Recall Search and Cryptarithmetic examples through heuristic-guided paths. Understand why traditional search strategies like A* or greedy are not suitable for CSPs and discover the relevance of DFS in tackling such problems efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Constraint Satisfaction Review Search with Implicit Goals
Recall Search problems: Find the sequence of actions that leads to the goal. Sequence of actions means a path in the search space. Paths come with different costs and depths. We use heuristics to guide the search efficiently. Constraint satisfaction problems: A search problem too! We care about the goal itself.
Cryptarithmetic Example Map numbers to letters to satisfy an arithmetic example: TWO + TWO ---------- FOUR Variables: the letters (T, W, O, F, U, R) and carries (X10,X100,X1000) Domains: integers (0-9) for the letters, (0,1) for the carries Constraints: The letters (T, W, O, F, U, R) have to take on different values Operations on variable values have to make arithmetic sense: e.g., O + O = R + 10*X10
CSP as Search We can set up state space representation as variables over domains, initial state as no variable assignments, and goal-test as constraints Which general search strategy should we use?
Why not A* or greedy? Since goal is not explicit, it may be really hard to estimate remaining path to goal (or trivially easy but not useful: e.g., in the N-queens problem, if we ve taken i steps, all next states have at least N-i more steps to go).
Why not Uniform Cost? No edge cost
Why not BFS? Exponential space requirement for no gain (since we know ahead of time that the solution will not be found until all the variables have been assigned, goal state cannot be found earlier than that)
Why not ID-DFS? Since we know ahead of time that the solution will not be found until all the variables have been assigned, goal state cannot be found earlier than that, so no point in redoing the goal-test early on.
Why DFS? For this type of problem, DFS is essentially running as DFS-limited, with the depth limit set for the number of variables. So we won t have to worry about DFS running into infinite loops or returning a suboptimal solution.
Why not generic DFS? Generic search doesn t realize that the order in which we pick variables to assign doesn t matter Generic search s goal-test doesn t realize that a particular search path is doomed to fail if a constraint is violated early on. Does it matter which variable we consider when? Does it matter what order we try the values? Aside from obvious assignment conflicts, are there other ways of detecting inevitable failures early?
Solving CSPs CSP Algorithms: Search: choose a new variable assignment from many possibilities Inference: constraint propagation, use the constraints to spread the word: reduce the number of values for a variable which will reduce the legal values of other variables etc. As a preprocessing step, constraint propagation can sometimes solve the problem entirely without search. Constraint propagation can be intertwined with search
Solving CSPs Backtracking search is the basic uninformed search for CSPs. It s a DFS such that Assign one variable at a time: assignments are commutative. (WA=red, NT=green) is same as (NT=green,WA=red) Check constraints on the go: consider values that do not conflict with previous assignments. Variable ordering and value selection heuristics help Forward checking prevents assignments that guarantee later failure The power of CSPs: domain-independent, that is you only need to define the problem and then use a solver that implements CSPs mechanisms.
CSP: Representation Example Pitt's Cucina serves dinner Wednesday through Sunday. The restaurant is closed on Monday and Tuesday. Five entrees (veal parmesan, grilled swordfish, pan seared salmon, pork loin, chicken parmesan) are served as the special each week according to the following restrictions: Something must be served every day Grilled swordfish is never served on Friday. Pork loin cannot be served the day after veal parmesan Pan seared salmon and veal parmesan must be served on the weekend. Chicken parmesan is always served within two days of grilled swordfish. Specify the problem of determining which meals can be served on which day as a CSP.
