Description
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.
Farmer, Rabbit, Fox and Bag of Carrots A farmer with his rabbit, bag of carrots and fox came to the east side of a river that they wish to cross. The farmer has a boat at the river’s edge, but only he can row. The boat can only hold single thing(rabbit, bag of carrots or fox) in addition to the rower at any one time. If the fox is left alone with the rabbit, the fox may eat it. Similarly if the rabbit is left alone with the bag of carrots, the rabbit will eat it. How can the farmer get to the west side of the river so that all four arrive safely?
A) Implementation
1) Formalize this problem in a well-defined graph form and present your state and action representations in detail.
2) Run both BFS and DFS algorithms 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 number of move steps on the found solution.
3) The algorithm (BFS or DFS) to be used for search should be chosen by a command line argument as in the given example.
4) When the solution is found, you should print the sequence of moves so that all four arrive safely to the other side of the river.
Your program should compile and run using the following commands:
g++ sourcecode.cpp –o project1 ./project1 bfs ./project1 dfs
Sample Output: The numbers may not reflect the real results. ./project1 dfs Algorithm: DFS Number of the visited nodes: 21 Maximum number of nodes kept in the memory: 9 Running time: 0.34 seconds Solution move count: 9 Farmer Rabbit Carrot Fox || (Farmer, Rabbit, ) Carrot Fox || Farmer Rabbit (Farmer, <) Farmer Carrot Fox || Rabbit (Farmer, Carrot, ) Fox || Farmer Carrot Rabbit … || Farmer Rabbit Carrot Fox
B) Report
1) Present your problem formulation, state and action representations in detail.
2) How does your algorithms work? a) Write your pseudo-code. b) Show complexity of your algorithm on pseudo-code.
3) In Depth-First Search algorithm, why should we maintain a list of discovered nodes?
4) Is the graph constructed by the given problem formulation a bipartite graph? Why or why not? (Implementation is not required for this part.) 5) Analyze and explain the algorithm results in terms of: ● the number of visited nodes ● the maximum number of nodes kept in the memory ● the running time. ● the number of move steps on the found solution.
Note: If you have any questions, please feel free to contact Res. Asst. Çağatay Koç via e-mail (kocca@itu.edu.tr).
Policy: ● You may discuss the problem addressed by the project at an abstract level with your classmates, but you should not share or copy code from your classmates or from the Internet.You should submit your own, individual project. ● Academic dishonesty including but not limited to cheating, plagiarism, collaboration is unacceptable and subject to disciplinary actions.
Submission Instructions: ● Please submit your homework through Ninova e-Learning System. ● You must submit all your source code in a single cpp file and a softcopy report (PDF). You can define multiple classes in a single cpp file. ● All your code must be written in C++, and we must be able to compile and run on it on ITU’s Linux Server (you can access it through SSH) using g++. ● When you write your code, try to follow an object-oriented methodology with well-chosen variable, method, and class names and comments where necessary. ● Your code must compile without any errors; otherwise, you may get a grade of zero on the assignment. ● You should be aware that the Ninova e-Learning System clock may not be synchronized with your computer, watch, or cell phone. Do not e-mail the teaching assistant or the instructors your submission after the Ninova site submission has closed. If you have submitted to Ninova once and want to make any changes to your report, you should do it before the Ninova submission system closes. Your changes will not be accepted by e-mail. Connectivity problems to the Internet or to Ninova in the last few minutes are not valid excuses for being unable to submit. You should not risk leaving your submission to the last few minutes. After uploading to Ninova, check to make sure that your project appears there