Scribd
Upload
4 views6 pages

Sample Questions

The document outlines various search algorithms including Depth-First Search (DFS), Breadth-First Search (BFS), Uniform Cost Search (UCS), Iterative Deepening (ID), and A* Search, providing examples and questions for each. It includes tree structures and asks for paths, stack or queue states, and comparisons between different search methods. Additionally, it touches on a square root problem and a Traveling Salesman Problem (TSP) scenario, requiring calculations and justifications for heuristics.

Uploaded by

abeermaliik78
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views6 pages

Sample Questions

The document outlines various search algorithms including Depth-First Search (DFS), Breadth-First Search (BFS), Uniform Cost Search (UCS), Iterative Deepening (ID), and A* Search, providing examples and questions for each. It includes tree structures and asks for paths, stack or queue states, and comparisons between different search methods. Additionally, it touches on a square root problem and a Traveling Salesman Problem (TSP) scenario, requiring calculations and justifications for heuristics.

Uploaded by

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

Depth-First Search (DFS)

Question: Consider the tree below. Perform Depth-First Search starting from node S to find
node G. Show the stack at each step and state the path found.

/\

A B

/ \

C G

Question: Perform DFS on the following tree from S to G. Show stack at each step. If there are
multiple paths to G, state which one DFS finds first.

/\

A B

/\ \

C D E

/ /\ \

F G H I

Breadth-First Search (BFS)

Question: Perform BFS on the tree below from S to G. Show the queue at each step.

/\

A B

/ \

C G
Question: Perform BFS on this tree. Show queue at each step. Compare the path found with
DFS.

/\

A B

/\ \

C D E

/ /\ \

F G H I

Uniform Cost Search (UCS)

Question: Find the cheapest path from S to G using Uniform Cost Search. Edge costs are shown.

/\

2 3

/ \

A B

/ \

4 7

/ \

C G

Question: Find cheapest path from S to G using UCS.

/\

5 3

/ \

A B
/\ /\

2 4 2 1

/ \/ \

C D G

/\

3 2

/ \

E F

Iterative Deepening (ID)

Question: Explain how Iterative Deepening would work on a tree where G is at depth 3. What
depth limits would be tried?

text

Depth 0: S

Depth 1: A, B

Depth 2: C, D, E

Depth 3: F, G, H

Question: Perform Iterative Deepening on this tree. G is at depth 4. Show each iteration's
exploration.

text

/\

A B

/ \

C D

/ \

E F

/ \
G H

A* Search

Question: Find path from S to G using A* with given heuristic h(n).

text

/\

2 3

/ \

A B

/ \

4 7

/ \

C G

Heuristics: h(S)=10, h(A)=8, h(B)=5, h(C)=6, h(G)=0

Calculate f(n)=g(n)+h(n) for each node.

Question 2 is same as in UCS take tree from there and heuristics values are as follows:

Heuristics: h(S)=7, h(A)=5, h(B)=3, h(C)=4, h(D)=2, h(E)=1, h(F)=1, h(G)=0

Square Root

Question: In the square root problem (finding x such that x3 = y):

1. What is the state?

2. What is the utility function?

3. What is the operator?

4. What is the process?


A*
map with actual distances (edge costs) and straight-line heuristics (h-values):

text

A (h=140)

/\

75 118

/ \

B C (h=111)

/\ /\

71 75 70 90

/ \/ \

D (h=151) E (h=146) F (h=99)

\ /\ /

\ / \ /

\/ \/

G (h=80) H (h=97)

\ /

\ /

\/

I (h=0) Goal

1. Calculate f(n) = g(n) + h(n) for each node as you explore

2. Show the priority queue at each step

3. What path does A* find?

4. What is the total cost of the path?

5. Is the heuristic admissible? Justify for at least two nodes.


TSP
10

A ----- B

|\ |

|\ |

8| \ |9

| \ |

| \ |

| \|

C ----- D

Missing edges in the drawing but exist in the problem:

 A to D = 12 (the diagonal)

 B to C = 11 (the other diagonal)

You might also like