PROJECT TWO: comparison of alternative search algorithms (using The 15 Puzzle) Here is your FIRST Problem-Solving assignment. Its is due a little more than two weeks from today. I hope you find this not only straightforward, but quite a bit of fun as well! But yes there is a bit of grunt work to do in setting up your experimental facility: The intent of this assignment is to help demonstrate to you the expense of the various search algorithms we've been discussing, and the benefits that KNOWLEDGE accrues when solving problems. We started with BFS and DFS, which are called "WEAK" methods, since they search without much problem specific knowledge available to them. We discussed Uniform Cost Search that added a cost model to our search to allow us to seek minimal cost solutions. Shortly we'll add heuristic knowledge to our problem-solver in developing the A* algorithm. Each additional bit of knowledge and structure should improve performance, i.e. searching should take less time (fewer states generated and explored) in computing solutions. So, this is your assignment: 1-Fully implement the BFS and DFS search algorithms. 2-Fully implement the Uniform Cost Search Algorithm by modifying that code (simply copy the code of the search alg. and modify it accordingly, including the definition of a node. 3-Fully implement the Iterative Deepening DFS algorithm. At this point, you should have 4 search algorithms coded and ready to be used, but first, we'll add yet another SMARTER algorithm. 4-Fully implement the Greedy and A* algorithms (which will be discussed in class with you next week, in plenty of time to complete the project.) Do this by modifying the uniform cost search code by adding additional info to a node, another access function, and a call in the appropriate place to a heuristic evaluation function. 5-INSTRUMENT each of the 6 algorithms you've coded to produce basic statistics: a)the number of nodes generated b)the number of nodes containing states that were generated previously c)the number of nodes on the OPEN list when termination occurs d)the number of nodes on the CLOSED list (if there is one) when termination occurs 6-Fully implement the 15 PUZZLE (its the 4 by 4 version of the 8 PUZZLE, with tiles numbered from 1 to 15, rather than 1 to 8). The same operators defined for the 8 PUZZLE should work, but of course the state representation must change. The "success" function should be written to allow an optional flag to control whether or not a solution is printed, or the statistics gathered in 4, or both. (Ughhh, more grunt work.) 7-Now, here is the fun part. You must also define TWO Heuristic evaluation functions, one based upon the function described in class on the 8 Puzzle, and another function OF YOUR OWN CHOICE. These Heuristic Evaluation functions are to be used by the A* and Greedy algorithms previously implemented in step 4. 8-Finally, run all of the above on at least three test cases: a)a hard 15 puzzle (meaning a starting position that requires at least 15 moves) b)a moderately hard puzzle (meaning a starting position with at least 8 moves) and c) a trivial puzzle (meaning a starting position with at least 3 moves). This means that starting with each of the three puzzles, you should run a)BFS and generate solutions and statistics b)DFS and likewise generate solutions and statistics, taking care to run this one repeatedly for different depth bounds c)Likewise with iterative deepening d)Likewise with Uniform Cost Search with the cost function defined as simply ONE and generate solutions and statistics f)Greedy and A* with inclass heuristic function and generate solutions and statistics g)Greedy and A* with your very own heuristic function generate solutions and statistics WE WILL BE SENDING TEST PUZZLES FOR YOU TWO DAYS BEFORE IT IS DUE! And that's all folks! sal SOME MORE FOOD FOR THOUGHT: You might find it very interesting to run your test cases for each of the algorithms under different ORDERINGS of the operators! This means, that running BFS and DFS multiple times for the same starting state but with different orderings of operators (i.e. the successor function implements North/East/South/West, then North/South/East/West, then North/West/East/South, and so forth) will likely produce different results! Hmmmmm..... Will alternative orderings make a difference in Uniform Cost Search? Greedy? A*? In BFS? In DFS? Interesting question, isn't it?