need help with CS homework

Rawan ageeli
CS330_Module2_Part3.pdf
Home>Computer Science homework help>need help with CS homework

www.funFruit.com CS330 By Fozia Noor

www.funFruit.com CS330 By Fozia Noor

Chapter Outline

Problem Solving agent

Definition of Problems and their Solution

Search Algorithms

Performance Measure of each algorithm

www.funFruit.com CS330 By Fozia Noor

Restrict a depth-first search to a fixed depth.

If no path was found, increase the depth and

restart the search.

www.funFruit.com CS330 By Fozia Noor

 The problem with DLS is choosing a depth parameter

 incomplete or admits poor solutions

 It is complete and find best solution

 Basic idea is:

 do IDS for depth n = 0; if solution found, return It;

 otherwise do IDS for depth n = n + 1; if solution found, return it, etc;

 So we repeat IDS for all depths until solution found.

 Useful if the search space is large and the maximum depth of the solution is

not known.

www.funFruit.com CS330 By Fozia Noor 5

L=0

www.funFruit.com CS330 By Fozia Noor 6

L=1

www.funFruit.com CS330 By Fozia Noor 7

L=2

www.funFruit.com CS330 By Fozia Noor 8

L=3

www.funFruit.com CS330 By Fozia Noor

www.funFruit.com CS330 By Fozia Noor

 Uniform cost searches always expand the node with the lowest total

path cost from the initial node.

 UCS is always optimal because of the fact that they start from the

initial start node when they calculate the path cost in the search

10

www.funFruit.com CS330 By Fozia Noor

Searching Algorithm

Frontier = queue ordered by path cost.

www.funFruit.com CS330 By Fozia Noor

Consider the following problem…

B

C

S G

A

15

1 10

5

5 5

We want to find the shortest route from node S to node G; that is, node S is the initial state and node G is the goal state…

Example: UCS

www.funFruit.com CS330 By Fozia Noor

S

Queue: Empty

Current level: n/a Current level: 0

Queue: S

A

B

C

Queue: A, B, C

1

15

5 S

Current level: 1

G

10 A

Queue: B, G11, C

Current level: 0 Current level: 1

5

Queue: G10, G11, C15

B

Current level: 2

G G G G G

The goal state is achieved and the path S-B-G is returned. In relation to path cost, UCS has found the optimal

route. Press space to end.

Example: UCS

www.funFruit.com CS330 By Fozia Noor

www.funFruit.com CS330 By Fozia Noor

Initial State: S

Goal State :g

www.funFruit.com CS330 By Fozia Noor 16

S B

A D

E

C

F

G

1 20

2

3

4 8

6 1 1

The graph above shows the step-costs for different paths going from the start (S) to

the goal (G).

Use uniform cost search to find the optimal path to the goal.

www.funFruit.com CS330 By Fozia Noor

Arad

Bucharest

Oradea Zerind

Faragas

Neamt

Iasi

Vaslui

Hirsova

Eforie

Urziceni

Giurgui

Pitesti

Dobreta

Craiova

Rimnicu

Mehadia

Timisoara

Lugoj

87

92

142

86

98

86

211

101

90

99

71

75

140 118

111

70

75

120

138

146

97

80

140

80

97

101

Sibiu

Rimnicu

www.funFruit.com CS330 By Fozia Noor 18

www.funFruit.com CS330 By Fozia Noor 19

Goal Start

 It runs two simultaneous searches: 2 queues

 One forward from the initial state, and one backward from the leaf,

 Stopping when the two meet in the middle.

 Both of forward and backward will deal with half of the nodes

www.funFruit.com CS330 By Fozia Noor