Intelligent Systems (XB_0031)
All Lectures + Working Groups Summary
,Lecture 1/2 - UNINFORMED SEARCH
1. Sets, Graphs and Trees
• n-tuples are sequences of lengths n
• ORDER makes a difference
o (a) is a singlet
o (a, b) is a pair
o (a, b, c) is a triple
▪ Likes = {(john, mary), (john, food),…}
Graph = A generalization of the simple concept of a set of dots, links, edges or arcs
V = set of vertices = set of notes
E = set of edges = the relations between nodes
A graph is a pair G = (V, E), where V is a set whose elements are called vertices (singular: vertex), and E is a
set of paired vertices, whose elements are called edges (sometimes links or lines)
An Eulerian path (Eulerian trail, Euler walk) in a graph is a path that uses each edge precisely once. If such
a path exists, the graph is called traversable.
Euler's Theorem: If a graph has exactly two vertices of odd degree, then the graph is semi-Eulerian.
A tree is a connected undirected graph with no simple circuits.
Rooted tree = Once a vertex of a tree has been designated as the root of the tree, it is possible to
assign direction to each of the edges.
Not a rooted tree -> Rooted Tree ->
A rooted tree is called an n-ary tree if every internal vertex has no more than n children. The tree is called a
full n-ary tree if every internal vertex has exactly n children. An n-ary tree with n=2 is called a binary tree.
The level or depth of a vertex v in a rooted tree is the length of the unique path from the root to this
vertex. Depth of 3 ->
2. State Space Representations
PROBLEM SOLVING AGENTS STATE SPACE SEARCH
State-Space representation = Abstract problem representation, graphs are used to represent
5 (5) -> 3 -> 3 (3) & 2 (5) -> 2(5) -> 2(3) -> 2(3) , 5 (5) -> 4 (5)
What are the transitions?
3. Problem Solving as Search
Basic search algorithms
A state is a (representation of) a physical configuration
A node is a data structure belong to a search tree
,4. Search Strategies
Fringe = data structure
Uninformed search strategies
• Breadth-first search (BF search)
o Checks for a solution, level by level
o Expand shallowest unexpanded node
o Implementation: fringe is a FIFO (first in first out) queue
• Uniform-cost search
o
• Depth-first search
o Check the first child all the way down, and then work back up to the right, then down, etc.
o Expand deepest unexpanded node
o Implementation: fringe is a LIFO (Last In First Out) queue (=stack)
• Depth-limited search
o
• Iterative deepening search.
o
• Bidirectional search
o
, A strategy defines picking order of node expansion.
• Performance is measured in four ways:
o Completeness; - Does it always find a solution if one exists?
o Optimality; - Does it always find the least-cost solution?
o Time Complexity; - Number of nodes generated/expanded?
o Space Complexity; - Number of nodes stored in memory during search?
All Lectures + Working Groups Summary
,Lecture 1/2 - UNINFORMED SEARCH
1. Sets, Graphs and Trees
• n-tuples are sequences of lengths n
• ORDER makes a difference
o (a) is a singlet
o (a, b) is a pair
o (a, b, c) is a triple
▪ Likes = {(john, mary), (john, food),…}
Graph = A generalization of the simple concept of a set of dots, links, edges or arcs
V = set of vertices = set of notes
E = set of edges = the relations between nodes
A graph is a pair G = (V, E), where V is a set whose elements are called vertices (singular: vertex), and E is a
set of paired vertices, whose elements are called edges (sometimes links or lines)
An Eulerian path (Eulerian trail, Euler walk) in a graph is a path that uses each edge precisely once. If such
a path exists, the graph is called traversable.
Euler's Theorem: If a graph has exactly two vertices of odd degree, then the graph is semi-Eulerian.
A tree is a connected undirected graph with no simple circuits.
Rooted tree = Once a vertex of a tree has been designated as the root of the tree, it is possible to
assign direction to each of the edges.
Not a rooted tree -> Rooted Tree ->
A rooted tree is called an n-ary tree if every internal vertex has no more than n children. The tree is called a
full n-ary tree if every internal vertex has exactly n children. An n-ary tree with n=2 is called a binary tree.
The level or depth of a vertex v in a rooted tree is the length of the unique path from the root to this
vertex. Depth of 3 ->
2. State Space Representations
PROBLEM SOLVING AGENTS STATE SPACE SEARCH
State-Space representation = Abstract problem representation, graphs are used to represent
5 (5) -> 3 -> 3 (3) & 2 (5) -> 2(5) -> 2(3) -> 2(3) , 5 (5) -> 4 (5)
What are the transitions?
3. Problem Solving as Search
Basic search algorithms
A state is a (representation of) a physical configuration
A node is a data structure belong to a search tree
,4. Search Strategies
Fringe = data structure
Uninformed search strategies
• Breadth-first search (BF search)
o Checks for a solution, level by level
o Expand shallowest unexpanded node
o Implementation: fringe is a FIFO (first in first out) queue
• Uniform-cost search
o
• Depth-first search
o Check the first child all the way down, and then work back up to the right, then down, etc.
o Expand deepest unexpanded node
o Implementation: fringe is a LIFO (Last In First Out) queue (=stack)
• Depth-limited search
o
• Iterative deepening search.
o
• Bidirectional search
o
, A strategy defines picking order of node expansion.
• Performance is measured in four ways:
o Completeness; - Does it always find a solution if one exists?
o Optimality; - Does it always find the least-cost solution?
o Time Complexity; - Number of nodes generated/expanded?
o Space Complexity; - Number of nodes stored in memory during search?
