COMP30024 Artificial Intelligence
Week 3 Problem Sheet
Weekly Topic Review
Recall that graph search is the problem of selecting action sequences on a graph to achieve a goal state in environments that are deterministic, observable, and static with a completely specified state space. This tutorial we will be working with uninformed search methods – these are limited to taking actions and performing a goal test, and do not have access to any further domain knowledge. This sheet and future tutorials will assume familiarity with basic notions of graph theory.
Copyright By PowCoder代写 加微信 powcoder
In lectures you saw multiple uninformed search strategies, we will briefly describe 3 below. In what follows let b denote the branching factor of the graph, and d the depth of the shallowest goal state.
• Breadth-first search (BFS) expands the shallowest unexpanded node, and hence maintains a FIFO queue for the frontier (i.e. the set of unexpanded visited nodes). BFS systematically explores the search space and is therefore complete (provided the state space is finite), but not optimal in general. Both the space and time complexity are O(bd), due to exhaustive enumeration of states.
• Depth-first search (DFS) expands the most recently generated node first, and hence may be considered to maintain a LIFO queue for the frontier. It fails to systematically explore the search space on indefinitely large graphs, but will eventually explore the finite space on acyclic finite graphs. For this reason it is neither complete nor optimal (as it returns the first goal state found, not guaranteed to be that of minimal cost). The time complexity is identical to BFS, but the space complexity is linear in b: O(bm), where m is the maximum depth of the tree – this comes about as we need to keep track of potential successors for each state lying on our current path through the graph.
• Iterative deepening search (IDS) combines the best parts of BFS and DFS, iteratively per- forming DFS until the goal state is found (or it reaches some maximum depth limit). The same caveats for optimality from BFS apply here. Unlike DFS, IDS is optimal on finite acyclic graphs. The space complexity of IDS is identical to DFS, and you will derive the time complexity below (spoiler: it is asymptotically identical to BFS).
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.
(b) Repeat part (a), but for DFS.
(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.
2. Iterative Deepening [T] Recall the iterative deepening search (IDS) strategy from lectures.
(a) Derive the time complexity of iterative deepening search on a graph with branching factor b and minimum goal depth d.
(b) Can you think of a situation where IDS performs much worse than regular depth-first search?
(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.
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 an undirected 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 undirected graph G as input and counts the number of connected components of G.
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. Formulate this problem as a graph algorithm and analyze its running time.
(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.
5. Diameters The diameter of a tree T = (V, E) is defined by ∆= max δ(v1,v2),
v1 ,v2 ∈V 1Recall f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)).
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. Hint: this is similar in spirit to question 2.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com