# CS代考计算机代写 flex algorithm assembly computer architecture CS 561a: Introduction to Artificial Intelligence

CS 561a: Introduction to Artificial Intelligence

CS 561, Sessions 2-3

1

Last time: Summary

Definition of AI?

Turing Test?

Intelligent Agents:

Anything that can be viewed as perceiving its environment through sensors and acting upon that environment through its effectors to maximize progress towards its goals.

PAGE (Percepts, Actions, Goals, Environment)

Described as a Perception (sequence) to Action Mapping: f : P* A

Using look-up-table, closed form, etc.

Agent Types: Reflex, state-based, goal-based, utility-based

Rational Action: The action that maximizes the expected value of the performance measure given the percept sequence to date

CS 561, Sessions 2-3

2

Outline: Problem solving and search

Introduction to Problem Solving

Complexity

Uninformed search

Problem formulation

Search strategies: depth-first, breadth-first

Informed search

Search strategies: best-first, A*

Heuristic functions

CS 561, Sessions 2-3

3

Example: Measuring problem!

Problem: Using these three buckets,

measure 7 liters of water.

3 l

5 l

9 l

CS 561, Sessions 2-3

4

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

5

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

6

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

7

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

8

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

9

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

10

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

11

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

12

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

13

Example: Measuring problem!

(one possible) Solution:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

14

Example: Measuring problem!

Another Solution:

a b c

0 0 0 start

0 5 0

3 2 0

3 0 2

3 5 2

3 0 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

15

Example: Measuring problem!

Another Solution:

a b c

0 0 0 start

0 5 0

3 2 0

3 0 2

3 5 2

3 0 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

16

Example: Measuring problem!

Another Solution:

a b c

0 0 0 start

0 5 0

3 2 0

3 0 2

3 5 2

3 0 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

17

Example: Measuring problem!

Another Solution:

a b c

0 0 0 start

0 5 0

3 2 0

3 0 2

3 5 2

3 0 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

18

Example: Measuring problem!

Another Solution:

a b c

0 0 0 start

0 5 0

3 2 0

3 0 2

3 5 2

3 0 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

19

Example: Measuring problem!

Another Solution:

a b c

0 0 0 start

0 5 0

3 2 0

3 0 2

3 5 2

3 0 7 goal

3 l

5 l

9 l

a

b

c

CS 561, Sessions 2-3

20

Which solution do we prefer?

Solution 1:

a b c

0 0 0 start

3 0 0

0 0 3

3 0 3

0 0 6

3 0 6

0 3 6

3 3 6

1 5 6

0 5 7 goal

Solution 2:

a b c

0 0 0 start

0 5 0

3 2 0

3 0 2

3 5 2

3 0 7 goal

CS 561, Sessions 2-3

21

Problem-Solving Agent

Note: This is offline problem-solving. Online problem-solving involves acting w/o complete knowledge of the problem and environment

action

// From LA to San Diego (given curr. state)

// e.g., Gas usage

// What is the current state?

// If fails to reach goal, update

CS 561, Sessions 2-3

22

Example: Buckets

Measure 7 liters of water using a 3-liter, a 5-liter, and a 9-liter buckets.

Formulate goal: Have 7 liters of water in 9-liter bucket

Formulate problem:

States: amount of water in the buckets

Operators: Fill bucket from source, empty bucket

Find solution: sequence of operators that bring you

from current state to the goal state

CS 561, Sessions 2-3

23

Remember: Environment types

Environment Accessible Deterministic Episodic Static Discrete

Operating System Yes Yes No No Yes

Virtual Reality Yes Yes Yes/No No Yes/No

Office Environment No No No No No

Mars No Semi No Semi No

The environment types largely determine the agent design.

CS 561, Sessions 2-3

24

Problem types

Single-state problem: deterministic, accessible

Agent knows everything about world, thus can

calculate optimal action sequence to reach goal state.

Multiple-state problem: deterministic, inaccessible

Agent must reason about sequences of actions and

states assumed while working towards goal state.

Contingency problem: nondeterministic, inaccessible

Must use sensors during execution

Solution is a tree or policy

Often interleave search and execution

Exploration problem: unknown state space

Discover and learn about environment while taking actions.

CS 561, Sessions 2-3

25

Problem types

Single-state problem: deterministic, accessible

Agent knows everything about world (the exact state),

Can calculate optimal action sequence to reach goal state.

E.g., playing chess. Any action will result in an exact state

CS 561, Sessions 2-3

26

Problem types

Multiple-state problem: deterministic, inaccessible

Agent does not know the exact state (could be in any of the possible states)

May not have sensors at all

Assume states while working towards goal state.

E.g., walking in a dark room

If you are at the door, going straight will lead you to the kitchen

If you are at the kitchen, turning left leads you to the bedroom

…

CS 561, Sessions 2-3

27

Problem types

Contingency problem: nondeterministic, inaccessible

Must use sensors during execution

Solution is a tree or policy

Often interleave search and execution

E.g., a new skater in an arena

Sliding problem.

Many skaters around

CS 561, Sessions 2-3

28

Problem types

Exploration problem: unknown state space

Discover and learn about environment while taking actions.

E.g., Maze

CS 561, Sessions 2-3

29

Example: Vacuum world

Simplified world: 2 locations, each may or not contain dirt,

each may or not contain vacuuming agent.

Goal of agent: clean up the dirt.

CS 561, Sessions 2-3

30

CS 561, Sessions 2-3

31

CS 561, Sessions 2-3

32

CS 561, Sessions 2-3

33

CS 561, Sessions 2-3

34

Example: Romania

In Romania, on vacation. Currently in Arad.

Flight leaves tomorrow from Bucharest.

Formulate goal:

be in Bucharest

Formulate problem:

states: various cities

operators: drive between cities

Find solution:

sequence of cities, such that total driving distance is minimized.

CS 561, Sessions 2-3

35

Example: Traveling from Arad To Bucharest

CS 561, Sessions 2-3

36

CS 561, Sessions 2-3

37

Problem formulation

CS 561, Sessions 2-3

38

Selecting a state space

Real world is absurdly complex; some abstraction is necessary to allow us to reason on it…

Selecting the correct abstraction and resulting state space is a difficult problem!

Abstract states real-world states

Abstract operators sequences or real-world actions

(e.g., going from city i to city j costs Lij actually drive from city i to j)

Abstract solution set of real actions to take in the

real world such as to solve problem

CS 561, Sessions 2-3

39

Example: 8-puzzle

State:

Operators:

Goal test:

Path cost:

start state

goal state

CS 561, Sessions 2-3

40

State: integer location of tiles (ignore intermediate locations)

Operators: moving blank left, right, up, down (ignore jamming)

Goal test: does state match goal state?

Path cost: 1 per move

Example: 8-puzzle

start state

goal state

CS 561, Sessions 2-3

41

Example: 8-puzzle

start state

goal state

Why search algorithms?

8-puzzle has 362,880 states

15-puzzle has 10^12 states

24-puzzle has 10^25 states

So, we need a principled way to look for a solution in these huge search spaces…

CS 561, Sessions 2-3

42

Back to Vacuum World

CS 561, Sessions 2-3

43

Back to Vacuum World

CS 561, Sessions 2-3

44

Example: Robotic Assembly

CS 561, Sessions 2-3

45

Real-life example: Circuit Board Layout

Given schematic diagram comprising components (chips, resistors, capacitors, etc) and interconnections (wires), find optimal way to place components on a printed circuit board, under the constraint that only a small number of wire layers are available (and wires on a given layer cannot cross!)

“optimal way”??

minimize surface area

minimize number of signal layers

minimize number of vias (connections from one layer to another)

minimize length of some signal lines (e.g., clock line)

distribute heat throughout board

etc.

CS 561, Sessions 2-3

46

CS 561, Sessions 2-3

47

Use automated tools to place components

and route wiring.

CS 561, Sessions 2-3

48

CS 561, Sessions 2-3

49

Function General-Search(problem, strategy) returns a solution, or failure

initialize the search tree using the initial state problem

loop do

if there are no candidates for expansion then return failure

choose a leaf node for expansion according to strategy

if the node contains a goal state then

return the corresponding solution

else expand the node and add resulting nodes to the search tree

end

Search algorithms

Basic idea:

offline, systematic exploration of simulated state-space by generating successors of explored states (expanding)

CS 561, Sessions 2-3

50

Example: micromouse in a maze

CS 561, Sessions 2-3

51

Example: Traveling from Arad To Bucharest

CS 561, Sessions 2-3

52

From problem space to search tree

Some material in this and following slides is from

http://www.cs.kuleuven.ac.be/~dannyd/FAI/ check it out!

A

D

B

E

C

F

G

S

3

4

4

4

5

5

4

3

2

S

A

D

B

D

E

A

C

E

E

B

B

F

D

F

B

F

C

E

A

C

G

G

C

G

F

G

3

3

3

3

3

2

2

2

4

4

4

4

4

4

4

4

4

4

4

4

5

5

5

5

5

5

Problem space

Associated

loop-free

search tree

CS 561, Sessions 2-3

53

Paths in search trees

S

A

D

B

D

E

A

C

E

E

B

B

F

D

F

B

F

C

E

A

C

G

G

C

G

F

G

Denotes:

SA

Denotes:SDA

Denotes:

SDEBA

CS 561, Sessions 2-3

54

General search example

CS 561, Sessions 2-3

55

General search example

CS 561, Sessions 2-3

56

General search example

CS 561, Sessions 2-3

57

General search example

CS 561, Sessions 2-3

58

Implementation of search algorithms

Function General-Search(problem, Queuing-Fn) returns a solution, or failure

nodes make-queue(make-node(initial-state[problem]))

loop do

if nodes is empty then return failure

node Remove-Front(nodes)

if Goal-Test[problem] applied to State(node) succeeds then return node

nodes Queuing-Fn(nodes, Expand(node, Operators[problem]))

end

Queuing-Fn(queue, elements) is a queuing function that inserts a set of elements into the queue and determines the order of node expansion. Varieties of the queuing function produce varieties of the search algorithm.

CS 561, Sessions 2-3

59

Encapsulating state information in nodes

CS 561, Sessions 2-3

60

Paths in search trees

…

states

CS 561, Sessions 2-3

61

Paths in search trees

Search tree nodes

CS 561, Sessions 2-3

62

Evaluation of search strategies

A search strategy is defined by picking the order of node expansion.

Search algorithms are commonly evaluated according to the following four criteria:

Completeness: does it always find a solution if one exists?

Time complexity: how long does it take as function of num. of nodes?

Space complexity: how much memory does it require?

Optimality: does it guarantee the least-cost solution?

Time and space complexity are measured in terms of:

b – max branching factor of the search tree

d – depth of the least-cost solution

m – max depth of the search tree (may be infinity)

CS 561, Sessions 2-3

63

Binary Tree Example

root

N1

N2

N3

N4

N5

N6

Number of nodes at max depth: n = 2 max depth

Number of levels (given n at max depth) = log2(n)

Depth = 0

Depth = 1

Depth = 2

CS 561, Sessions 2-3

64

Complexity

Why worry about complexity of algorithms?

because a problem may be solvable in principle but may take too long to solve in practice

CS 561, Sessions 2-3

65

Complexity: Tower of Hanoi

CS 561, Sessions 2-3

66

Complexity:

Tower of Hanoi

CS 561, Sessions 2-3

67

Complexity: Tower of Hanoi

3-disk problem: 23 – 1 = 7 moves

64-disk problem: 264 – 1.

210 = 1024 1000 = 103,

264 = 24 * 260 24 * 1018 = 1.6 * 1019

One year 3.2 * 107 seconds

CS 561, Sessions 2-3

68

Complexity: Tower of Hanoi

The wizard’s speed = one disk / second

1.6 * 1019 = 5 * 3.2 * 1018 =

5 * (3.2 * 107) * 1011 =

(3.2 * 107) * (5 * 1011)

500 billion years

CS 561, Sessions 2-3

69

Complexity: Tower of Hanoi

The time required to move all 64 disks from needle 1 to needle 3 is roughly 5 * 1011 years.

It is estimated that our universe is about 15 billion = 1.5 * 1010 years old.

5 * 1011 = 50 * 1010 33 * (1.5 * 1010).

CS 561, Sessions 2-3

70

Complexity: Tower of Hanoi

Assume: a computer with 1 billion = 109 moves/second.

Moves/year=(3.2 *107) * 109 = 3.2 * 1016

To solve the problem for 64 disks:

264 1.6 * 1019 = 1.6 * 1016 * 103 =

(3.2 * 1016) * 500

500 years for the computer to generate 264 moves at the rate of 1 billion moves per second.

CS 561, Sessions 2-3

71

Complexity

Why worry about complexity of algorithms?

because a problem may be solvable in principle but may take too long to solve in practice

How can we evaluate the complexity of algorithms?

through asymptotic analysis, i.e., estimate time (or number of operations) necessary to solve an instance of size n of a problem when n tends towards infinity

See AIMA, Appendix A.

CS 561, Sessions 2-3

72

Complexity example: Traveling Salesman Problem

There are n cities, with a road of length Lij joining

city i to city j.

The salesman wishes to find a way to visit all cities that

is optimal in two ways:

each city is visited only once, and

the total route is as short as possible.

CS 561, Sessions 2-3

73

Complexity example: Traveling Salesman Problem

This is a hard problem: the only known algorithms (so far) to solve it have exponential complexity, that is, the number of operations required to solve it grows as exp(n) for n cities.

CS 561, Sessions 2-3

74

Why is exponential complexity “hard”?

It means that the number of operations necessary to compute the exact solution of the problem grows exponentially with the size of the problem (here, the number of cities).

exp(1) = 2.72

exp(10) = 2.20 104 (daily salesman trip)

exp(100) = 2.69 1043 (monthly salesman planning)

exp(500) = 1.40 10217 (music band worldwide tour)

exp(250,000) = 10108,573 (fedex, postal services)

Fastest

computer = 1012 operations/second

CS 561, Sessions 2-3

75

So…

In general, exponential-complexity problems cannot be solved for any but the smallest instances!

CS 561, Sessions 2-3

76

Complexity

Polynomial-time (P) problems: we can find algorithms that will solve them in a time (=number of operations) that grows polynomially with the size of the input.

for example: sort n numbers into increasing order: poor algorithms have n^2 complexity, better ones have n log(n) complexity.

CS 561, Sessions 2-3

77

Complexity

Since we did not state what the order of the polynomial is, it could be very large! Are there algorithms that require more than polynomial time?

Yes (until proof of the contrary); for some algorithms, we do not know of any polynomial-time algorithm to solve them. These belong to the class of nondeterministic-polynomial-time (NP) algorithms (which includes P problems as well as harder ones).

for example: traveling salesman problem.

In particular, exponential-time algorithms are believed to be NP.

CS 561, Sessions 2-3

78

Note on NP-hard problems

The formal definition of NP problems is:

A problem is nondeterministic polynomial if there exists some algorithm that can guess a solution and then verify whether or not the guess is correct in polynomial time.

(one can also state this as these problems being solvable in polynomial time on a nondeterministic Turing machine.)

In practice, until proof of the contrary, this means that known algorithms that run on known computer architectures will take more than polynomial time to solve the problem.

CS 561, Sessions 2-3

79

Complexity: O() and o() measures (Landau symbols)

How can we represent the complexity of an algorithm?

Given: Problem input (or instance) size: n

Number of operations to solve problem: f(n)

If, for a given function g(n), we have:

then f is dominated by g

If, for a given function g(n), we have:

then f is negligible compared to g

CS 561, Sessions 2-3

80

Landau symbols

is bounded

CS 561, Sessions 2-3

81

Examples, properties

f(n)=n, g(n)=n^2:

n is o(n^2), because n/n^2 = 1/n -> 0 as n ->infinity

similarly, log(n) is o(n)

n^C is o(exp(n)) for any C

if f is O(g), then for any K, K.f is also O(g); idem for o()

if f is O(h) and g is O(h), then for any K, L: K.f + L.g is O(h)

idem for o()

if f is O(g) and g is O(h), then f is O(h)

if f is O(g) and g is o(h), then f is o(h)

if f is o(g) and g is O(h), then f is o(h)

CS 561, Sessions 2-3

82

Polynomial-time hierarchy

From Handbook of Brain

Theory & Neural Networks

(Arbib, ed.;

MIT Press 1995).

AC0

NC1

NC

P complete

NP complete

P

NP

PH

AC0: can be solved using gates of constant depth

NC1: can be solved in logarithmic depth using 2-input gates

NC: can be solved by small, fast parallel computer

P: can be solved in polynomial time

P-complete: hardest problems in P; if one of them can be proven to be

NC, then P = NC

NP: nondeterministic-polynomial algorithms

NP-complete: hardest NP problems; if one of them can be proven to be

P, then NP = P

PH: polynomial-time hierarchy

CS 561, Sessions 2-3

83

Complexity and the human brain

Are computers close to human brain power?

Current computer chip (CPU):

10^3 inputs (pins)

10^7 processing elements (gates)

2 inputs per processing element (fan-in = 2)

processing elements compute boolean logic (OR, AND, NOT, etc)

Typical human brain:

10^7 inputs (sensors)

10^10 processing elements (neurons)

fan-in = 10^3

processing elements compute complicated functions

Still a lot of improvement needed for computers; but

computer clusters come close!

CS 561, Sessions 2-3

84

Remember: Implementation of search algorithms

Function General-Search(problem, Queuing-Fn) returns a solution, or failure

nodes make-queue(make-node(initial-state[problem]))

loop do

if nodes is empty then return failure

node Remove-Front(nodes)

if Goal-Test[problem] applied to State(node) succeeds then return node

nodes Queuing-Fn(nodes, Expand(node, Operators[problem]))

end

Queuing-Fn(queue, elements) is a queuing function that inserts a set of elements into the queue and determines the order of node expansion. Varieties of the queuing function produce varieties of the search algorithm.

85

Remember: Implementation of search algorithms

Function General-Search(problem, Queuing-Fn) returns a solution, or failure

nodes make-queue(make-node(initial-state[problem]))

loop do

if nodes is empty then return failure

node Remove-Front(nodes)

if Goal-Test[problem] applied to State(node) succeeds then return node

nodes Queuing-Fn(nodes, Expand(node, Operators[problem]))

end

Breadth-first search: Enqueue expanded (children) nodes to the back of the queue (FIFO order)

Depth-first search: Enqueue expanded (children) nodes to the front of the queue (LIFO order)

Uniform cost search: Enqueue expanded (children) nodes so that queue is ordered by path cost (priority queue order).

CS 561, Sessions 2-3

86

Encapsulating state information in nodes

CS 561, Sessions 2-3

87

Evaluation of search strategies

A search strategy is defined by picking the order of node expansion.

Search algorithms are commonly evaluated according to the following four criteria:

Completeness: does it always find a solution if one exists?

Time complexity: how long does it take as function of num. of nodes?

Space complexity: how much memory does it require?

Optimality: does it guarantee the least-cost solution?

Time and space complexity are measured in terms of:

b – max branching factor of the search tree

d – depth of the least-cost solution

m – max depth of the search tree (may be infinity)

CS 561, Sessions 2-3

88

Note: Approximations

In our complexity analysis, we do not take the built-in loop-detection into account.

The results only ‘formally’ apply to the variants of our algorithms WITHOUT loop-checks.

Studying the effect of the loop-checking on the complexity is hard:

overhead of the checking MAY or MAY NOT be compensated by the reduction of the size of the tree.

Also: our analysis DOES NOT take the length (space) of representing paths into account !!

http://www.cs.kuleuven.ac.be/~dannyd/FAI/

CS 561, Sessions 2-3

89

Uninformed search strategies

Use only information available in the problem formulation

Breadth-first

Uniform-cost

Depth-first

Depth-limited

Iterative deepening

CS 561, Sessions 2-3

90

Breadth-first search

CS 561, Sessions 2-3

91

Breadth-first search

Move downwards, level by level, until goal is reached.

S

A

D

B

D

A

E

C

E

E

B

B

F

D

F

B

F

C

E

A

C

G

G

G

G

F

C

CS 561, Sessions 2-3

92

Example: Traveling from Arad To Bucharest

CS 561, Sessions 2-3

93

Breadth-first search

CS 561, Sessions 2-3

94

Breadth-first search

CS 561, Sessions 2-3

95

Breadth-first search

CS 561, Sessions 2-3

96

Properties of breadth-first search

Completeness:

Time complexity:

Space complexity:

Optimality:

Search algorithms are commonly evaluated according to the following four criteria:

Completeness: does it always find a solution if one exists?

Time complexity: how long does it take as function of num. of nodes?

Space complexity: how much memory does it require?

Optimality: does it guarantee the least-cost solution?

Time and space complexity are measured in terms of:

b – max branching factor of the search tree

d – depth of the least-cost solution

m – max depth of the search tree (may be infinity)

CS 561, Sessions 2-3

97

Properties of breadth-first search

Completeness: Yes, if b is finite

Time complexity: 1+b+b2+…+bd = O(b d), i.e., exponential in d

Space complexity: O(b d) (see following slides)

Optimality: Yes (assuming cost = 1 per step)

CS 561, Sessions 2-3

98

Time complexity of breadth-first search

If a goal node is found on depth d of the tree, all nodes up till that depth are created and examined (note: and the children of nodes at depth d are created and enqueued, but not yet examined).

m

G

b

d

Thus: O(bd)

CS 561, Sessions 2-3

99

QUEUE contains all nodes. (Thus: 4) .

In General: bd+1 – b ~ bd

Space complexity of breadth-first

Largest number of nodes in QUEUE is reached on the level d+1 just beyond the goal node.

G

b

d

CS 561, Sessions 2-3

100

Demo

CS 561, Sessions 2-3

101

Uniform-cost search

So, the queueing function keeps the node list sorted by increasing path cost, and we expand the first unexpanded node (hence with smallest path cost)

A refinement of the breadth-first strategy:

Breadth-first = uniform-cost with path cost = node depth

CS 561, Sessions 2-3

102

Romania with step costs in km

CS 561, Sessions 2-3

103

Uniform-cost search

CS 561, Sessions 2-3

104

Uniform-cost search

CS 561, Sessions 2-3

105

Uniform-cost search

CS 561, Sessions 2-3

106

Properties of uniform-cost search

Completeness: Yes, if step cost >0

Time complexity: # nodes with g cost of optimal solution, O(b d)

Space complexity: # nodes with g cost of optimal solution, O(b d)

Optimality: Yes, as long as path cost never decreases

g(n) is the path cost to node n

Remember:

b = branching factor

d = depth of least-cost solution

CS 561, Sessions 2-3

107

Implementation of uniform-cost search

Initialize Queue with root node (built from start state)

Repeat until (Queue empty) or (first node has Goal state):

Remove first node from front of Queue

Expand node (find its children)

Reject those children that have already been considered, to avoid loops

Add remaining children to Queue, in a way that keeps entire queue sorted by increasing path cost

If Goal was reached, return success, otherwise failure

CS 561, Sessions 2-3

108

Caution!

Uniform-cost search not optimal if it is terminated when any node in the queue has goal state.

G

100

5

D

5

10

E

5

15

F

5

20

S

A

C

1

5

5

1

B

1

2

Uniform cost returns the path with cost 102 (if any goal node is considered a solution), while there is a path with cost 25.

CS 561, Sessions 2-3

109

Note: Loop Detection

In class, we saw that the search may fail or be sub-optimal if:

– no loop detection: then algorithm runs into infinite cycles

(A -> B -> A -> B -> …)

– not queuing-up a node that has a state which we have

already visited: may yield suboptimal solution

– simply avoiding to go back to our parent: looks promising,

but we have not proven that it works

Solution? do not enqueue a node if its state matches the state of any of its parents (assuming path costs>0).

Indeed, if path costs > 0, it will always cost us more to consider a node with that state again than it had already cost us the first time.

Is that enough??

CS 561, Sessions 2-3

110

Example

G

From: http://www.csee.umbc.edu/471/current/notes/uninformed-search/

CS 561, Sessions 2-3

111

Breadth-First Search Solution

From: http://www.csee.umbc.edu/471/current/notes/uninformed-search/

CS 561, Sessions 2-3

112

Uniform-Cost Search Solution

From: http://www.csee.umbc.edu/471/current/notes/uninformed-search/

CS 561, Sessions 2-3

113

Note: Queueing in Uniform-Cost Search

In the previous example, it is wasteful (but not incorrect) to queue-up three nodes with G state, if our goal if to find the least-cost solution:

Although they represent different paths, we know for sure that the one with smallest path cost (9 in the example) will yield a solution with smaller total path cost than the others.

So we can refine the queueing function by:

– queue-up node if

1) its state does not match the state of any parent

and 2) path cost smaller than path cost of any

unexpanded node with same state in the queue (and in this case, replace old node with same

state by our new node)

Is that it??

CS 561, Sessions 2-3

114

A Clean Robust Algorithm

Function UniformCost-Search(problem, Queuing-Fn) returns a solution, or failure

open make-queue(make-node(initial-state[problem]))

closed [empty]

loop do

if open is empty then return failure

currnode Remove-Front(open)

if Goal-Test[problem] applied to State(currnode) then return currnode

children Expand(currnode, Operators[problem])

while children not empty

[… see next slide …]

end

closed Insert(closed, currnode)

open Sort-By-PathCost(open)

end

CS 561, Sessions 2-3

115

A Clean Robust Algorithm

[… see previous slide …]

children Expand(currnode, Operators[problem])

while children not empty

child Remove-Front(children)

if no node in open or closed has child’s state

open Queuing-Fn(open, child)

else if there exists node in open that has child’s state

if PathCost(child) < PathCost(node)
open Delete-Node(open, node)
open Queuing-Fn(open, child)
else if there exists node in closed that has child’s state
if PathCost(child) < PathCost(node)
closed Delete-Node(closed, node)
open Queuing-Fn(open, child)
end
[… see previous slide …]
CS 561, Sessions 2-3
116
Example
G
100
5
D
5
E
5
F
5
S
A
C
1
5
B
1
1
# State Depth Cost Parent
1 S 0 0 -
CS 561, Sessions 2-3
117
Example
G
100
5
D
5
E
5
F
5
S
A
C
1
5
B
1
1
# State Depth Cost Parent
1 S 0 0 -
2 A 1 1 1
3 C 1 5 1
Insert expanded nodes
Such as to keep open queue
sorted
Black = open queue
Grey = closed queue
CS 561, Sessions 2-3
118
Example
G
100
5
D
5
E
5
F
5
S
A
C
1
5
B
1
1
# State Depth Cost Parent
1 S 0 0 -
2 A 1 1 1
4 B 2 2 2
3 C 1 5 1
Node 2 has 2 successors: one with state B
and one with state S.
We have node #1 in closed with state S;
but its path cost 0 is smaller than the path
cost obtained by expanding from A to S.
So we do not queue-up the successor of
node 2 that has state S.
CS 561, Sessions 2-3
119
Example
G
100
5
D
5
E
5
F
5
S
A
C
1
5
B
1
1
# State Depth Cost Parent
1 S 0 0 -
2 A 1 1 1
4 B 2 2 2
5 C 3 3 4
6 G 3 102 4
Node 4 has a successor with state C and
Cost smaller than node #3 in open that
Also had state C; so we update open
To reflect the shortest path.
CS 561, Sessions 2-3
120
Example
G
100
5
D
5
E
5
F
5
S
A
C
1
5
B
1
1
# State Depth Cost Parent
1 S 0 0 -
2 A 1 1 1
4 B 2 2 2
5 C 3 3 4
7 D 4 8 5
6 G 3 102 4
CS 561, Sessions 2-3
121
Example
G
100
5
D
5
E
5
F
5
S
A
C
1
5
B
1
1
# State Depth Cost Parent
1 S 0 0 -
2 A 1 1 1
4 B 2 2 2
5 C 3 3 4
7 D 4 8 5
8 E 5 13 7
6 G 3 102 4
CS 561, Sessions 2-3
122
Example
G
100
5
D
5
E
5
F
5
S
A
C
1
5
B
1
1
# State Depth Cost Parent
1 S 0 0 -
2 A 1 1 1
4 B 2 2 2
5 C 3 3 4
7 D 4 8 5
8 E 5 13 7
9 F 6 18 8
6 G 3 102 4
CS 561, Sessions 2-3
123
Example
G
100
5
D
5
E
5
F
5
S
A
C
1
5
B
1
1
# State Depth Cost Parent
1 S 0 0 -
2 A 1 1 1
4 B 2 2 2
5 C 3 3 4
7 D 4 8 5
8 E 5 13 7
9 F 6 18 8
10 G 7 23 9
The node with state G and cost 102 has been removed from the open queue and replaced by cheaper node with state G and cost 23 which was pushed into the open queue.
CS 561, Sessions 2-3
124
Example
G
100
5
D
5
E
5
F
5
S
A
C
1
5
B
1
1
# State Depth Cost Parent
1 S 0 0 -
2 A 1 1 1
4 B 2 2 2
5 C 3 3 4
7 D 4 8 5
8 E 5 13 7
9 F 6 18 8
10 G 7 23 9
Goal reached
CS 561, Sessions 2-3
125
Depth-first search
CS 561, Sessions 2-3
126
Depth First Search
B
C
E
D
F
G
S
A
CS 561, Sessions 2-3
127
Romania with step costs in km
CS 561, Sessions 2-3
128
Depth-first search
CS 561, Sessions 2-3
129
Depth-first search
CS 561, Sessions 2-3
130
Depth-first search
CS 561, Sessions 2-3
131
Properties of depth-first search
Completeness: No, fails in infinite state-space (yes if finite state space)
Time complexity: O(b m)
Space complexity: O(bm)
Optimality: No
Remember:
b = branching factor
m = max depth of search tree
CS 561, Sessions 2-3
132
Time complexity of depth-first: details
In the worst case:
the (only) goal node may be on the right-most branch,
G
m
b
Time complexity == bm + bm-1 + … + 1 = bm+1 -1
Thus: O(bm)
b - 1
CS 561, Sessions 2-3
133
Space complexity of depth-first
Largest number of nodes in QUEUE is reached in bottom left-most node.
Example: m = 2, b = 3 :
...
QUEUE contains all nodes. Thus: 4.
In General: ((b-1) * m)
Order: O(m*b)
G
CS 561, Sessions 2-3
134
Avoiding repeated states
In increasing order of effectiveness and computational overhead:
do not return to state we come from, i.e., expand function will skip possible successors that are in same state as node’s parent.
do not create paths with cycles, i.e., expand function will skip possible successors that are in same state as any of node’s ancestors.
do not generate any state that was ever generated before, by keeping track (in memory) of every state generated, unless the cost of reaching that state is lower than last time we reached it.
CS 561, Sessions 2-3
135
Depth-limited search
Is a depth-first search with depth limit l
Implementation:
Nodes at depth l have no successors.
Complete: if cutoff chosen appropriately then it is guaranteed to find a solution.
Optimal: it does not guarantee to find the least-cost solution
CS 561, Sessions 2-3
136
Iterative deepening search
Function Iterative-deepening-Search(problem) returns a solution,
or failure
for depth = 0 to do
result Depth-Limited-Search(problem, depth)
if result succeeds then return result
end
return failure
Combines the best of breadth-first and depth-first search strategies.
Completeness: Yes,
Time complexity: O(b d)
Space complexity: O(bd)
Optimality: Yes, if step cost = 1
CS 561, Sessions 2-3
137
Romania with step costs in km
CS 561, Sessions 2-3
138
CS 561, Sessions 2-3
139
CS 561, Sessions 2-3
140
CS 561, Sessions 2-3
141
CS 561, Sessions 2-3
142
CS 561, Sessions 2-3
143
CS 561, Sessions 2-3
144
CS 561, Sessions 2-3
145
CS 561, Sessions 2-3
146
Iterative deepening complexity
Iterative deepening search may seem wasteful because so many states are expanded multiple times.
In practice, however, the overhead of these multiple expansions is small, because most of the nodes are towards leaves (bottom) of the search tree:
thus, the nodes that are evaluated several times
(towards top of tree) are in relatively small number.
CS 561, Sessions 2-3
147
Iterative deepening complexity
In iterative deepening, nodes at bottom level are expanded once, level above twice, etc. up to root (expanded d+1 times) so total number of expansions is:
(d+1)1 + (d)b + (d-1)b^2 + … + 3b^(d-2) + 2b^(d-1) + 1b^d = O(b^d)
In general, iterative deepening is preferred to depth-first or breadth-first when search space large and depth of solution not known.
CS 561, Sessions 2-3
148
Bidirectional search
Both search forward from initial state, and backwards from goal.
Stop when the two searches meet in the middle.
Problem: how do we search backwards from goal??
predecessor of node n = all nodes that have n as successor
this may not always be easy to compute!
if several goal states, apply predecessor function to them just as we applied successor (only works well if goals are explicitly known; may be difficult if goals only characterized implicitly).
Goal
Start
CS 561, Sessions 2-3
149
Bidirectional search
Problem: how do we search backwards from goal?? (cont.)
…
for bidirectional search to work well, there must be an efficient way to check whether a given node belongs to the other search tree.
select a given search algorithm for each half.
Goal
Start
CS 561, Sessions 2-3
150
Bidirectional search
1. QUEUE1 <-- path only containing the root;
QUEUE2 <-- path only containing the goal;
2. WHILE both QUEUEs are not empty
AND QUEUE1 and QUEUE2 do NOT share a state
DO remove their first paths;
create their new paths (to all children);
reject their new paths with loops;
add their new paths to back;
3. IF QUEUE1 and QUEUE2 share a state
THEN success;
ELSE failure;
CS 561, Sessions 2-3
151
Bidirectional search
Completeness: Yes,
Time complexity: 2*O(b d/2) = O(b d/2)
Space complexity: O(b m/2)
Optimality: Yes
To avoid one by one comparison, we need a hash table of size O(b m/2)
If hash table is used, the cost of comparison is O(1)
CS 561, Sessions 2-3
152
Bidirectional Search
d
d / 2
Initial State
Final State
CS 561, Sessions 2-3
153
Bidirectional search
Bidirectional search merits:
Big difference for problems with branching factor b in both directions
A solution of length d will be found in O(2bd/2) = O(bd/2)
For b = 10 and d = 6, only 2,222 nodes are needed instead of 1,111,111 for breadth-first search
CS 561, Sessions 2-3
154
Bidirectional search
Bidirectional search issues
Predecessors of a node need to be generated
Difficult when operators are not reversible
What to do if there is no explicit list of goal states?
For each node: check if it appeared in the other search
Needs a hash table of O(bd/2)
What is the best search strategy for the two searches?
CS 561, Sessions 2-3
155
Comparing uninformed search strategies
Criterion Breadth- Uniform Depth- Depth- Iterative Bidirectional
first cost first limited deepening (if applicable)
Time b^d b^d b^m b^l b^d b^(d/2)
Space b^d b^d bm bl bd b^(d/2)
Optimal? Yes Yes No No Yes Yes
Complete? Yes Yes No Yes, Yes Yes
if ld
b – max branching factor of the search tree
d – depth of the least-cost solution
m – max depth of the state-space (may be infinity)
l – depth cutoff
CS 561, Sessions 2-3
156
Summary
Problem formulation usually requires abstracting away real-world details to define a state space that can be explored using computer algorithms.
Once problem is formulated in abstract form, complexity analysis helps us picking out best algorithm to solve problem.
Variety of uninformed search strategies; difference lies in method used to pick node that will be further expanded.
Iterative deepening search only uses linear space and not much more time than other uniformed search strategies.
)
(
)
(
)
(
,
,
,
,
0
0
g
O
f
n
kg
n
f
n
n
n
n
k
Î
£
³
N
Î
"
N
Î
$
Â
Î
$
)
(
)
(
)
(
,
,
,
,
0
0
g
o
f
n
kg
n
f
n
n
n
n
k
Î
£
³
N
Î
"
N
Î
$
Â
Î
"
0
)
(
)
(
)
(
)
(
,
)
(
®
£
¥
®
¥
®
Û
"
Û
Î
n
n
n
g
n
f
n
kg
n
f
k
g
o
f
g
f
n
kg
n
f
k
g
O
f
n
Û
$
Û
Î
£
¥
®
)
(
)
(
,
)
(
/docProps/thumbnail.jpeg