Learn · AI:Constraint Satisfaction

Lecture 21 of 42Week 5: Combining search and reasoning, Lookback methods and Gaschnig's backjumping

Search Methods for Solving CSPs

Prof. Deepak Khemani · IIT Madras

Credits and licence

From
AI:Constraint Satisfaction, IIT Madras (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

  1. Constraint Satisfaction Problems Video
  2. CSP Examples: Map colouring, N-Queens, Classroom scheduling Video
  3. CSP Examples: Huffman-Clowes Labelling, Waltz Algorithm, Crosswords Video
  4. Model Based Diagnosis - An application of CSP Video
  5. Constraint Networks - An Introduction Video
  6. Binary Constraint Networks (BCN), Equivalent Networks Video
  7. Projection Networks Video
  8. Constraint Propagation Video
  9. Algorithms AC1 and AC3 Video
  10. Can we do better than AC3? Video
  11. Algorithm AC4 Video
  12. Generalized AC, Path-Consistency Video
  13. i-Consistency, Algorithm PC1 Video
  14. Algorithm PC2, Strong i-Consistency Video
  15. Directional Consistency and Graph Ordering Video
  16. Min-Width and Min-Induced-Width Ordering Video
  17. Directional Arc-Consistency and Tree CSPs Video
  18. Directional Path-Consistency and Directional i-Consistency Video
  19. Backtrack-Free search and Adaptive Consistency Video
  20. Adaptive Consistency: Bucket Elimination Video
  21. Search Methods for Solving CSPs Video
  22. Algorithm Backtracking Video
  23. Look-Ahead Methods in Search Video
  24. Look-Ahead Search: Examples Video
  25. Combining Search with Reasoning: Algorithm DPLL Video
  26. Algorithm Backmarking Video
  27. Dynamic Value Ordering, Dynamic Variable Ordering Video
  28. Look-Back Methods - Definitions Video
  29. Gaschnig’s Backjumping: The Culprit Variable Video
  30. Gaschnig’s Backjumping, Graph-Based Backjumping Video
  31. Graph-Based Backjumping: Internal and Relevant Dead-Ends Video
  32. Conflict-Directed Backjumping: Definitions Video
  33. Algorithm Conflict-Directed Backjumping Video
  34. Combining Look-Ahead and Look-Back: FC-CBJ Video
  35. Learning During Search Video
  36. Model Based Systems Video
  37. Model Based Diagnosis Video
  38. Truth Maintenance Systems Video
  39. Planning as Constraint Satisfaction Video
  40. Planning as Constraint Satisfaction (cont.) Video
  41. Planning as Satisfiability Video
  42. Wrapping Up and Further Study Video