[SOLVED] Excel data structure algorithm Microsoft PowerPoint ai2.pptx

$25

File Name: Excel_data_structure_algorithm_Microsoft_PowerPoint__ai2.pptx.zip
File Size: 574.62 KB

5/5 - (1 vote)

Microsoft PowerPoint ai2.pptx

COMP3308/COMP3608, Lecture 2
ARTIFICIAL INTELLIGENCE

Problem Solving and Search.
Uninformed Search: BFS, DFS, UCS and IDS

Informed Search: Greedy Best-First

Reference: Russell and Norvig, ch. 3

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 1

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 2

Reminders

Tutorials start this week
All tutorials are on Tuesday or Wednesday in the SIT labs; check

your timetable
All students must submit their homework in Canvas by 4pm on

Tuesday (no matter when your tutorial class is)
Tutorial solutions will be available on Canvas on Wednesday after

the last tutorial (at 5pm)
Lecture slides are posted on Saturday morning and will not contain

the answers to all questions and exercises that we do during the
lecture. The complete lecture slides with the answers will be available
on Monday after the lecture (at 1pm)

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 3

Outline
Problem-solving and search
Search strategies

Uninformed (blind)
Informed (heuristic)

Uninformed search strategies
Breadth-first
Uniform cost
Depth-first
Depth-limited
Iterative-deepening

Informed search strategies
Greedy best-first
A* next week

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 4

Problem Solving and Search

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 5

Solving Problems by Searching
Many tasks can be formulated as search problems
Task: to get from an initial problem state to a goal state

Driving: starting address -> destination address
Chess: initial board position -> checkmate position
Reasoning: set of facts and rules + query -> answer

Solution: a path from the initial state to the goal state
Operators

possible actions, possible moves in a game

Cost (quality) of operators
distance, time, money
strength of board position in games

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 6

Example: Romania
On holiday in Romania

currently in Arad
flight leaves tomorrow from Bucharest

Step 1. Formulate goal: be in Bucharest
Step 2. Formulate search problem:

states: various cities
operators: drive between cities, e.g. from Arad to Sibiu, from

Arad to Zerind
Step 3. Find solution (path):

a sequence of cities from Arad to Bucharest, e.g. Arad, Sibiu,
Fagaras, Bucharest

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 7

Romania Example Map

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 8

Romania

http://en.wikipedia.org/wiki/File:Location_Romania_EU_Europe.PNG

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 9

Search Problem Formulation
A search problem is defined by 4 items

1) Initial state, e.g. Arad
2) Goal state (1 or more)

Stated explicitly, e.g.Bucharest
Stated implicitly with a goal test, e.g.checkmate state

3) Operators = actions
A set of possible actions transforming 1 state to another , e.g. Arad-

>Zerind, Arad->Sibiu, etc.
4) Path cost function assigns a numeric value to each path

Reflects the performance measure
E.g. time, path length in km, number of operators executed

Solution a path from the initial to a goal state
Its quality is measured by the path cost
Optimal solution is the one with the lowest path cost

State space all states reachable from the initial state by operators

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 10

Choosing States and Actions Abstraction
Real problems are too complex, to solve them we need to abstract them,

i.e. to simplify them by removing the unnecessary details
E.g. we ignore the weather, travel companion, scenery; they are irrelevant

for the task of finding a path to Bucharest
The actions need to be suitably specified, e.g. turn the steering wheel to

the left by 5 degrees is not appropriate
=> the level of abstraction must be appropriate (valid and useful)

(Abstract) state = set of real states
(Abstract) action = complex combination of real actions
(Abstract) solution = a real path that is solution in the real world

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 11

Example Problem 1: The 8-puzzle

States?
Operators?
Goal state?
Path cost?

a sliding block puzzle

1 state = 1 board configuration of the tiles
Move blank left, right, up, down
Given
1 per move, i.e. path cost=length of path=number of steps

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 12

Example Problem 2: The 8-queens

Goal state?
Path cost?

States =? 1 state = 1 board configuration of the tiles
Operators =? Put 1 queen on the board or move 1 queen

Place 8 queens on a chessboard (88) so
that no queen attacks each other

Is this a solution?

8 queens on board, none attacked
0 (= only the goal state matters and not the number of

steps). Other options are also possible, e.g. 1 per move.

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 13

8-queens Different Types of Problem
Formulation

1. Incremental start with an empty board, add 1 queen at a time
2. Complete-state start with all 8 queens and move them around

Lets take a closer look at 2 possible incremental formulations!

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 14

8-queens Incremental Formulation 1

States? Any arrangement of 0 to 8 queens
Initial state? No queens on the board
Operators? Add a queen to any square
State space = 1.8 x 1014 states (= 64 x 63 x x 57)

Can you suggest a better formulation?
Prohibit placing a queen in any square that is already

attacked!

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 15

8-queens Incremental Formulation 2

States? Any arrangement of 0 to 8 queens, 1 in each column,
with no queen attacking another

Initial state? No queens on the board
Operators? Place a queen in the left-most empty column such

that it is not attacked by any other queen
State space:2057 states

For 100-queens:
formulation 1: 10400 states
formulation 2: 1052 states (huge improvement but problem still

not tractable)
The problem formulation is very important!

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 16

Searching for Solutions
How can we solve the 8-queens puzzle or the Romania example?

By searching the state space
We can generate a search tree starting from the initial state and

applying the operators
Or we can generate a search graph in a graph the same state

can be reached from multiple paths

Tree-Search algorithm Pseudo Code
Basic idea: offline exploration of the state space by generating

successors of the explored states (i.e. by expanding states)

1. Choose a node for expansion based on the search strategy
2. Check if it is a goal node

Yes-> return solution
No -> expand it by generating its children

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 17

start with the initial node
the initial node at the beginning

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 18

Expanded and Fringe Lists

We will keep two lists:
Expanded for nodes that have been expanded
Fringe for nodes that have been generated but not expanded yet.
We will keep the fringe ordered (implemented as a priority queue) and

always select for expansion the first node of the fringe
For the figure:

Expanded: Arad
Fringe: Sibiu, Timisoara, Zerind
All the other nodes have not been generated yet
Note the notation in the figure for the different types of nodes

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 19

Tree Search Example

Fringe: Arad
Expanded: none

Is Arad a goal node? No => expand it

Lets put the children of the expanded node at the end of the fringe

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 20

Tree Search Example (2)

Fringe: Sibiu, Timisoara, Zerind
Expanded: Arad

Is Sibiu a goal node?
No => expand it

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 21

Tree Search Example (3)

Fringe: Timisoara, Zerind, Arad, Fagaras, Oradea, Riminicu Vilcea
Expanded: Arad, Sibiu

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 22

Tree Search More Detailed Pseudo Code

// nodes in fringe ordered based on their priority according to the search strategy

//select node for expansion, then check if it is a goal

Is the first node in the fringe a goal node?
Yes =>stop and return solution
No => expand it:

Move it to the expanded list
Generate its children and put them in the

fringe in a order defined by the search strategy
(top of the fringe =most desirable child)

We will keep the fringe ordered

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 23

Nodes vs States
A node is different than a state
A node:

represents a state
is a data structure used in the search tree
includes parent, children, and other relevant information e.g.

depth and path cost g

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 24

Search Strategies
A search strategy defines which node from the fringe is most promising

and should be expanded next
We will keep the nodes in the fringe ordered based on the search

strategy and always expand the first one (i.e. the best one)
Evaluation criteria

Completeness is it guaranteed to find a solution if one exists?
Optimality is it guaranteed to find an optimal (least cost path) solution?
Time complexity how long does it take to find the solution?(measured as

number of generated nodes)
Space complexity What is the maximum number of nodes in memory?

Time and space complexity are measured in terms of:
b max branching factor of the search tree (we can assume that it is finite)
d depth of the optimal (least cost) solution
m maximum depth of the state space (can be finite or not finite, i.e. )

Two types of search methods: uniformed (blind) and informed (heuristic)

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 25

Uninformed (Blind) Search Strategies

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 26

Uninformed (Blind) Search Strategies
Uninformed strategies:

Do not use problem-specific heuristic knowledge
Generate children in a systematic way, e.g. level by level, from left

to right
Know if a child node is a goal or non-goal node
Do not know if one non-goal child is better (more promising) than

another one. Exception: UCS, but this is not based on heuristic
knowledge.

In contrast, informed (heuristic) use heuristic knowledge to
determine the most promising non-goal child

5 uninformed search strategies
Breadth first
Uniform-cost
Depth-first

Depth-limited
Iterative deepening

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 27

Breadth-First Search (BFS)
Expands the shallowest unexpanded node
Implementation: insert children at the end of the fringe

Fringe: A
Expanded: none

Goal node

Is the first node in the fringe a goal node?
Yes => stop and return solution
No => expand it:

Move it to the expanded list
Generate its children and put them in the

fringe in a order defined by the search strategy

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 28

Breadth-First Search (BFS)
Expands the shallowest unexpanded node
Implementation: insert children at the end of the fringe

Fringe: B, C
Expanded: A

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 29

Breadth-First Search (BFS)
Expands the shallowest unexpanded node
Implementation: insert children at the end of the fringe

Fringe: C, D, E
Expanded: A, B

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 30

Breadth-First Search (BFS)
Expands the shallowest unexpanded node
Implementation: insert children at the end of the fringe

Fringe: D, E, F, G
Expanded: A, B, C

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 31

Breadth-First Search (BFS)
Expands shallowest unexpanded node
Implementation: insert children at the end of the fringe

Fringe: E, F, G
Expanded: A, B, C, D

Fringe: F, G
Expanded: A, B, C, D, E

Fringe: G
Expanded: A, B, C, D, E, F
G is a goal node => stop

Order of expansion: ABCDEFG (the goal node is also included)
Goal node found: G
Solution path found: ACG(requires tracing back)

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 32

BFS for Romania Example
There will be loops (repeated states)
Needs a repeated state checking mechanism

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 33

Properties of BFS
Complete? Yes (if branching factor b is finite but we assume this)
Optimal?

Optimal solution = least cost path
It doesnt consider the step cost + we need to know the step costs
If all step costs are the same, e.g. =1, is BFS optimal? Yes
If the step costs are different, is BFS optimal? No

The shallowest goal node is not
necessarily the optimal one!

Suppose C and J
were goal nodes
and J is a better
solution than C;
BFS will find C
not optimal

6
2

1

1

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 34

Properties of BFS (2)
Complete? Yes
Optimal? Not optimal in general; Yes, if step cost is the same, e.g. =1
Time? generated nodes = 1+b+b2+b3+b4 + +bd = O(bd), exponential
Space? O(bd) (keeps every node in memory)
Both time and space are problems as they grow exponentially with

depth but space is the bigger problem!
Search problems
with exponential
complexity can
NOT be solved
by uninformed

search except for
small depth &

small branching
factor.

You may wait 13 days for the solution to an important problem but there is still no personal computer
with 1 petabyte of memory!

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 35

Romania with Step Coast in km

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 36

Uniform Cost Search (UCS)
We saw that:

BFS does not consider the step cost at all; it simply systematically
expands the nodes level by level, from left to right

BFS finds the shallowest goal node but this may not be always the
optimal solution (least cost solution = shortest path)

UCS considers the step cost. It expands the least-cost unexpanded
node the node n with the lowest path cost g(n) from the initial state

Implementation: insert nodes in the fringe in order of increasing path
cost from the root

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 37

UCS for the Romania Example (1)

Arad

fringe

Fringe: Arad
Expanded: none

Is Arad a goal state? No
-Move it to Expanded
-Generate its children and

put them in Fringe in
order

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 38

UCS for the Romania Example

Arad

Zerind Sibiu Timisoara

75
140

118

fringe

The fringe is ordered based on the path cost from the root

Fringe: (Zerind,75), (Timisoara, 118), (Sibiu, 140)
Expanded: Arad

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 39

UCS for the Romania Example

Arad

Zerind Sibiu Timisoara

75
140

118

Arad Oradea

75 71

fringe

Fringe: (Timisoara, 118), (Sibiu, 140), (Oradea,146), (Arad, 150)
Expanded: Arad, (Zerind, 75)

The fringe is ordered based on the path cost from the root

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 40

UCS for the Romania Example

Arad

Zerind Sibiu Timisoara

75
140

118

Arad Oradea

75 71

Arad Lugoj

110
111

fringe

Fringe: (Sibiu, 140), (Oradea,146), (Arad, 150), (Arad,228), (Lugoj, 229)
Expanded: Arad, (Zerind, 75), (Timisoara, 118)

The fringe is ordered based on the path cost from the root

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 41

UCS for the Romania Example

Arad

Zerind Sibiu Timisoara

75
140

118

Arad Oradea

75 71

Arad Lugoj

110
111

fringe

Fringe: (Oradea,146), (Arad, 150), (Riminicu Vilcea, 220),
(Arad,228), (Lugoj, 229), (Fagaras, 239), (Oradea , 291)
Expanded: Arad, (Zerind, 75), (Timisoara, 118), (Sibiu, 140)

etc. not finished

99

Arad Oradea Fagaras
Rimnicu
Vilcea

151 80

The fringe is ordered based on the path cost from the root

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 42

Properties of UCS
Complete? Yes ( if step cost>0 )
Optimal? Yes
Time?
Space?

Time? O(b 1+[C*/] ), typically > O(bd)
Space? O(b 1+[C*/] )

C* cost of optimal solution
the smallest step cost

-> because UCS may explore long
paths of small steps before
exploring paths with large steps
which might be more useful

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 43

UCS and BFS
When is UCS equivalent to BFS? What should be the step cost and

the g(n) cost? Assume that among the nodes with the same priority
the left most is expanded first. Reminder:
g(n) is the cost from the root node to a given node
step cost is the cost between 2 nodes

Answer in all of these cases:
1. step cost is 1
2. step cost is the same (a constant) generalization ofcase 1
3. g(n) is the same (follows fromcase 2 if the step cost is a constant,

then g(n) is also a constant)
4. g(n)=depth(n)
5. g(n) is the same at each level and increasing as the level increases,

e.g. 5 for level 1, 7 for level 2, etc.

Draw a tree for each of these cases and run UCS and BFS!

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 44

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert children at the front of the fringe

Goal node: M

Fringe: A
Expanded: none

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 45

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: B, C
Expanded: A

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 46

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: D, E, C
Expanded: A, B

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 47

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: H, I, E, C
Expanded: A, B, D

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 48

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: I, E, C
Expanded: A, B, D, H

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 49

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: E, C
Expanded: A, B, D, H, I

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 50

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: J, K, C
Expanded: A, B, D, H, I, E

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 51

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: K, C
Expanded: A, B, D, H, I, E, J

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 52

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: C
Expanded: A, B, D, H, I, E, J, K

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 53

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: F, G
Expanded: A, B, D, H, I, E, J, K, C

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 54

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: L, M, G
Expanded: A, B, D, H, I, E, J, K, C, F

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 55

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert successors at the front of the fringe

Fringe: M, G
Expanded: A, B, D, H, I, E, J, K, C, F, L

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 56

Depth-First Search (DFS)
Expands deepest unexpanded node
Implementation: insert children at the front of the fringe

Fringe: M, G
Expanded: A, B, D, H, I, E, J, K, C, F, L

M is a goal node => stop
order of expansion: ABDHIEJKCFLM
solution node found: M
solution path found: ACFM

B

D E
H I J K L

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 57

DFS for Romania Example

DFS can perform infinite cyclic explorations => needs a
finite, non-cyclic search space or a repeated state checking
mechanism

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 58

Properties of DFS
Complete?

No, fails in infinite-depth spaces (i.e. m = )
Yes, in finite spaces (i.e. if m is finite)

Optimal? No
May find a solution longer than the optimal (even if step cost=1)

Time? 1+b+b2+b3+b4 + +bm = O(bm) similar to BFS
higher than BFS as m>>d (m=max depth, d=least cost solution depth)

Space? O(bm), linear; excellent; Why?
Suppose J and C
were goal nodes
and C is a better
solution than J;
DFS will find J
not optimal

Can get stuck going down a
very long (or even infinite)
path e.g. suppose the left sub-
tree was unbounded and did
not contain a goal node DFS
would never terminate

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 59

Space Complexity of DFS
Space? O(bm), linear; excellent why?
Once a node has been expanded, it can be removed from memory as

soon as all its descendants have been fully explored

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 60

Depth-Limited Search
Depth-limited search = DFS with depth limit l

i.e. it imposes a cutoff on the maximum depth
Properties similar to DFS:

Complete? Yes (as the search depth is always finite)
Optimal? No
Time? 1+b2+b3+b4 + +bl = O(bl)
Space? O(bl)

Problem how to select a good limit l? Based on domain knowledge.
There are 20 cities on the map of Romania => if there is a solution it

must be of length 19 at most => l=19
We can even see that any city can be reached from any other city in at

most 9 steps; this is called diameter of a state space => l=9
However, for most problems the diameterof the state space is not

known in advance , i.e. before we have solved the problem

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 61

Iterative Deepening Search (IDS)
Sidesteps the issue of choosing the best depth limit by trying all

possible depth limits in turn (0, 1, 2, etc.) and applying DFS
for depth=0 to do depth-limited search(depth):

Tries to combine the benefits of DFS (low memory) and BFS (completeness
if b is finite and optimality if step costs are the same) by repeated DFS
searches with increased depth

The nodes close to the root will be expanded multiple times but the
number of these nodes is small the majority of the nodes are close to the
leaves, not the root => the overhead is small

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 62

IDS, l=0
cutoff limit l=0
A tree till level l=0; do DFS
Goal found?

Yes -> stop
No -> increment l and repeat

Expanded: A
The tree we are searching
M is the goal node

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 63

IDS, l=1

Expanded: A, B, C

cutoff limit l=1
A tree till level l=1; do DFS
Goal found?

Yes -> stop
No -> increment l and repeat

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 64

IDS, l=2

Expanded: A, B, D, E, C, F, G

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 65

IDS, l=3

Expanded: A, B, D, H, I, E, J, K, C, F, L, M (goal)

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 66

IDS Overhead of Multiple Expansion
May seem wasteful as many nodes are expanded multiple times
But for most problems the overhead of this multiple expansion is

small!
BFS: # expansions: 1+b+b2++bd, i.e. 111 111 for b=10,d=5
IDS: #expansions: (d+1)1+(d)b+(d-1)b2++3bd-2+2bd-1+1bd , i.e.

123 456 for b=10,d=5 => only 11% more
IDS is the preferred method when there is a large search space and

the depth of the solution is unknown

Expanded:
A
A, B, C
A, B, D, E, C, F, G
A, B, D, H, I, E, J, K, C, F, L, M (goal)

B

D E
H I J K L

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 67

Properties of IDS
Combines the benefits of DFS and BFS
Complete? As BFS:

Yes [DFS: yes, if m is finite; no otherwise]*
Optimal? As BFS:

No in general; Yes if step cost=1
[DFS: not optimal, even if step cost=1] *

Time? As BFS:
(d+1)b0+db1+(d-1)b2+ +bd = O(bd)[DFS: O(bm)] *

Space? As DFS:
O(bd), linear

Where are the improvements of IDS in comparison to DFS?
in completeness, optimality and time (shown with *)

Can be modified to explore uniform-cost tree

b branching factor
d depth of least cost solution
m max depth

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 68

Summary
Example

DFS?
SADEG, solution found: SAG (non optimal)

BFS?
SABCDEG, solution found: SAG (non-optimal

solution; will find optimal solution only if step
cost=1)

UCS?
Resolving ties: Among nodes with the same

priority, expand the node that was added first to
the fringe

SADBCEG, solution found: SBG (optimal)
Among nodes with the same priority (E and C,
g=8), the first added to the fringe (C) was chosen
to be expanded first

IDS (l=2)
S SABC SADEG, solution found: SAG (non-

optimal solution; will find optimal solution only
if step cost=1)

S

A B C

D E G

1
5 8

3
7

9 4
3

G is the goal.
Give the list of
expanded nodes
and the solution
path.

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 69

Real-World Path Finding Problems
Planning trips from A to B Google maps, planning public

transport trips
Example web sites for planning air travel:

Initial and goal states: specified by the user
Actions: take any flight from the initial location, leaving after the

current time with enough time for within-airport transfer
Path cost: monetary cost, flight time, waiting time, time of the day

(too early/too late), frequent-flyer millage awards, customs and
immigration procedures

VLSI layout position millions of components and connections on a very
small chip (to minimize area and circuits delays)

Assembling objects by a robot find the correct order for the parts;
wrong order will require undoing some of the work already done

Protein design find a sequence of amino acids that will fold into a 3-
dimensional protein with useful properties (i.e. curing a disease)

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 70

Informed (Heuristic) Search Strategies

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 71

Informed vs Uninformed Search
A search strategy defines the order of node expansion
Uninformed search strategies do not use problem specific knowledge

beyond the definition of the problem, i.e. they do not use heuristic
knowledge. They:

expand nodes systematically, e.g. BFS: level by level, from left to right
know if a given node is a goal or non-goal node
cannot compare 2 non-goal nodes they do not know if one non-goal

node is better than another one based on heuristic knowledge
UCSdoes this but it is not based on heuristic knowledge but path

cost so far, so it is classified as uninformed
are typically inefficient in finding the solution (time and space)

Informed search strategies use problem-specific heuristic knowledge
to select the order of node expansion. They:

can compare non-goal nodes theyknowif one non-goal node is better
than another one

are typically more efficient

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 72

Best-first Search
How can informed strategies compare non-goal nodes?
By using domain specific knowledge to devise an evaluation

function which estimates how good each node is
The evaluation function assigns a value to each node
At each step, the best node is expanded (the one with the best

value)
This is called best-first search

Note that we dont really know which is the best node as we use an
estimate based on the evaluation function.So best-first search expands
the node that appears to be the best.

Fringe: insert children in decreasing order of desirability
We will study 2 best-first search algorithms:greedy and A*

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 73

Greedy Search

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 74

Romania with Step Coast and Straight-line
Distance to Bucharest

Problem-specific knowledge

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 75

Greedy Search (GS)
It uses the so called h value as an evaluation function (h

from heuristic)
The h(n) for a node n is the estimated cost from n to a

goal node
E.g. for the Romania example we can use h(n)=SLD(n,

Bucharest) = straight-line distance from n to Bucharest
Note that theh value of a goal node is 0, i.e. h(goal)=0

GS expands the node with the smallest h, i.e.
The note that appears to be closest to a goal

Thus: GS minimizes h, the estimated cost to a goal

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 76

Greedy Search for Romania Example

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 77

Greedy Search for Romania Example

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 78

Greedy Search for Romania Example

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 79

Greedy Search for Romania Example

Solution path: Arad-Sibiu-Fagaras-Bucharest, cost=450
Optimal =?

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 80

Greedy Search for Romania Example

Solution path: Arad-Sibiu-Fagaras-Bucharest, cost=450
Optimal =?

found=450

shorter: 418

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 81

Greedy Search Another Example
Given:

Goal nodes: C, I, E and K
Step path cost: along the links
h value of each node: in ()

Run GS
List of expanded nodes =?
Solution path =? Cost of the solution path=?

3

2 2

3

S

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

7

3 5 3

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 82

Solution
Fringe: S
Expanded: nill

3

2 2

3

S

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

7

3 5 3

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 83

Solution

Fringe: (A,3), (B,4)
Expanded: S

3

2 2

3

S

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

7

3 5 3

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 84

Solution
Fringe: (C,0), (B,4), (D, 5)//C and D are added and the fringe is ordered
Expanded: S, (A,3)

3

2 2

3

S

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

7

3 5 3

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 85

Solution
C is selected for expanding; is it a goal node? Yes ->stop

Expanded: S, A, C //note that the goal node is also considered to be
// expanded and is included in the list of expanded

Solution path: SAC, path cost: 2+8=10

3

2 2

3

S

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

7

3 5 3

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 86

Solution
Is SAC the optimal solution (i.e. shortest path to a goal)?

3

2 2

3

S

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

7

3 5 3

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 87

Properties of Greedy Search
Complete? As DFS

Yes, in finite space (if m is finite)
No fails in infinite spaces (and can get stuck in loops, e.g. Iasi->Neamt-

>Iasi->Neamt)
Optimal? No (e.g. Arad->Sibiu->R.Vincea->Pitesti->Buharest is

shorter)
Time? O(bm), but a good heuristic can give dramatic improvement
Space? O(bm) , keeps every node in memory

Irena Koprinska, [email protected]/3608 AI, week 2, 2018 88

Question
g(n) = cost so far
h(n) = estimated cost to the goal
Greedy search uses h(n)
Suppose that we run a greedy search algorithm with h(n) =
g(n). This greedy search will be equivalent to what kind of
uninformed search?
In other words, which algorithm uses g(n)?

UCS
3

2 2

3

S

A B

E F G

(4)

(2) (2)
(0)

K
(0)

C D

(0)
(5)

H I J

6
(4 )

( 0) ( 3)

(3)

8
4

7

3 5 3

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Shopping Cart
[SOLVED] Excel data structure algorithm Microsoft PowerPoint ai2.pptx
$25