COMP3308/3608 Artificial Intelligence
Week 2 Tutorial exercises
Search Problem Formulation. Uninformed Search. Informed Search: Greedy.
Updated: 6/3/2022
Copyright By PowCoder代写 加微信 powcoder
Welcome to your first AI tutorial! Please note the following:
• The tutorial notes typically include more exercises than what we can do in the 1-hour tutorial. We will do only some of them in class, but you need to do the remaining at your own time. The exercises are very useful to help you understand the material, that’s why we have prepared more. We will provide the solutions to all of them (at 6pm on Wednesday, after the last tutorial).
• The homework for this week includes Exercise 1. The homework exercises are marked with “(Homework)”. Usually only 1 exercise is given for homework.
• The homework exercises for the regular and advanced stream are typically the same, unless otherwise specified.
• A reminder about how to submit the homework: via the submission box in Canvas, due on Tuesday 4pm every week.
Exercise 1. Uninformed search (Homework)
Given is the tree below, where the tree branches are labeled with their cost. List the order in which the nodes are expanded using the following search strategies:
a) Breadth-First Search (BFS);
b) Uniform Cost Search (UCS) – when there is a tie, i.e. more than 1 candidate with the same cost,
expand first the left-most node as shown on the figure.
c) Depth-First Search (DFS)
d) Iterative-Deepening Search (IDS).
Assume that none of the nodes are goal nodes, i.e. show the traversal of the whole tree using the search strategies.
a) BFS Expanded:
b) UCS Expanded:
COMP3308/3608 Artificial Intelligence, s1 2022
c) DFS Expanded:
d) IDS Expanded:
Exercise 2. Uninformed search
The same questions as in the previous exercise but for the following tree:
a) BFS Expanded:
b) UCS Expanded:
c) DFS Expanded:
d) IDS Expanded:
34 10 11 12 13
Exercise 3. Greedy search
Consider the tree below. The step costs are indicated along the edges and the heuristic values h are shown in brackets. The goal nodes are circled twice, i.e. they are C, I, E and K. Run the greedy search algorithm. Show the list of expanded nodes and the solution path found with its cost. If there are nodes with the same priority for expansion, expand the last added first.
COMP3308/3608 Artificial Intelligence, s1 2022
Expanded nodes: Path found:
Path cost:
Exercise 4. IDS
Consider the following tree where O is the goal. (Ignore the different type of node outlines). The branching factor is b=2, the depth of the solution is d=3. Run IDS and check that the number of expanded nodes to find the solution is:
1(d+1)+b1d+b2(d-1)+…+bd1= 1(d+1) + b1d + b2(d-1) + b31
Updated: 6/3/2022
Exercise 5. The n-rooks problem
Given is a n x n board and the following task: starting with an empty board, put one rook at the left-most column on a square that is not attacked by any other rook. A rook attacks another rook horizontally or vertically.
Show that the state space has n! states there are n! goal states.
Exercise 6. The n-queens problem (Advanced students only)
Consider the n-queens problem using the efficient incremental formulation from the lectures. Recall that it starts with empty n x n board and at each step puts one queen at the left-most column on a square that
is not attacked by any other queen. Show that the state space has at least 3 n! states.
Hint: Consider the maximum number of squares that a queen can attack in the following column and then
derive a lower bound for the number of states.
Exercise 7. (Advanced students only)
A robot must find the shortest path between a starting point s and a goal point g in the two-dimensional space populated by polygonal obstacles shown below. The path can be adjacent to (touching) the obstacles, but cannot intersect any of them. Assume the robot is of infinitesimal size.
COMP3308/3608 Artificial Intelligence, s1 2022
a) Draw the shortest path from s to g.
b) Although there are an infinite number of points in this two dimensional space, what is the minimal set of points that must be considered in searching for a shortest path between an arbitrary s point and an arbitrary g point?
c) Given one of the points in the minimal set you just found, describe a method for generating the successors of this point in the corresponding search graph. What are the successor points for point s in the figure?
Additional exercises (to be done at your own time)
Exercise 8. Missionary and cannibals
Three missionaries and three cannibals come to a river. There is a boat on their side of the river that can be used by either one or two persons. How should they use this boat to cross the river in such a way that cannibals never outnumber missionaries on either side of the river?
a) Design and describe an appropriate representation for a state in this search problem.
b) Under your chosen representation, what are the initial and goal states?
c) Draw the graph of the states and label its nodes. Include only those states that are “legal”, i.e. states in which the cannibals do not outperform missionaries on either side of the river.
d) Why do you think people have a hard time solving this puzzle, give than the state space is so simple?
Exercise 9. Farmer, wolf, goat and cabbage
A farmer is trying to cross a river with a wolf, a goat and a cabbage. He has a row boat that he can use to carry at most one item at a time (plus himself) across the river. Only the farmer can row the boat so he has to be with the boat in each of its trips across the river. The farmer’s problem is that he can’t leave the wolf alone with the goat, or the goat alone with the cabbage, at any time. How should they use the boat to cross the river? For this question, you are to design a state-space search approach to this problem.
a) Design and describe an appropriate representation for a state in this search problem. b) Under your chosen representation, what is a goal state for the search problem?
c) Under your chosen representation, show the initial state and its legal successors.
d) In general, what conditions need to be in order to generate legal successors of a state? e) Conduct the search using your representation.
COMP3308/3608 Artificial Intelligence, s1 2022
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com