This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get all the help you need from the TAs or the instructor. You are encouraged to use the WebCT Discussions page to post problems so that other students can also answer/see the answers.
The goal of this assignment is to implement a generic
predicate call_bfs that attempts to
satisfy goals breadth-first-search
rather than using Prolog's depth-first search strategy. Use your generic
predicate to find solutions to at least one of the following problems Missionaries
and Cannibals and The
Knight's Tour.
Here is a simple example demonstrating how call_bfs(G) is different from call(G):
If we have a graph and paths as defined by the code below:
link(g,h).link(g,d).link(e,d).link(h,f).link(e,f).link(a,e).link(a,b).link(b,f).link(b,c).link(f,c).
go(X,X,[X]).
go(X,Y,[X|T]):-
link(X,Z),
go(Z,Y,T).
And
suppose your goal is to find all the paths from a to c, denoted by go(a,c,X), call_bfs(go(a,c,X))
will get the following results:
X
= [a,b,c] ;
X = [a,e,f,c] ;
X = [a,b,f,c] ;
no
rather than
X
= [a,e,f,c] ;
X = [a,b,f,c] ;
X = [a,b,c] ;
no
Implement a generic best-first search algorithm.
Reference:
Prolog Tutorial 2 Be sure to read 3.3 Meta-interpreters in Prolog
Due Date:
|
Received Time |
Grade Modification |
|
before Monday, 11/28, 11:59PM |
+10% |
|
before Tuesday, 11/29, 11:59PM |
no modification (on time) |
|
before Wednesday, 11/30, 11:59PM |
-10% |
|
from Thursday, 11/31, 12:00AM to |
-25% |
|
after Saturday, 12/1, 12:00AM |
not accepted |
Grading: The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor (comment, comment, comment!). See the professor or TAs, if you have ideas for other extensions for this assignment and would like extra credit for implementing them.
Submission Requirements: Please submit a ZIP file with your code, including a README file. In the README file, place the names of each group member (up to two). Your README file should also have a list of specific features / bugs in your solution. Your ZIP file should be named with your WebCT user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair via WebCT.