|
(a)Describe, using examples, the two
blind state-space search techniques.
[6 marks ]
In each case:
one mark should be awarded for naming the search; one mark should
be awarded for a satisfactory elaboration; and one mark should be
awarded for good, illustrative example.
•Breadth-first search (1 mark).This involves searching a tree
level by level
(1 mark).
•Depth-first search (1 mark).This involves searching a tree along
one path until a goal, a dead end, or a path already travelled is
reached (1 mark).
[6 marks ]
(b)List two advantages of using a heuristic
search, as opposed to a blind state-space search.[2 marks ]
One mark should be awarded for each advantage named (up to a maximum
of two marks). Examples include the following:
•It improves the efficiency of the search process by sacrificing
claims of
completeness (1 mark).
•It is more economical than a blind search (1 mark).
Other valid answers should also receive credit. [2 marks ]
(c)List three points at which heuristic
information can be applied in a search.[3 marks]
One mark should be awarded for each valid point (up to a maximum of
three marks). Examples include the following:
•Deciding which node to expand next.
•Deciding which successor o successors to generate.
•Deciding which nodes should be discarded.
Other valid answers should also receive credit.
[3 marks ]
(d)Give one example of each of the following types of information:
(i)Objects.[1 mark ]
(ii)Events.[1 mark ]
(iii)Performance.[1 mark ]
(iv)Meta knowledge.[1 mark ]
(i)Any acceptable example should receive credit, e.g., “birds
have wings.” [1 mark ]
(ii)Any acceptable example should receive credit, e.g., “it will
rain tomorrow.” [1 mark ]
(iii)Any acceptable example should receive credit, e.g., composing
sentences. [1 mark ]
(iv)Any acceptable example should receive credit, e.g., the level
of expertise in a particular domain. [1 mark ]
|