need help with CS homework
Rawan ageeli
CS330_Module2_Part3.pdf
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 20
https://www.youtube.com/watch?v=4i-2X73t3U0
www.funFruit.com CS330 By Fozia Noor
