# The types of search considered here are called *uninformed* because they do not use any *a priori* knowledge about the search domain and the search criteria.

Uninformed search algorithms are implemented on state space graphs such as the following one.

**A state space graph**

Here A, B, C, D, E, …, are the states with A as the Start state and U as the Goal state where the search conditions are fulfilled. The most common uninformed search algorithms are the breadth-first and depth-first searches.

The above state space graph is traversed in a breadth-first search of the goal as follows: **The BFS trace **

This trace of BFS is performed using two stacks, **open **and **close**.

**Task 1. **

Consider the depth-first search for the same graph.

Develop the trace of the DFS similar to the above BFS trace.

**Task 2. **

Develop the pseudocodes for both BFS and DFS using the stacks as above.

**Task 3. **

This task is about using the BFS and DFS for solving the 8-puzzle.

# 8-puzzle

The 8-puzzle belongs to the family of sliding block puzzles used as test problems for search algorithms in AI. It uses a 3 by 3 board of numbered (from 1 to 8) tiles and one empty space (shown below as a blue square). A tile adjacent to the empty square can be “swapped” with this empty space.

Starting with a given unordered displacement the steps should end up with the ordered tiles:

START à GOAL

The solution is illustrated with the following search tree expansion:

** **

**Using your favorite programming language develop two 8-puzzle programs implementing the BFS and DFS methods in accordance with the pseudocodes from Task 2. **

You should decide on

- representation of needed data structures to make the program more efficient;
- method of the tree expansion for an arbitrary start position of the tiles; (c) evaluation of a position – is it the goal?

**Run the both programs for some start positions. Compare the results. Which of the two methods works better? What criteria should be used for comparison? **

**Submission **

This Project can be performed by one or two students working together if you decide so.

Put your work into a single file including answers to all tasks above.

Include your codes, and the run results.

Submit your work to the Beachboard by Friday September 16, 11:59 pm.

The types of search considered here are called *uninformed* because they do not use any *a priori* knowledge about the search domain and the search criteria.

Uninformed search algorithms are implemented on state space graphs such as the following one.

**A state space graph**

Here A, B, C, D, E, …, are the states with A as the Start state and U as the Goal state where the search conditions are fulfilled. The most common uninformed search algorithms are the breadth-first and depth-first searches.

The above state space graph is traversed in a breadth-first search of the goal as follows: **The BFS trace **

This trace of BFS is performed using two stacks, **open **and **close**.

**Task 1. **

Consider the depth-first search for the same graph.

Develop the trace of the DFS similar to the above BFS trace.

**Task 2. **

Develop the pseudocodes for both BFS and DFS using the stacks as above.

**Task 3. **

This task is about using the BFS and DFS for solving the 8-puzzle.

# 8-puzzle

The 8-puzzle belongs to the family of sliding block puzzles used as test problems for search algorithms in AI. It uses a 3 by 3 board of numbered (from 1 to 8) tiles and one empty space (shown below as a blue square). A tile adjacent to the empty square can be “swapped” with this empty space.

Starting with a given unordered displacement the steps should end up with the ordered tiles:

START à GOAL

The solution is illustrated with the following search tree expansion:

** **

**Using your favorite programming language develop two 8-puzzle programs implementing the BFS and DFS methods in accordance with the pseudocodes from Task 2. **

You should decide on

- representation of needed data structures to make the program more efficient;
- method of the tree expansion for an arbitrary start position of the tiles; (c) evaluation of a position – is it the goal?

**Run the both programs for some start positions. Compare the results. Which of the two methods works better? What criteria should be used for comparison? **

## Reviews

There are no reviews yet.