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
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
