关于算法:COMPSCI-367问题解答

School of Computer ScienceCOMPSCI 367 Assignment 2 due 8 October 2023
Due: by 11:59pm on the due date. Late assignments will not be marked.
Total mark: 15.Worth: This assignment counts towards 15% of your final mark.Please answer ALL questions. Submit the answer to Question 1 as a pdf file Q1.pdf. Submitthe answers to Question 2 and Question 3 as Prolog code, i.e., .pl files, as mapcolouring.pland surround.pl, respectively.

Q1.

Suppose you are building a decision support system that helps people with investment options. The system assumes that the user has some money to invest and can help selectamong the following possibilities:

• an income fund
• a growth fund
• a conservative fund

You will build a simple knowledge base, consisting of a set of rules written below (in a slightlyabbreviated form). Each rule is written as an implication, expressed in terms of an if part (thepremise) and a then part (the conclusion). The conclusion conservative, income, growthare the three fund possibilities.For example, rule (3) delivers the following message:“If you are retired and you havebasicinsurance coverage, then the category of fund to select is the income fund”.

(1) if have health insurance and have life insurance then basic insurance coverage
(2) if investment for retirement and basic insurance coverage then conservative
(3) if retired and basic insurance coverage
then income
(4) if investment for children education and basic insurance coverage then growth
(5) if investment for home ownership and basic insurance coveragethen growth
(6) if age≤65 then not retired COMPSCI 367 Assignment 2 Page 1 of 4
(7) if age>65 then retired
(8) if not retired and no pensionthen investment for retirement
(9) if have children and children’s education not funded then investment for children education
(10) if no home ownership and want home
then investment for home ownershipAnswer the following questions and write down the solutions in Q1.pdf file. Clearly indicatethe solutions to (a) and (b):

(a) [2 marks] Design a definite clause knowledge base using the information above. Clearlylist the atomic propositions (with their intended meaning) and the clauses in the KB. Anexample that contains a few atomic propositions and a rule is given below:Example. Atomic propositions:

• BasInsure: The user has basic insurance cover
• HeaInsure: The user has health insurance
• LifInsure: The user has life insurance

Clause (1): BasInsure ← HeaInsure ∧ LifInsure(b) [3 marks] Suppose a user has the following information:

(11) is 42 years old
(12) has health insurance, and (13) life insurance
(14) not covered by a pension plan
(15) has one child, age 12, who (16) does not have funding for education
(17) does not currently own a house and (18) would like to own one.Apply SLD resolution on the three queriesi. ask conservativeii. ask incomeiii. ask growth

For each case, provide a proof if the answer is true, and answer why if the answer is false.

Q2

Solve the map colouring problem for North Island using Prolog. Up to three colours,red, green, blue, are allowed to use. Two adjacent regions cannot be marked with the samecolour.You may use the following knowledge base:

• different(red, green).
• different(red, blue).
• different(green, blue).

COMPSCI 367 Assignment 2 Page 2 of 4

• different(green, red).
• different(blue, red).
• different(blue, green).

Implement a Prolog predicate mapcolouring(N,A,WA,B,G,T,M,H,WE) where a variable shouldbe the corresponding word as indicated in the following map. Submit your answer asmapcolouring.pl file.

Q3

Given is a 4 × 4 board with each grid marked with either“+”or“−”. The goQGiven is a 4 × 4 board with each grid marked with either“+”or“−”. The goalis to find all − grids that are surrounded by +. A − grid at the edge cannot be surrounded.More formally, each grid can have up to 4 neighbour grids, i.e., top, bottom, left and right. Ifone grid or a group of“−”grids forms a“connected”area and their neighbours are all“+”grids, then all“−”grids in this group are surrounded. Otherwise, if any a − grid in that grouphas a − neighbourthat is at the edge, then all neg grids in this group are nonsurrounded. Forexample, in figure (a), the − grids highlighted in red are surrounded; in figure (b), no − gridis surrounded.Use theconstants g11, g12, . . . , g44 to denote the coordinates of grids. Use the rules neg(G)and pos(G) to denote a grid marked with − and +,respectively, where the variable G ∈ {g11,g12, . . . , g44}.You are requested to: Build a knowledge base and implement a Prolog predicateis surrounded (G) such that is surrounded (G) is true if G is a − grid and is surrounded by + grids, and false otherwise. Youare allowed to define any additional and auxiliaryrules.COMPSCI 367 Assignment 2 Page 3 of 4Evaluation. Your programme may be testedusing different configurations of the board. ForThe configuration code will be added at the top of the knowledge base when testing.Submit your answer as surround.pl file.COMPSCI 367 Assignment 2 Page 4 of 4