AI Assignment 3

Artificial Intelligence Assignment No.
ASSIGNMENT NO. 3: PROBLEM SOLVING TECHNIQUES

Assignment
Subject: Artificial Intelligence Assigned: April 25, 2022
Marks: 80
Instructor: M.Siddique Due Date: June 1, 2022 Class : BSCS-
6C
OBJECTIVES:
The objective of this assignment is to give you some practice regarding:
Problem Representation
Components of Problem Solving
Search Strategies
INSTRUCTIONS:
Please read the following instructions before attempting to solve this assignment
1. This is an individual assignment. You will submit your work individually through your
logins. Also submit hardcopy of the assignment.
2. Write your name and roll number at the start of the assignment.
3- You should concern recommended books for clarify your concepts, as handouts are not
sufficient.
4. Try to make solution by yourself and protect your work from other students. If I found the
solution files of some students are same then I will reward zero marks to all those students.
5. Deadline for this assignment is (Friday) June 3, 2022. This deadline will not be extended.
Question No. 1 Marks = 5
In the farmer-fox-goose-grain puzzle, a farmer wishes to cross a river taking his fox, goose, and
grain with him. He can use a boat which will accommodate only the farmer and one possession.
If the fox is left alone with the goose, the goose will be eaten. If the goose is left alone with the
grain it will be eaten.
a) Set up a state-space search formulation of the farmer-fox-goose-grain puzzle:
i. Clearly identify the four components of problem solving in the above puzzle
a. problem statement
b. Name the operators on states and give precise description of what each operator
does to a state description
c. solution space
d. Goal state.
b) Draw a state space search tree for this puzzle using 0 and 1 to left and right river bank
respectively.
c) How many journeys will be taken to cross the river
In the water-jug-puzzle, we are given a 3-liter jug, named Three, and a 4-liter jug, named Four.
Initially, Three and Four are empty. Either jug can be filled with water from a tape, T, and we can
discard water from either jug down a drain, D. Water may be poured from one jug into the other.
There is no additional measuring device. We want to find a set of operations that will leave
precisely two liters of water in Four
i. Clearly identify the four components of problem solving in the above puzzle
BIMS 1
Artificial Intelligence Assignment No. 3
c. solution space
d. Goal state.
b) Draw a graph of all the distinct state-space nodes that are within three moves of the stat
node, label each node by its state description, and show at least one path to each node in
the graph- labeling each arc by the name of the appropriate operators. In addition these
nodes, show also all of the nodes and arc(properly labeled) on a path to the solution.
There are four people who want to cross a bridge; they all begin on the same side. You have 17
minutes to get them all across to the other side. It is night, and they have one flashlight. A
maximum of two people can cross the bridge at one time. Any party that crosses, either one or
two people, must have the flashlight with them. The flashlight must be walked back and forth; it
cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2
minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at
the rate of the slower person’s pace. For example, if person 1 and person 4 walk across first, 10
minutes have elapsed when they get to the other side of the bridge. If person 4 returns the
flashlight, a total of 20 minutes have passed and you have failed the mission.
ii. Clearly identify the four components of problem solving in the above puzzle
c. solution space
d. Goal state.
b) Draw a state space search tree for this puzzle using 0 and 1 to left and right river bank
respectively.
c) How many journeys will be taken to cross the river
The Königsberg bridge puzzle is universally accepted as the problem that gave birth to graph
theory. It was solved by the great Swiss-born mathematician Leonhard Euler (1707—1783). The
problem asked whether one could, in a single stroll, cross all seven bridges of the city of
Königsberg exactly once and return to a starting point. Following is a sketch of the river with its
two islands and seven bridges:
a) State the problem as a graph problem.

b) Does this problem have a solution? If you believe it does, draw such a stroll; if you believe
it does not, explain why and indicate the smallest number of new bridges that would be
required to make such a stroll possible.
BIMS 2
A century after Euler’s discovery (see Problem 4), another famous puzzle–this one invented by
the renown Irish Mathematician Sir William Hamilton (1805-1865)–was presented to the world
under the name of the Icosian Game. The game was played on a circular wooden board on which
the following graph was carved:
Find a Hamiltonian circuit–a path that visits all the graph’s vertices exactly once before returning
to the starting vertex–for this graph.
Consider the following map:
a) Explain how we can use the graph-coloring problem to color the map so that no two
neighboring regions are colored the same.
b) Use your answer to part (a) to color the map with the smallest number of colors.
Give the initial state, goal state, successor function (transition function)/ operators for each of the
following. Choose a formulation (problem representation) that is precise enough to be
implemented.
a) A 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot
ceiling. He would like to get the bananas. The room contains two stackable, moveable,
climbable 3-foot-high crates.
b) You have a program that outputs the message “illegal input record” when fed a certain
file of input records. You know that processing of each record is independent of other
records. You want to discover what record is illegal.
BIMS 3

Examine the AI literature to discover whether the following tasks can currently be solved by
computers: For the currently infeasible tasks, try to find out what the difficulties are:
a. Playing a decent game of table tennis (ping-pong).
b. Driving in the center of Cairo.
c. Buying a week's worth of groceries at the market.
d. Buying a week's worth of groceries on the web.
e. Playing a decent game of bridge at a competitive level.
f. Discovering and proving new mathematical theorems.
g. Writing an intentionally funny story.
h. Giving competent legal advice in a specialized area of law.
i. Translating spoken English into spoken French in real time.
j. Performing a complex surgical operation.
a) "Surely computers cannot be intelligent-they can do only what their programmers tell
them." Is the latter statement true, and does it imply the former?
b) "Surely animals cannot be intelligent-they can do only what their genes tell them." Is
the latter statement true, and does it imply the former?
c) "Surely animals, humans, and computers cannot be intelligent-they can do only what
their constituent atoms are told to do by the laws of physics." Is the latter statement true,
and does it imply the former?
BIMS 4

AI Assignment 3

Uploaded by

Copyright:

Available Formats

AI Assignment 3

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

AI Assignment 3

Uploaded by

Copyright:

Available Formats

Artificial Intelligence Assignment No.

ASSIGNMENT NO. 3: PROBLEM SOLVING TECHNIQUES

a) State the problem as a graph problem.

Question No. 8 Marks = 20

You might also like