In class and with the lab we saw how a single function can perform many tasks as long as that function contains the general structure that is needed by several tasks. The main example given in the lab was the reduce function that could sum, multiply, or, or do any number of other specific tasks on a list structure. Search on a tree structure can be looked at in a similar manner: there's one specific function used to get the next item and see if it's a match. The difference between breadth-first and depth-first search is in how the nodes to be searched are ordered. In breadth-first search, nodes are ordered as a queue and in depth-first search they are ordered as a stack. This doesn't just work for breadth- and depth- first search, but can be extended to algorithms like A* where the nodes are ordered as a priority queue.
The goals of this homework are the following:
Download the definitions file. This file contains structures for a problem and a node as well as a couple of helpful functions if you choose to consider a queue as a list of nodes. You'll need to write a function for the general search routine and put it in a file called search.lisp. This function should have the following definition and arguments:
(defun general-search (my-problem queuing-fn q-lst) )
my-problem is of type problem, the queuing-fn is the function to use for determining which nodes to search first (think of it as a function that will put nodes on the front of a list for a stack and on the back for a queue, etc.), and q-lst is a convenient way to keep track of the list of nodes to be searched when doing recursion. The q-lst is the list of nodes that remain to be search in your current depth/breadth of the tree because you can only search one at a time. Speaking of which, your solution should be recursive and you'll probably want to compile it to make it run faster. The move function that goes in the problem structure is what will expand your tree as it will generate all next moves from the current move in the tree.
The general-search function should return nil if an answer is not found in the search. Otherwise, it should return the node of the answer. To fix the problem with running into a potential infinite loop with depth-first search, you are allowed to change your move function to quit generating moves beyond a specific depth. Note that this is not the same thing as a true limited depth-first search, but it will work for this assignment.
Hint: Remember that you can call a function that's passed in with either apply or funcall.
Write functions the use the general search for depth-first and breadth-first search. Both functions should take a single argument: my-problem or type problem and both should go in the search.lisp file.
You really need some way to test your algorithms and the problem should have relatively few states and be easy to program. We highly recommend solving the eight puzzle (see the sample problem definition in the given definitions file). Use your problem as a test of your code and submit it in a separate file. You are allowed to limit the move function in the problem so that it doesn't consider nodes below a specific depth. This will keep the problem from running infinitely for depth-first search.
You will be using Wtry to submit your project. For this particular homework there are 2-3 submissions:
You can resubmit
as often as you like before the deadline. WTry will be open for the
grace period after the deadline and you will receive 10% off for every day after the submission deadline, even if your project is only 2 minutes after the deadline.