程序代写代做代考 data structure go C game graph algorithm 3-16. ARTIFICIAL INTELLIGENCE

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