[go: up one dir, main page]
Scribd
Upload
10 views38 pages

4-Uninformed Search-part2

The document discusses various search algorithms including Depth-First Search (DFS), Iterative Deepening Search (IDS), and Bidirectional Search (BDS). It evaluates their completeness, time and space complexity, and optimality, highlighting the advantages and disadvantages of each method. Applications of these algorithms in real-world scenarios such as GPS navigation and social networks are also mentioned.

Uploaded by

Hoda Aboulgoud hasan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views38 pages

4-Uninformed Search-part2

The document discusses various search algorithms including Depth-First Search (DFS), Iterative Deepening Search (IDS), and Bidirectional Search (BDS). It evaluates their completeness, time and space complexity, and optimality, highlighting the advantages and disadvantages of each method. Applications of these algorithms in real-world scenarios such as GPS navigation and social networks are also mentioned.

Uploaded by

Hoda Aboulgoud hasan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 38

3.

DFS

1
3.DFS

2
DFS

3
DFS

4
DFS

5
DFS

6
DFS

7
DFS

8
DFS

9
DFS, evaluation

3. Depth-first search(DFS)

❖ Complete? No (fails in infinite-depth spaces, spaces with loops)

❖ Time? Time Consuming-O(b^m) > O(b^d)

❖ Space? Better than BFS --O(bm)

❖ Optimal? No

✓ m is the maximum depth of any node


✓ d is the depth of the shallowest solution

7
DFS, evaluation

❖ DFS would require 156 kilobytes instead of 10 exabytes at depth d = 16, a factor of
7 trillion times less space.

12
DFS-based BACKTRACKING SEARCH

❖A variant of DFS uses less memory.


❖Only O(m) memory is needed rather than O(bm).

❖Why??

13
DFS, Example

Consider this state space for a given problem :

Apply DFS to find the goal state, G?

14
4. Depth-limited search

❖Embarrassing failure of DFS in infinite state spaces


using a predetermined depth limit ℓ.

❖Time & space complexity is O(bℓ).

✓ DLS is a source of incompleteness--when??

✓ DLS is nonoptimal--when??

15
5. Iterative Deepening Search(IDS)

17
IDS

9
IDS

19
IDS

20
IDS

21
IDS

22
IDS

23
IDS

24
IDS

25
IDS

26
IDS

27
IDS

28
IDS

29
IDS

30
31
IDS, evaluation

Iterative Depth-search (IDS)

❖ Complete? Yes

❖ Time? Time Consuming –O(b^d)-BFS

❖ Space Less Space --DFS

❖ Optimal? Yes (if all trans. have same cost)

9
IDS

❑IDS seems wasteful and costly w.r.t. BFS!


❖Is this true? Specify!
✓ Ex. if b = 10 and d = 5

❖The preferred uninformed search method when the


search space is large, and the depth of the solution is
not known.

33
6. Bidirectional search (BDS)

❖BDS search simultaneously forward from START and backward


from GOAL.
❖Replacing the goal test with a check whether the frontiers of
the two searches intersect.
❖Solution is found if the two searches meet.

▪ Time & space complexity of BDS using BFS in both directions is


O(b^d/2).

35
BDS

❖ For example, if a problem has solution depth d=6, and


each direction runs BFS one node at a time, then in the
worst case the two searches meet when they have
generated all of the nodes at depth 3.

❖ For b=10, this means a total of 2,220 node generations,


compared with 1,111,110 for a standard BFS.

❖ Is there is some way to reduce the space requirements of BDS??

36
Applications

❖ GPS Navigation systems: Google Maps, which can give


directions to reach from one place to another using BDS

❖ Social Networks: Facebook treats each user profile as a node


on the graph search space and two nodes are said to be
connected if they are each other's friends.

37
Comparing uninformed search strategies

38
Quiz

❑ Based on this graph, initial state is S and goal state is G


1- Apply BFS to reach destination state
2- Apply DFS to reach destination state
3-Apply IDS to reach destination state
4-Apply UCS to reach destination state , is this the optimal solution? Why?

❑ For each algorithm:


- Compute solution cost, (if there is a solution)
- Express time and space in terms of # nodes
39
40
Thank You !

41

You might also like