Description
Lab 3: Uninformed Search Strategies
Uninformed strategies use only the information available in the problem definition. Uninformed Search includes the following algorithms:
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Uniform Cost Search (UCS)
- Depth Limited Search (DLS)
- Iterative Deepening Search (IDS)
- Bidirectional Search (BS)
BFS
- Expand shallowest unexpanded node.
- In breadth-first search the frontier is implemented as a FIFO (first-in, first-out) queue. Thus, the path that is selected from the frontier is the one that was added earliest.
- This approach implies that the paths from the start node are generated in order of the number of arcs in the path. One of the paths with the fewest arcs is selected at each stage.
Pseudocode:
Input: A graph G and a starting vertex v of G
Output: All vertices reachable from v labeled as explored.
A non-recursive implementation of breadth-first search:
Fig 1.
Exercise 1:
- Write a program to implement BFS in Fig 1.
- Show which sequences of paths are explored by BFS.
- Use queue/stack data structure that you implemented in Experiment 2.
