Algorithms, Pseudocode, or Code
Ch 5:
1-BackTracking Pseudocode(slide 13) :
function Backtracking-Search(csp):
return Recursive-Backtrack({}, csp)
function Recursive-Backtrack(assignment, csp):
if all variables are assigned:
return assignment
var = select an unassigned variable
for each value in the variable's domain:
if value is consistent with the assignment:
assign value to var
result = Recursive-Backtrack(assignment, csp)
if result is not failure:
return result
undo the assignment (backtrack)
return failure
2- Arc consistency:
function AC3(constraints):
queue = all arcs (A, B) in the problem # Start with all pairs (A, B) that
have constraints
while queue is not empty:
(A, B) = queue.remove() # Take one arc (A, B) from the queue
if remove_inconsistent_values(A, B): # If A's domain is reduced
for each neighbor C of A (except B): # Check all variables related to A
queue.add((C, A)) # Add these arcs back to the queue
return "Domains reduced and consistent"
function remove_inconsistent_values(A, B):
removed = false
for each value in domain[A]: # Loop through A's possible values
if no value in domain[B] satisfies the constraint (A, B): # If A's value is
invalid
domain[A].remove(value) # Remove it from A's domain
removed = true
return removed # Return whether we removed anything
Ch 7:
1- Simple KB agent:
function KB-Agent(percept) returns an action
static: KB, a knowledge base # A database storing knowledge about the
world
t, a counter, initially 0 # Keeps track of time steps
Tell(KB, Make-Percept-Sentence(percept, t)) # Add the percept to the
KB
action ← Ask(KB, Make-Action-Query(t)) # Query KB for the best
action
Tell(KB, Make-Action-Sentence(action, t)) # Add the chosen action to
the KB
t ← t + 1 # Increment the time step
return action # Return the action to be performed
What Does the Agent Do?
The agent is a loop of sensing, thinking, and acting:
1. Sense: Perceives something from the environment (e.g., light, sound).
2. Think: Updates its knowledge base with the new information and
queries it for the best action.
3. Act: Executes the chosen action and records it for future reasoning.
Example
Scenario:
● Agent’s Job: Turn on the light if it’s dark.
● Percept: "It’s dark."
● Knowledge Base: Contains:
○ Rule: "If it’s dark, turn on the light."
Steps:
1. Perceive:
○ The agent receives the percept "It’s dark."
○ Tell(KB, "It’s dark at time t").
2. Reason:
○ The agent queries the KB: "What action should I take at time ttt?"
○ KB applies the rule and answers: "Turn on the light."
3. Act:
○ The agent records: "I turned on the light at time ttt."
○ Then performs the action: Turn on the light.
4. Repeat:
○ Next percept, next reasoning, next action.
2-Inference By Enumeration (slide 38):
function TT-Entails(KB, α):
symbols = all symbols in KB and α
return Check-All(KB, α, symbols, {})
function Check-All(KB, α, symbols, model):
if symbols is empty:
if KB is true in the model:
return α is true in the model
else:
return true
else:
P = first symbol in symbols
rest = remaining symbols
return Check-All(KB, α, rest, model + {P: true}) and
Check-All(KB, α, rest, model + {P: false})
Explanation
1. TT-Entails Function
● This is the main function. It checks if KB⊨αKB \models αKB⊨α (if the
knowledge base entails the query).
● Input:
1. KB: The knowledge base.
2. α: The query (proposition to check if it follows from the KB).
● Steps:
1. Extract all the symbols (propositions) from KB and α
2. Call the recursive function Check-All to evaluate all possible
models (truth assignments).
2. Check-All Function
● This function performs recursive enumeration of all possible truth
assignments (models).
● Parameters:
○ KB: The knowledge base.
○ α: The query.
○ symbols: The list of remaining symbols to assign truth values to.
○ model: The current truth assignment (e.g., {P: true, Q: false}).
Steps in Check-All
1. Base Case (symbols is empty):
○ If there are no more symbols to assign:
■ Check if KB is true in the current model:
■ If KB is false, skip this model (return true because we
only care about models where KB is true).
■ If KB is true, check if α is also true:
■ If α is false, return false (this model disproves
KB⊨α).
○ If all models where KB is true also make α true, return true.
2. Recursive Case:
○ Pick the first symbol (P) from symbols.
○ Assign P=true and recursively evaluate the rest of the symbols.
○ Assign P=false and recursively assess the rest of the symbols.
○ Combine results using and: both branches must confirm KB⊨α.
3- Forward Chaining algorithm:
function Forward-Chaining(KB, q):
agenda = facts from KB
inferred = {} # Track which facts have already been processed
count = {rule: number of premises in rule for each rule in KB} # Count
remaining premises for each rule
while agenda: # Keep processing as long as there are facts to check
p = Pop(agenda) # Get the next fact from the agenda
if not inferred.get(p, False): # If the fact has not been processed yet
inferred[p] = True # Mark the fact as processed
for rule in KB where p is a premise: # Check all rules where this fact is a
premise
count[rule] -= 1 # Reduce the number of unsatisfied premises for the rule
if count[rule] == 0: # If all premises for the rule are satisfied
conclusion = result of the rule # Get the conclusion of the rule
if conclusion == q: # If the conclusion matches the query
return True # The query is proven
agenda.append(conclusion) # Add the conclusion to the agenda for
further processing
return False # If no proof is found, return False
Example:
Knowledge Base (KB):
1. A∧B→C: "If A and B are true, then C is true."
2. C→D: "If C is true, then D is true."
3. A=true: "A is true."
4. B=true: "B is true."
Query (Q):
● Is D true?
Step-by-Step Execution
1. Initialization:
○ agenda = [A, B] (facts from KB).
○ inferred = {} (nothing processed yet).
○ count = { (A ∧ B → C): 2, (C → D): 1 }
(premises left to satisfy for each rule).
2. Process A:
○ p=A, remove A from agenda.
○ Mark A as processed: inferred = {A: true}.
○ Rule A ∧ B→C: Reduce count from 2 to 1.
3. Process B:
○ p=B, remove B from agenda.
○ Mark B as processed: inferred = {A: true, B:
true}.
○ Rule A∧B→C: Reduce count from 1 to 0 (all premises
satisfied).
○ Infer C: Add C to agenda.
4. Process C:
○ p=C, remove C from agenda.
○ Mark C as processed: inferred = {A: true, B: true,
C: true}.
○ Rule C→D Reduce count from 1 to 0 (all premises satisfied).
○ Infer D: Add D to agenda.
5. Process D:
○ p=D, remove D from agenda.
○ D=q: The query is proven true.
Final Result:
● The query (D) is true.
Key Steps Summary
1. Start with known facts (A, B).
2. Use rules to infer new facts (C, then D).
3. Stop when the query (q=D) is proven.
