Overview

Breadth First Search (BFS) and Depth First Search (DFS) are well-known graph traverse algorithms. In this project, you will need to implement BFS and DFS algorithms in order to solve the given problem.

Gold Miners

In this problem, your job is to place miners next to mining sites.

• Each miner can only be attached to a single mining site, there are as many miners as there are mining sites.
• The numbers across the top and down the side tell you how many miner are in the respective row or column.
• A miner can only be placed horizontally or vertically adjacent to a mining site.
• Miners are never adjacent to each other, neither vertically, horizontally, nor diagonally.
• A mining site might be next to two miners, but is only one miner can work on a single mining site.

An example problem and the solution can be seen below.

The problem given in the sample input file.	The solution given in the sample output file.

A) Implementation

• Formalize this problem in a well-defined graph form and present your state and action representations in detail.
  1. Each state can be represented as a node, and placement of a new miner may lead to a new node.
  2. You are not required to optimize the search procedure. Do not implement any forward checking mechanisms.
  3. Upon visiting a node, the constraints of the node must be checked. If the node does not meet the constraints, the node will not be expanded.

• Run both BFS and DFS algorithms (graph traversal version), and print the following information and analyze the results in terms of:
  • the number of the visited nodes
  • the maximum number of nodes kept in the memory
  • the running time

• The algorithm (BFS or DFS) to be used for search, the input file name and the output file name should be chosen by a command line argument as in the given example. Sample input files and output files are given. When the solution is found, you should write the results to the specified output file in the same format as the input file.

• You must use a graph representation for the model and solve it using DFS or BFS. Any other method will not be accepted.

• All your code must be written in C++, and should be compiled and run on ITUs Linux Server (you can access it through SSH) using g++. Otherwise your code will not be evaluated.

Your program should compile and run using the following commands:

(if you have other commands for compilation, you should state them as a comment in your code)

g++ sourcecode.cpp o project1

./project <dfs or bfs> <input-file-name> <output-file-name>

./project1 bfs input.txt output.txt

./project1 dfs input.txt output.txt

Sample Input File: (input.txt)

• The number of columns and the number of rows are given in the first row. Your code might be tested with the different number of rows or columns
• The numbers on the second line represents the number of miners that can be placed on the column.
• The numbers on the first column represents the number of miners that can be placed on the row
• . represents an empty location, s represents a mining site and m represents a miner.
• The columns are separated by tab(t) characters, and the rows are separated by line feed(
  ) characters.

8	8 2	2	0		2	2	1	2	1
2	.	s	.		.	.	.	s	.
1	s	.	s		.	.	.	.	.
1	.	.	.		.	.	.	.	.
2	.	.	s		.	.	.	.	s
0	.	s	.		.	.	.	.	.
3	.	.	.		s	.	.	.	.
0	.	s	.		.	.	.	s	.
3	.	.	.		s	.	.	s	.

Sample Output File: (output.txt)

8	8 2	2	0	2	2	1	2	1
2	m	s	.	.	.	m	s	.
1	s	.	s	m	.	.	.	.
1	m	.	.	.	.	.	.	.
2	.	.	s	m	.	.	m	s
0	.	s	.	.	.	.	.	.
3	.	m	.	s	m	.	m	.
0	.	s	.	.	.	.	s	.
3	.	m	.	s	m	.	s	m

Sample Output: The numbers may not reflect the real results.

> ./project1 dfs input.txt output.txt

Algorithm: DFS

Number of the visited nodes: 21

Maximum number of nodes kept in the memory: 9 Running time: 0.34 seconds

Solution is written to the file.

B) Report

• Present your problem formulation,
  1. Describe state and action representations in detail.
  2. Write your pseudo-code.
  3. Show complexity of your algorithm on the pseudo-code.

• Analyze and compare the algorithm results in terms of: the number of visited nodes
• the maximum number of nodes kept in the memory the running time.

• Why should we maintain a list of discovered nodes? How this affects the outcome of the algorithms?