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?