人工智能的课件CH7_Logic Agents.ppt

Backward chaining example Backward chaining example Backward chaining example Backward chaining example Backward chaining example Backward chaining example Forward vs. backward chaining FC is data-driven, automatic, unconscious processing, e.g., object recognition, routine decisions May do lots of work that is irrelevant to the goal BC is goal-driven, appropriate for problem-solving, e.g., Where are my keys? How do I get into a PhD program? Complexity of BC can be much less than linear in size of KB Efficient propositional inference Two families of efficient algorithms for propositional inference: Based on backtracking search Based on hillclimbing search Complete backtracking search algorithms DPLL algorithm (Davis, Putnam, Logemann, Loveland) Incomplete local search algorithms WalkSAT algorithm The DPLL algorithm Determine if an input propositional logic sentence (in CNF) is satisfiable. A recursive depth-first enumeration of possible models. Improvements over truth table enumeration: Early termination A clause is true if any literal is true. A sentence is false if any clause is false. Pure symbol heuristic Pure symbol: always appears with the same sign in all clauses. e.g., In the three clauses (A ? ?B), (?B ? ?C), (C ? A), A and B are pure, C is impure. Make a pure symbol literal true. Unit clause heuristic Unit clause: only one literal in the clause The only literal in a unit clause must be true. The DPLL algorithm The WalkSAT algorithm Incomplete, local search algorithm Evaluation function: The min-conflict heuristic of minimizing the number of unsatisfied clauses Balance between greediness and randomness The WalkSAT algorithm Hard satisfiability problems Consider random 3-CNF sentences. e.g., (?D ? ?B ? C) ? (B ? ?A ? ?C) ? (?C ? ?B ? E) ? (E ? ?D ? B) ? (B ? E ? ?C) m = number of clauses n = number of symbols Hard problems seem to cluster near m/n = 4.3 (critical point) Hard satisfiability problems Hard satisfiability problem