程序代写代做代考 Excel data structure algorithm Microsoft PowerPoint – ai2.pptx – INTERVIEW&CODEHELP

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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 1

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 4

Problem Solving and Search

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 7

Romania Example – Map

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 8

Romania

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

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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 (8×8) 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, irena.koprinska@sydney.edu.au COMP3308/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

Let’s take a closer look at 2 possible incremental formulations!

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 17

start with the initial node
the initial node at the beginning

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 19

Tree Search Example

Fringe: Arad
Expanded: none

Is Arad a goal node? No => expand it

• Let’s put the children of the expanded node at the end of the fringe

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 21

Tree Search Example (3)

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

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 25

Uninformed (Blind) Search Strategies

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 32

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

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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 doesn’t 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

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 35

Romania with Step Coast in km

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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

Arad Oradea Fagaras
Rimnicu
Vilcea

151 80

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

Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/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 of case 1
3. g(n) is the same (follows from case 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, irena.koprinska@sydney.edu.au COMP3308/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, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 2, 2018 45