COMP30024 Artificial Intelligence
Week 3 Problem Sheet Solutions
• Tutors: These are not unique, complete (and definitely not optimally pedagogical) solutions. there are other ways of deriving these results and the way you prefer is to some extent an aesthetic judgement.
• Students: If you want to attain any benefit from the problems you should make a genuine attempt at them before you see the solutions.
Copyright By PowCoder代写 加微信 powcoder
Comments/corrections are as always greatly appreciated by the teaching team.
1. Toy Graphs [T] In BFS and DFS, an undiscovered node is marked discovered when it is first generated, and marked processed when it has been completely searched. At any given moment, several nodes might simultaneously be in the discovered state.
(a) Describe a graph on n vertices and root v such that Θ(n)1 nodes are simultaneously in the discovered state when conducting BFS starting from v.
A graph of depth 1 where v has n children. (b) Repeat part (a), but for DFS.
A graph of depth n with a single linear branch of children extending from v.
(c) Describe a graph on n vertices and root v such that at some point Θ(n) remain undis-
covered, while Θ(n) nodes have been processed during DFS starting from v.
Multiple answers possible. A graph of depth n/2 with two linear equal-length branches of children extending from v. Note the case in part (b) is not acceptable here as any node along the chain is not marked processed until the recursion returns.
2. Iterative Deepening [T] Recall the iterative deepening search (IDS) strategy from lectures. 1Recall f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)).
(a) Derive the time complexity of iterative deepening search on a graph with branching factor b and minimum goal depth d.
Within each iteration, IDS exhaustively enumerates all nodes up to the current depth. At depth n, the size of this set is bn. Nodes at all levels apart from d are re-generated multiple times – the nodes in the penultimate layer are generated twice, the nodes in the third-last layer are generated three times, and so on, with the root node generated d times. This implies that an upper bound on the number of generated nodes, and hence the time complexity is:
d+(d−1)b+(d−2)b2 +…+2bd−1 +bd =O(bd) So asymptotically approaches BFS.
(b) Can you think of a situation where IDS performs much worse than regular depth-first search?
Consider the situation where the graph is a linear chain with depth d. DFS terminates in d iterations but IDS takes d n = n(n+1) iterations.
(c) BFS and IDS are not optimal in general. State a necessary condition on the cost function
g : paths → R for both methods to be optimal.
Necessary for g to be a non-decreasing function of depth – otherwise the cost of a path from the start to the goal state could be decreased by taking a path with a greater number of actions. This can be formally proved via induction.
3. Connected Components [T] A graph G = (V, E) is connected if a path exists between any two vertices v1,v2 ∈ V. A connected component of a graph is a maximal subset Vc ⊆ V such that there exists a path between any two vertices in Vc. Describe an algorithm, using graph search, that accepts an arbitrary graph G as input and counts the number of connected components of G.
For undirected graphs with a finite state space, BFS/DFS will eventually enumerate all vertices within a connected component, starting at an arbitrary node within the connected component, since the vertex ordering is irrelevant.
• Start at an arbitrary node.
• Run BFS/DFS until the frontier is exhausted – all processed vertices belong to the first
connected component.
• Restart BFS/DFS from an arbitrary undiscovered node until all vertices have been marked processed, counting the number of restarts required.
4. Directed Graphs [T] Your tutor’s job is to arrange n ill-behaved children in a straight line, facing front. They are given a list of m statements of the form ”child i hates child j”. If i hates j, they cannot put i somewhere behind j, because i is then capable of throwing something at j.
(a) They have enlisted your help to design an algorithm which orders the line (or says it is not possible), using depth-first search. Analyze the running time of your algorithm.
• Form a directed graph with the vertices corresponding to children and an edge point- ing from i to j if j hates i (note the reversal!).
• Topologically sort the graph as follows:
– Form a stack which will hold the topologically sorted nodes.
– Perform DFS, and push nodes σ onto the stack only after all descendants of σ in the graph have been fully explored/processed. If there is an edge i → j, this guarantees that i is only pushed onto the stack after j.
– The top node on the stack always has no incoming edges from any vertex in the stack.
– Repeatedly popping nodes off the stack yields a topological ordering where i will always precede j if j hates i.
• Tutors: Please write out pseudo-code illustrating this for your students.
• The time complexity is the same as standard DFS, that is, O(m + n).
Note this algorithm will fail if we have cycles, that is, hate relations of the form i → j → k → i. Topological ordering is only achievable on a directed acyclic graph.
(b) For the class photo, the children must be arranged in rows such that if i hates j, i must be in a lower-numbered row than j, otherwise it is possible for i to drop something on j. Design an efficient algorithm to find the minimum number of rows needed.
Construct the graph as before. The seating position of children not involved in a hate relation are irrelevant (these represent singleton disconnected nodes), so we want to find the height of the connected component of the graph of maximum height. This can be found in O(m + n) time using our strategy for Question 3 using BFS to enumerate all vertices within each connected component.
5. Diameters The diameter of a tree T = (V, E) is defined by ∆= max δ(v1,v2),
where δ(v1, v2) is the number of edges on the path from v1 to v2. Describe an efficient algorithm to compute the diameter of a tree, argue why it is correct intuitively, and describe the running time of your algorithm.
6. Keys and Rooms [C] There are n rooms labeled from 0 to n − 1. All the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, implement an algorithm to determine if you can visit all the rooms.
def dfs_sol(rooms: List[List[int]]) -> bool:
visited = set()
def dfs(room):
visited.add(room)
if len(visited) == len(rooms):
return True
[dfs(key) for key in rooms[room] if key not in visited]
return len(visited) == len(rooms)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com