Ask Programming Language Expert

Part A - State Space Search using LISP

This part of the assignment requires you to solve the following problem using the LISP computer programming language:

A merchant has a beaker containing 24 ounces of a precious fluid. He also has empty 5-ounce, 11- ounce, and 13-ounce beakers. How can he divide the fluid into three equal portions?

For this part of the assignment you are required to solve this problem as a state space search problem using the A-star algorithm that has been described in lectures.

You have been supplied with LISP code for A-star search. The code is contained in the file a-star.lisp. You should not make any changes to the code in this file. All the problem-specific code you write should be contained in a file called precious.lisp.

The code in precious.lisp should contain only the following:

  Definition of a global variable *start-state* whose value represents the initial state.

  Definition of a global variable *operators* which lists the names of the operators.

  Definition of a predicate solution-state? that takes a state as argument and returns T if that state is a solution, and nil otherwise.

  Function definitions for each of the operators listed in *operators*.

  Definition of a function cost-of-applying-operator that takes a state and an operator as arguments, and returns the cost of applying the operator to that state. We will assume that all costs are equal, and hence this function should always return 1, irrespective of the state or the operator.

  Definition of a function estimated-distance-from-goal that takes a state as an argument, and returns an estimate of the number of steps required to get from this state to the goal. Note that this function will determine the number of states examined in the search-the fewer the better. You can, of course, write any number of helper functions which are called by the functions above.

Compare the performance of A-star search (using the heuristic you have defined) with the performance of breadth first search. You should compare the number of states examined, the length of the solution and the maximum depth of the search tree. You can obtain this information by examining the value of the variable *stats* after the search has completed.

Notes:
  Using A-star search with a heuristic that evaluates all states as 0 results in a breadth first search. In order to run breadth first search, all you need to do is replace the function estimateddistance- from-goal with the following:

(defun estimated-distance-from-goal (state) 0)

  Don't forget to reset the value of *stats* before running the search again.

Write a short report on your findings (approx. 150 words). The report should contain a table that compares the number of states examined, the length of the solution, and the maximum depth of the search tree.

Part B - State Space Search using Prolog

This part of the assignment requires you to solve the following problem using the Prolog computer programming language:

Ten cannibals and ten missionaries come to the left bank of a crocodile infested river, where there is a boat that can be used by one or two persons. There is an island in the middle of the river. If cannibals outnumber the missionaries at any time, the cannibals eat the missionaries. How can they use the boat to cross the river so that all missionaries survive? All trips must be either to or from the island; i.e., crossings directly from bank to bank are not allowed.

For this part of the assignment you are required to solve this problem as a state space search problem using the best-first-search algorithm.

You have been supplied with two Prolog files: adts.pl and bfs.pl. The file adts.pl contains Prolog code implementing various abstract data types. The file bfs.pl contains code that can be used to perform bestfirst- search in Prolog. Note that the file bfs.pl consults adts.pl.

For this task you are required to write Prolog code to solve the missionaries and cannibals problem. To assist you, two example files have been made available on the LMS: fwgc.pl and jugs.pl, which implement the farmer, wolf, goat and cabbage problem, and the water jugs problem, respectively. Note that these files contain all of the code in bfs.pl, in addition to the problem-specific operators, coded in a procedure move(Current_State, Next_State). It is suggested that you study the code in these files before commencing your solution to the missionaries and cannibals problem.

In addition to outputting the sequence of steps required to move from the start state to the goal state, your code should also show the total number of states examined (i.e., the sum of the number of states on the Open and Closed lists), the maximum depth of the search tree, and the length of the solution. All code (with the exception of code in the file adts.pl) should be contained in a file called mc.pl.
Procedures that you will need to include in mc.pl are:

  A procedure move(Current_State, Next_State) that described the problem solving operator for moving from Current_State to Next_State .

  A procedure heuristic(State, Goal, H) where state is the state being evaluated, Goal is the goal state, and H is the heuristic evaluation for state. (Note that bfs.pl contains the procedure heuristic(State, Goal, 0).

This assigns a H value of 0 to every state, and thus results in breadth first search. You should replace this with a procedure that implements your proposed heuristic).

  Procedures to find the the total number of states on the Open and Closed lists, the maximum depth of the search tree, and the length of the solution.

  Any helper procedures required. (For example, you may wish to write a procedure unsafe(State) that returns False if state State is unsafe (i.e., if the number of cannibals at any location outnumber the number of missionaries at that location).

Compare the performance of A-star search (using the heuristic you have defined) with the performance of breadth first search. You should compare the number of states examined, the length of the solution and the maximum depth of the search tree.

Write a short report on your findings. The report should contain a table that compares the number of states 

Programming Language, Programming

  • Category:- Programming Language
  • Reference No.:- M9740667

Have any Question?


Related Questions in Programming Language

Assignment - haskell program for regular expression

Assignment - Haskell Program for Regular Expression Matching Your assignment is to modify the slowgrep.hs Haskell program presented in class and the online notes, according to the instructions below. You may carry out th ...

Assignment task -q1 a the fibonacci numbers are the numbers

Assignment Task - Q1. (a) The Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and are characterised by the fact that every number after the first two is the sum of the ...

Question - create a microsoft word macro using vba visual

Question - Create a Microsoft Word macro using VBA (Visual Basic for Applications). Name the macro "highlight." The macro should highlight every third line of text in a document. (Imagine creating highlighting that will ...

Assignmentquestion onegiving the following code snippet

Assignment Question One Giving the following code snippet. What kind of errors you will get and how can you correct it. A. public class HelloJava { public static void main(String args[]) { int x=10; int y=2; System.out.p ...

Assignment - proposal literature review research method1

Assignment - Proposal, Literature Review, Research Method 1. Abstract - Summary of the knowledge gap: problems of the existing research - Aim of the research, summary of what this project is to achieve - Summary of the a ...

1 write a function named check that has three parameters

1. Write a function named check () that has three parameters. The first parameter should accept an integer number, andthe second and third parameters should accept a double-precision number. The function body should just ...

Assignment - horse race meetingthe assignment will assess

Assignment - Horse Race Meeting The Assignment will assess competencies for ICTPRG524 Develop high level object-oriented class specifications. Summary The assignment is to design the classes that are necessary for the ad ...

Task silly name testeroverviewcontrol flow allows us to

Task: Silly Name Tester Overview Control flow allows us to alter the order in which our programs execute. Building on our knowledge of variables, we can now use control flow to create programs that perform more than just ...

Structs and enumsoverviewin this task you will create a

Structs and Enums Overview In this task you will create a knight database to help Camelot keep track of all of their knights. Instructions Lets get started. 1. What the topic 5 videos, these will guide you through buildi ...

Task working with arraysoverviewin this task you will

Task: Working with Arrays Overview In this task you will create a simple program which will create and work with an array of strings. This array will then be populated with values, printed out to the console, and then, w ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As