3-16. ARTIFICIAL INTELLIGENCE
1. A Binary Search Tree (BST) is a particular type of dynamic data structure that uses a key for search and storage of data items. These keys are kept in sorted order.
Each node of a BST stores a unique key (e.g. an integer) and (optionally) a value asso- ciated with that key; and has two edges pointing away from it, one for the left sub-tree, and one for the right sub-tree:
node:Key
Left Right
The invariant property of a BST is in-order traversal, meaning that:
• The key stored in each node must be greater than or equal to any key stored in
its Left sub-tree;
• The key stored in each node must be less than or equal to any key stored in its
Right sub-tree;
i.e., ∀k ∈ Left.k < Key ∧ ∀k ∈ Right.Key < k (i.e. no duplicates).
This question explores how Prolog can be used to represent a BST and perform specific operations on it.
a) Define a Prolog representation for an empty, and a non-empty BST.
b) Define a predicate lookup(+Key, +BST) which is true if key Key can be found
in binary search tree BST.
[4]
c) Define a predicate insert(+Key, +BST1, ?BST2) which returns true if bi- nary search tree BST2 is the same as binary search tree BST1 but with key Key inserted.
[4]
d) Define a predicate delete(+Key, +BST1, ?BST2) which returns true if bi- nary search tree BST2 is the same as binary search tree BST1 but with key Key deleted. Explain what happens if the key is not found in the tree.
[4]
e) Define a predicate verify(+BT) which succeeds if binary tree BT satisfies the invariant property of in-order traversal (i.e. is a BST).
[4]
Note: the next page has additional information on the algorithms for delete and verify.
3-16. Artificial Intelligence ⃝c Imperial College London 1/6
[4]
Delete
The action of:
• Deleting a node from an empty tree returns the empty tree;
• Deleting a node with empty sub-trees returns the empty tree;
• Deleting a node with one empty sub-tree returns the non-empty sub-tree.
To delete a node with two non-empty sub-trees:
• Get the in-order successor to the node from its right sub-tree; • Replace this node’s key with the successor key;
• Delete the successor-node from the sub-tree!
To find the in-order successor, look for the leftmost node with an empty left sub-tree.
Verify
In a BST, the set of possible keys is a complete order, with a minimum value MinKey and a maximum value MaxKey.
Therefore, the key stored in every node must be greater than or equal to MinKey and less than or equal to MaxKey.
Then:
1. From the root node with key RootKey:
• For every key Key in the Left subtree: MinKey ≤ Key < RootKey; • For every key Key in the Right subtree: RootKey < Key ≤ MaxKey.
2. From the root of the Left subtree with key LKey:
• For every key Key in its Left subtree: MinKey ≤ Key < LKey;
• For every key Key in its Right subtree: LKey < Key ≤ RootKey.
3. From the root of the Right subtree with key RKey... And so on...
3-16. Artificial Intelligence ⃝c Imperial College London 2/6
2. The Missionaries and Cannibals Problem (Variation 1). Three devout missionaries are on one bank of a wide river with three hungry cannibals, and they all want to cross the river to get to the other bank. They are restricted, however, by the following conditions:
• None of them dare swim, for there are crocodiles in the river;
• There is only one rowing boat with one set of oars;
• At most two (2) people can ride in the boat for each crossing;
• All missionaries are, but only one cannibal is, able to row the boat;
• Unless there are no missionaries, there must never be fewer missionaries than
cannibals on either bank, otherwise the cannibals will eat the missionaries.
a) Give a state space formulation that could be used with the General Graph Search Engine (GGSE). Specify the initial state and the goal state.
[3]
b) Define a relation (predicate) movable(Bank, Rowers) which is true if Rowers is a permissible combination of rowers given the missionaries and cannibals who are on the bank Bank.
[3]
c) Define a relation (predicate) satisfiable(Bank) which is true if Bank satis- fies the constraints on the number of missionaries and cannibals on a bank.
[3]
d) Hence define a single state-change rule that could be used by the GGSE to compute all the state changes (new states) from an old state. Explain why this depends on the definition of movable/2.
[3]
e) Explain how the Iterative Deepening Depth-First search algorithm works.
Explain how the basic GGSE could be modified to implement this algorithm.
Evaluate, with justification, the Iterative Deepening Depth-First search algo- rithm with respect to appropriate criteria.
Comment on the suitability of this algorithm for solving the Missionaries and Cannibals Problem (Variation 1).
[8]
3-16. Artificial Intelligence ⃝c Imperial College London
3/6
3. a)
b)
c)
d)
In the context of the A* search algorithm, define the terms heuristic and admis- sible heuristic.
Explain why admissibility is essential to the A* search algorithm.
[4]
In the context of the A* search algorithm, discuss the criteria that might be used to choose which heuristic (or heuristics) are implemented, when there is more than one possible option.
[4]
Given the specification of a graph GS = ⟨S, Op⟩, give an inductive definition of the paths of the graph, and explain how the A* search algorithm explores the paths defined in this way.
[4]
In the context of the AlphaBeta algorithm for 2-player games, consider the following tree:
MAX
MIN
MAX
B XYZ?
e)
Explain what happens to branch B, assuming: firstly that X < Y and X > Z; and secondlythatX