week 3 Flashcards
chp 3
Introduction to Problem Solving by Searching
(definition)
- Definition: Problem-solving in AI
refers to the process of moving
from a given start state to a desired
goal state. - Multiple paths can lead to the goal.
- Not all paths are efficient or viable.
- Some problems might have no
solution.
Goal-Directed
Agent
A goal directed agent needs
to achieve certain goals.
* Many problems can be
represented as a set of
STATES and a set of rules of
how one state is
transformed to another.
* The agent must choose a
sequence of ACTIONS to
achieve the desired goal.
PROBLEM
FORMULATION
- State Space: “The environment in which the AI operates, containing all possible states the system can be in.”
- Goal Test: “Determine if a given state is a goal state. “
- Successor Function: “Provides the possible actions that can be taken from a given state.”
- Path Cost: “A measure of the effort needed to move from one state to another or to achieve a goal.”
TYPES OF SEARCH ALGORITHMS
1.Uninformed Search (Blind
Search): “Search strategies that use only the information available in the problem definition.”
2.Informed Search (Heuristic
Search): “Search strategies that employ additional knowledge about the problem domain to guide the search.
BREADTH FIRST SEARCH (BFS) (definition, characteristics)
- Definition: “Breadth-First Search (BFS) is a search strategy that
explores all nodes at the present depth before moving on to nodes at
the next depth level.” - Characteristics:
1. Complete: If a solution exists, BFS will find it.
2.Optimal: For problems with uniform costs, BFS guarantees the least-cost
solution.
3. Time Complexity: O(bd), where b is the branching factor and d is the depth.
4. Space Complexity: O(bd), as it needs to store all nodes at the current level to
generate their successors.
d: depth of the shallowest goal
node
m: maximum depth of the
search tree
the architecture of BFS
Draw the concept diagram
BFS ALGORITHM
The steps of the
algorithm work as
follow:
Start by putting any one
of the graph’s vertices at
the back of the queue.
Now take the front item
of the queue and add it
to the visited list.
Create a list of that
vertex’s adjacent nodes.
Add those which are not
within the visited list to
the rear of the queue.
Keep continuing steps
two and three till the
queue is empty.
Task 1
1.What is the order of visiting nodes using BFS if G is not the goal?
2.What happen if G is the goal?
3.Amend the code by specifying the goal node is G.
- Order of Visiting Nodes Using BFS (if G is not the goal)
Breadth-First Search (BFS) explores all neighbors of a node before moving to the next level. Starting from node A:
Step-by-Step BFS traversal:
Start at A (root node).
Visit neighbors B, C, and D.
Then visit the next level: E, F, and finally G (if G is not the goal).
Order of visiting nodes (if G is not the goal):
A → B → C → D → E → F → G
- What Happens if G is the Goal?
If G is the goal:
BFS stops as soon as it encounters the goal node.
Step-by-Step with G as goal:
Start at A → Visit B, C, D → Finally, G is reached.
Order of visiting nodes (if G is the goal):
A → B → C → D → G
- Amend the Code to Specify Goal Node G
Below is an example Python code for BFS that stops when the goal node G is found:
python
Copy code
from collections import deque
def bfs(graph, start, goal):
visited = set() # Track visited nodes
queue = deque([start]) # Initialize queue with start node
while queue:
node = queue.popleft() # Dequeue a node
if node not in visited:
visited.add(node)
print(f"Visited: {node}") # Print the node being visited
# Check if the goal node is reached
if node == goal:
print(f"Goal node {goal} found!")
return
# Enqueue all unvisited neighbors
queue.extend(graph[node])
print("Goal node not found in the graph.")
Example graph as adjacency list
graph = {
‘A’: [‘B’, ‘C’, ‘D’],
‘B’: [‘E’],
‘C’: [],
‘D’: [‘F’, ‘G’],
‘E’: [],
‘F’: [‘H’],
‘G’: [],
‘H’: []
}
Start BFS with goal node G
bfs(graph, start=’A’, goal=’G’)
Explanation of the Code:
Graph Representation: The graph is represented as an adjacency list.
Queue Initialization: BFS starts with node A.
Goal Check: As BFS explores each node, it checks if it matches the goal (G). If found, the function exits early.
Output: The function prints the traversal order and stops at the goal node if specified.
RULES OF BFS ALGORITHM
A queue (FIFO-First in First Out) data structure is used by BFS.
You mark any node in the graph as root and start traversing the data from it.
BFS traverses all the nodes in the graph and keeps dropping them as completed.
BFS visits an adjacent unvisited node, marks it as done, and inserts it into a queue.
Removes the previous vertex from the queue in case no adjacent vertex is found.
BFS algorithm iterates until all the vertices in the graph are successfully traversed and marked as completed.
There are no loops caused by BFS during the traversing of data from any node.
DEPTH FIRST SEARCH (DFS)
Concept: Recursive algorithm using backtracking.
Maze Analogy: Like solving a maze by choosing a route and following it until a dead end.
On Dead End: Retrace steps to the last untried path.
Backtracking: If no forward move is possible, move backward.
Traversal: Thoroughly explores all nodes along the current path before switching to the next path.
Objective: Visit every node once.
Key Idea: Dive as deep as possible, then backtrack.
DFS Algorithm
We will start by putting any one of the graph’s vertex on top of the stack. => After that take the top item of the stack and add it to the visted list of the vertex. =>Next, create a list of that adjacent node of the vertex. And the ones which aren’t in the visited list of vertexes to the top of the stack. =>Lastly, keep repeating steps 2 and 3 until stack is empty.
Task 2
What is the order of visiting nodes using DFS if G is NOT the goal?
What happen if G is the goal? Justify your answer by modifying the code.
Order of Visiting Nodes Using DFS (if G is NOT the goal)
In DFS, the algorithm explores as far as possible along each branch before backtracking. Starting from A:
Step-by-Step DFS Traversal:
Start at A.
Move to the first neighbor: B → Explore B’s neighbor: E.
Backtrack to A → Move to the next neighbor: C (no further neighbors).
Backtrack to A → Move to the next neighbor: D → Explore D’s neighbor: F → Then G → Finally H.
Order of visiting nodes (if G is NOT the goal):
A → B → E → C → D → F → G → H
- What Happens if G is the Goal?
If G is the goal:
DFS stops as soon as it encounters G.
Step-by-Step with G as goal:
Start at A → Visit B → Visit E → Backtrack to A → Visit C → Visit D → Finally reach G.
Order of visiting nodes (if G is the goal):
A → B → E → C → D → G
- Modified Code for DFS
Here’s an example Python code for DFS, which checks for the goal node G:
python
Copy code
def dfs(graph, start, goal, visited=None):
if visited is None:
visited = set()
# Mark the current node as visited
visited.add(start)
print(f"Visited: {start}") # Print the node being visited
# Check if the goal node is found
if start == goal:
print(f"Goal node {goal} found!")
return True
# Explore all unvisited neighbors
for neighbor in graph[start]:
if neighbor not in visited:
if dfs(graph, neighbor, goal, visited): # Stop if goal is found
return True
return False
Example graph as adjacency list
graph = {
‘A’: [‘B’, ‘C’, ‘D’],
‘B’: [‘E’],
‘C’: [],
‘D’: [‘F’, ‘G’],
‘E’: [],
‘F’: [‘H’],
‘G’: [],
‘H’: []
}
Start DFS with goal node G
print(“DFS Traversal when G is NOT the goal:”)
dfs(graph, start=’A’, goal=None)
print(“\nDFS Traversal when G is the goal:”)
dfs(graph, start=’A’, goal=’G’)
Explanation of the Code:
Graph Representation: The graph is represented as an adjacency list.
Recursive DFS Function: The function traverses nodes recursively and checks for the goal node.
Goal Check: If the goal node G is found, the function exits early.
Output:
If G is not the goal, it traverses all nodes.
If G is the goal, the traversal stops as soon as G is found.
Applications of DFS
Depth-First Search Algorithm has a wide range of applications for practical purposes. Some of them are as discussed below:
For finding the strongly connected components of the graph
For finding the path
To test if the graph is bipartite
For detecting cycles in a graph
Topological Sorting
Solving the puzzle with only one solution.
Network Analysis
Mapping Routes
Scheduling a problem
Task 3
Write the Python code for Depth Limited Search with predetermined depth limit, n=2.
What is the order or node visited using this algorithm?
def depth_limited_search(graph, start, limit, depth=0, visited=None):
if visited is None:
visited = set()
# Mark the current node as visited
visited.add(start)
print(f"Visited: {start}") # Print the current node being visited
# Stop recursion if the depth limit is reached
if depth == limit:
return visited
# Explore neighbors if depth limit is not yet reached
for neighbor in graph.get(start, []):
if neighbor not in visited:
depth_limited_search(graph, neighbor, limit, depth + 1, visited)
return visited
Example graph as adjacency list
graph = {
‘A’: [‘B’, ‘C’],
‘B’: [‘D’, ‘E’],
‘C’: [‘D’, ‘G’],
‘D’: [‘C’, ‘F’],
‘E’: [],
‘F’: [‘G’, ‘H’],
‘G’: [],
‘H’: []
}
Start DLS with depth limit of 2
print(“Depth-Limited Search with depth limit n=2:”)
depth_limited_search(graph, start=’A’, limit=2)
Order of Nodes Visited
Step-by-Step Execution with Depth Limit n=2:
Start at Node A (depth = 0):
Visited: A
Visit Node B (depth = 1):
Visited: B
Visit Node D (depth = 2):
Stop further exploration beyond this node since depth = 2.
Visit Node E (depth = 2):
Stop further exploration beyond this node.
Backtrack and Visit Node C (depth = 1):
Visited: C
Visit Node D (depth = 2):
Stop further exploration beyond this node.
Visit Node G (depth = 2):
Stop further exploration beyond this node.
Final Order of Nodes Visited:
A → B → D → E → C → D → G
This is the order of nodes visited using Depth-Limited Search with a limit of n=2.
Task 4
Write a code using Iterative Deepening Search and find the optimal G. State the iterative depth until it stops at the goal node, G.
class Node:
def __init__(self, name, children=None):
self.name = name
self.children = children or []
def iterative_deepening_search(root, goal):
def dls(node, depth):
if depth == 0 and node.name == goal:
return node
if depth > 0:
for child in node.children:
result = dls(child, depth - 1)
if result:
return result
return None
depth = 0
while True:
result = dls(root, depth)
if result:
return result, depth
depth += 1
Constructing the tree based on the provided image
root = Node(“A”, [
Node(“B”, [
Node(“D”, [Node(“C”), Node(“G”)]),
Node(“F”, [Node(“H”)]),
]),
Node(“C”, [
Node(“D”, [Node(“B”), Node(“E”)]),
Node(“F”, [Node(“G”), Node(“H”)]),
]),
])
Running the IDS algorithm to find “G”
goal_node, depth_found = iterative_deepening_search(root, “G”)
print(f”Found goal node: {goal_node.name} at depth: {depth_found}”)
Explanation:
Node Class: A tree node is represented with a name and a list of its children.
Iterative Deepening Search (IDS):
The dls function performs a depth-limited search.
The iterative_deepening_search function iteratively increases the depth until the goal node is found.
Tree Construction: The tree is created according to the structure in the provided image.
Search: The algorithm searches for the node named “G” and prints the result.
