Forward Chaining algorithm: Prolog Explanation: More Details on Horn Clause(Fig

Question

Forward Chaining algorithm:

Prolog Explanation:

More Details on Horn Clause(Fig 7.14 pseudocode):

function PL-FC-ENTAILS?(KB, q) returns true or false inputs: KB, the knowledge base, a set of propositional definite clauses g, the query, a proposition symbol count a table, where count [c] is the number of symbols in c's premise inferred a table, where inferred[s] is initially false for all symbols agenda a queue of symbols, initially symbols known to be true in KB while agenda is not empty do p POP( agenda) if p = q then return true if inferredlp]-false then inferred[p] true for each clause c in KB where p is in c.PREMISE do decrement count[c] if count[c] 0 then add c.CONCLUSION to agenda return false Figure 7.15 The forward-chaining algorithm for propositional logic. The agenda keeps track of symbols known to be true but not yet "processed." The count table keeps track of how many premises of each implication are as yet unknown. Whenever a new symbol p from the agenda is processed, the count is reduced by one for each implication in whose premise p appears (easily identified in constant time with appropriate indexing.) If a count reaches zero, all the premises of the implication are known, so its conclusion can be added to the agenda. Finally, we need to keep track of which symbols have been processed; a symbol that is already in the set of inferred symbols need not be added to the agenda again. This avoids redundant work and prevents loops caused by implications such as Q and Q P

Explanation / Answer

function SIMPLE-PROBLEM-SOLVING-AGENT(percept) returns an action persistent: seq, an action sequence, initially empty state, some description of the current world state goal, a goal, initially null problem, a problem formulation state UPDATE-STATE(state, percept) if seq is empty then goal FORMULATE-GOAL(state) problem FORMULATE-PROBLEM(state, goal) seq SEARCH(problem) if seq = failure then return a null action action FIRST(seq) seq REST(seq) return action

function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure node a node with STATE = problem.INITIAL-STATE, PATH-COST = 0 if problem.GOAL-TEST(node.STATE) then return SOLUTION(node) frontier a FIFO queue with node as the only element explored an empty set loop do if EMPTY?(frontier ) then return failure node POP(frontier ) /* chooses the shallowest node in frontier */ add node.STATE to explored for each action in problem.ACTIONS(node.STATE) do child CHILD-NODE(problem, node, action) if child.STATE is not in explored or frontier then if problem.GOAL-TEST(child.STATE) then return SOLUTION(child) frontier INSERT(child,frontier )

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.