A class of general-purpose algorithms that operates in a brute force way. The search space is explored without leveraging on any information on the problem. Also called blind search. Since the methods are generic, they are intrinsically inefficient Blind/Uniformed Search – searching without information. For example: BFS (one of blind search method). We just generate all successor state (child node) for current state (current node) and find is there a goal state among them, if isn’t we will generate one of child node’s successor and so on. Because we don’t have information, so just generate all.

This lecture will teaches you

• How to search a state space using depth first search strategy

Student should have information regarding uninformed searches

Depth-first search (DFS)

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Activity 1:

Create a simple tree

Solution:

tree = {

‘A’ : [‘B’,’C’],

‘B’ : [‘D’, ‘E’],

‘C’ : [‘F’],

‘D’ : [],

‘E’ : [],

‘F’ : []

}

print(tree)

Activity 2:

Convert the Activity 1 tree in following graph

Solution:

tree = {

‘A’ : [‘B’,’C’],

‘B’ : [‘D’, ‘E’],

‘C’ : [‘F’],

‘D’ : [],

‘E’ : [‘F’], ‘F’ : []

}

Activity 3:

Perform depth first search on Lab activity 1 and Lab activity 2:

visited = set() # Set to keep track of visited nodes. def dfs(visited, tree, node):

if node not in visited: print (node) visited.add(node)

for neighbour in tree[node]: dfs(visited, tree, neighbour)

# Driver Code

dfs(visited, tree, ‘A’)

Activity 4:

Assume the following train network between 6 cities