CMPUT 366 F20: Uninformed Search
James Wright & Vadim Bulitko
September 10, 2020
CMPUT 366 F20: Uninformed Search
1
Lecture Outline
Tutorial next Monday
In-lecture questions
Uninformed search
PM 3.5
CMPUT 366 F20: Uninformed Search 2
Summary of The Last Lecture
Many AI tasks can be represented as search problems
A single generic graph search algorithm can then solve them
with lots of fine print
A search problem consists of states, actions, start states, a successor function, a goal function
Optimizing solution quality can be addressed by labelling arcs of the search graph with costs
In the following lectures we will explore efficient search algorithms
CMPUT 366 F20: Uninformed Search 3
Search Graph for Tic-Tac-Toe
Build a search graph for the problem on the right
Nodes are the states
Neighbours are the successors of a state
add one arc from state n to each of n¡¯s successors
label each arc with the action that leads to the successor state
https://en.wikipedia.org/ wiki/Tic- tac- toe
CMPUT 366 F20: Uninformed Search
4
Generic Graph Search Algorithm
Given a graph, start nodes, and goal, incrementally explore paths from the start nodes
Maintain a frontier of paths that have been explored
As search proceeds, the frontier expands into the unexplored nodes until a goal is encountered
The way the frontier is expanded defines the search strategy
CMPUT 366 F20: Uninformed Search 5
Generic Graph Search Algorithm
CMPUT 366 F20: Uninformed Search 6
Algorithm Properties
Completeness Optimality
Time complexity
best, worst, average cases Memory complexity
best, worst, average cases
Asymptotic performance Worst case
CMPUT 366 F20: Uninformed Search 7
Search Graph Properties
Branching factor Maximum path depth Cycles?
Solution depth
Edge costs
https://www.growingwiththeweb.com/2012/06/a- pathfinding- algorithm.html
CMPUT 366 F20: Uninformed Search
8
Depth-First Search (DFS)
CMPUT 366 F20: Uninformed Search 9
Depth-First Search (DFS)
CMPUT 366 F20: Uninformed Search 10
Depth-First Search (DFS)
https://artint.info/2e/html/ArtInt2e.html
CMPUT 366 F20: Uninformed Search
11
Depth-First Search Properties
Low memory complexity
An effective neighbour order can be (sometimes) found
Stuck following deep/infinite paths Can miss shallow solutions Redundant work with transpositions
https://artint.info/2e/html/ArtInt2e.html
CMPUT 366 F20: Uninformed Search
12
Breadth-First Search (BFS)
CMPUT 366 F20: Uninformed Search 13
Breadth-First Search (BFS)
CMPUT 366 F20: Uninformed Search 14
Breadth-First Search (BFS)
https://artint.info/2e/html/ArtInt2e.html
CMPUT 366 F20: Uninformed Search
15
Breadth-First Search Properties
No problem with deep/infinite paths
Finds a solution with the smallest number of edges
High/prohibitive memory complexity
https://artint.info/2e/html/ArtInt2e.html
CMPUT 366 F20: Uninformed Search
16
DFS versus BFS
Search problem Preferred: BFS or DFS ?
Grid pathfinding Rubik¡¯s cube
https://www.growingwiththeweb.com/2012/06/ a- pathfinding- algorithm.html
https://en.wikipedia.org/wiki/Rubik¡¯ s_Cube
CMPUT 366 F20: Uninformed Search
17
More on DFS versus BFS
On tree search graphs with a constant branching factor b and a solution depth m:
Attribute
Completeness Number-of-edges optimality Worst-case space complexity Worst-case time complexity
DFS BFS
yes
yes
O(bm) O(bm)
for finite graphs
no
O(mb)
O(bm )
Can we get the space benefits of depth-first search without giving up completeness?
Run depth-first search to a chosen maximum depth then try again with a larger maximum
repeat until either goal found or graph exhausted
CMPUT 366 F20: Uninformed Search 18
Iterative Deepening Search
CMPUT 366 F20: Uninformed Search 19
Iterative Deepening Search Properties
No problem with deep/infinite paths
Finds a solution with the smallest number of edges
Redundant work
asymptotically optimal in exponential search spaces
Attribute
Completeness Optimality Space Time
DFS
BFS
IDS
yes
yes
O(mb) O(bm )
for finite graphs
yes
no
yes
O(mb)
O(bm )
O(bm )
O(bm )
https://artint.info/2e/html/ArtInt2e.html
CMPUT 366 F20: Uninformed Search
20
Types of Optimality
Attribute
Completeness Number-of-edges Optimality Space complexity Time complexity
DFS
BFS
IDS
yes
yes
O(mb) O(bm)
for finite graphs
yes
no
yes
O(mb)
O(bm )
O(bm )
O(bm )
Are any of these cost optimal?
CMPUT 366 F20: Uninformed Search
21
Least-cost First Search (LCFS)
None of the algorithms described so far is guided by edge costs BFS and IDS are number-of-edges optimal
the same as cost optimal only when edges have uniform costs
They return a path to a goal node when they happen to come across one, but it may not be the optimal one
Least Cost First Search is a search strategy that is guided by arc costs BFS but instead of shortest-first use lowest-cost first
CMPUT 366 F20: Uninformed Search 22
Least-cost First Search (LCFS)
CMPUT 366 F20: Uninformed Search 23
LCFS Properties
Attribute DFS
Completeness Edges optimality Cost optimality Space Time
BFS IDS
LCFS
yes with cost(v, v2) > ¦Å > ¨ no
yes
O(bm )
O(bm )
for finite graphs
yes
yes
no
yes
yes
no
no
no
O(mb)
O(bm )
O(mb)
O(bm )
O(bm )
O(bm )
CMPUT 366 F20: Uninformed Search
24
Recap
Different search strategies have different properties and behaviour costs DFS: space efficient, incomplete, suboptimal
BFS: space inefficient, complete, number-of-edges optimal IDS: space efficient, complete, optimal, less time efficient
LCFS is essentially BFS search with a cost-optimality guarantee
Can we do better than any of these?
CMPUT 366 F20: Uninformed Search 25