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 help from the TAs or the instructor. You are encouraged to use the RPILMS 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 using 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
Note: We will use SWI-Prolog
in this assignment. If you have problems compiling sample code from online tutorials, please
pay attention to syntactic differences among Prolog implementations, such as using "=<" instead of
"<=".
Due Date:
|
Received Time |
Grade Modification |
|
before Saturday, 09/19, 11:59PM |
+10% |
|
before Monday, 09/21, 11:59PM |
no modification (on time) |
|
before Tuesday, 09/22, 11:59PM |
-10% |
|
from Wednesday, 09/23, 0:00AM to |
-25% |
|
after Friday, 09/25, 0: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 RPILMS user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair via RPILMS.