In this file, I have summarized all the lectures of Intelligent Systems. I have added lecture notes and summarized important parts of the book. To make the summary more readable (were necessary), I have added illustrations from the slides.
Good luck with the exam!
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?
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller tigovangerven. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $14.97. You're not tied to anything after your purchase.
