Artificial Intelligence: A Modern Approach
3rd Edition
ISBN: 9780136042594
Author: Stuart Russell, Peter Norvig
Publisher: Prentice Hall
expand_more
expand_more
format_list_bulleted
Expert Solution & Answer
Chapter 5, Problem 20E
a.
Explanation of Solution
Finite leaf values
- There is no pruning.
- In a max tree, the...
b.
Explanation of Solution
Pruning in expectimax tree
- There is no pruning.
- An unseen leaf might have a value arbitrarily highe...
c.
Explanation of Solution
Nonnegative leaf values
- There is no pruning.
- In a max tree, ...
d.
Explanation of Solution
Nonnegative leaf values
- There is no pruning.
- Nonnegative value...
e.
Explanation of Solution
Leaf values in a range
- There is pruning.
- If the first...
f.
Explanation of Solution
Leaf values in a range
- There is pruning.
- Suppose the first action at the root has value 0...
g.
Explanation of Solution
Outcomes of a chance
- Highest probability first...
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Artificial Intelligence - Adversarial Search - a Game with uncertainty
1. In the following, a “max” tree consists only of max nodes, whereas an “expectimax” tree consistsof a max node at the root with alternating layers of chance and max nodes. At chance nodes, alloutcome probabilities are nonzero. The goal is to find the value of the root with a bounded-depthsearch. For each of following statements, either give an example or explain why this is impossible.
a) Assuming that leaf values are finite but unbounded, is pruning (as in α-β pruning) ever possiblein a max tree?b) Is pruning ever possible in an expectimax tree under the same conditions?c) If leaf values are all nonnegative, is pruning ever possible in a max tree? Give an example, orexplain why not.d) If leaf values are all nonnegative, is pruning ever possible in an expectimax tree? Give anexample, or explain why not.e) If leaf values are all in the range [0,1], is pruning ever possible in a max tree? Give an example,or explain…
You are given a weighted tree T.(As a reminder, a tree T is a graph that is connected and contains no cycle.) Each node of the tree T has a weight, denoted by w(v). You want to select a subset of tree nodes, such that weight of the selected nodes is maximized, and if a node is selected, then none of its neighbors are selected.
True/False. Give a short explanation.
i. Let T be a tree constructed by Dijkstra's algorithm for a weighted connected graph
G. T is a spanning tree of G?
ii. Let T be a tree constructed by Dijkstra's algorithm for a weighted connected graph
G. T is a minimum spanning tree of G?
iii. If an NP-complete problem can be solved in linear time, then all NP-complete
problems can be solved in linear time.
iv. If P # NP, there could be a polynomial-time algorithm for SAT.
Chapter 5 Solutions
Artificial Intelligence: A Modern Approach
Knowledge Booster
Similar questions
- Inference in Bayesian networks is NP-hard in the worst case because it includes propositional logic inference as a special case. Write down a Bayesian network, where the nodes represent logical sentences, that implements modus ponens inference rule A ⇒ B, A infer B.arrow_forwardYou use your favorite decision tree algorithm to learn a decision tree for binary classification. Your tree hasJ leaves indexed j = 1, . . . , J. Leaf j contains nj training examples, mj of which are positive. However,instead of predicting a label, you would like to use this tree to predict the probability P(Y = 1 | X) (whereY is the binary class and X are the input attributes). Therefore, you decide to have each leaf predict a realvalue pj ∈ [0, 1]. -What are the values pj that yield the largest log likelihood? Show your work.arrow_forwardAnswer the given question with a proper explanation and step-by-step solution.arrow_forward
- Correct answer only. Else i will dislike. The guide of the maze shapes a tree with n rooms numbered from 1 to n and n−1 burrows associating them to such an extent that it is feasible to go between each pair of rooms through a few passages. The I-th room (1≤i≤n) has simulated intelligence hallucination rate. To go from the x-th space to the y-th room, there should exist a passage among x and y, and it takes max(|ax+ay|,|ax−ay|) energy. |z| means the outright worth of z. To forestall grave looters, the labyrinth can change the hallucination pace of any room in it. Chanek and Indiana would ask q inquiries. There are two kinds of inquiries to be finished: 1 u c — The figment pace of the x-th room is changed to c (1≤u≤n, 0≤|c|≤109). 2 u v — Chanek and Indiana ask you the base amount of energy expected to take the mysterious fortune at room v in case they are at first at room u (1≤u,v≤n). Help them, so you can get a part of the fortune! Input :The primary line contains two integers n and…arrow_forwardConsider a graph G, where each of the edges have different weights. Let T1 be the minimum-weight spanning tree produced by Kruskal's Algorithm, and let T2 be the minimum-weight spanning tree produced by Prim's Algorithm. I claim that T1 and T2 must be identical spanning trees - i.e., the exact same set of edges must appear in both trees. Determine whether this claim is TRUE or FALSE. If your answer is TRUE, see if you can figure out why the claim is true. If your answer is FALSE, see if you can come up with a counterexample.arrow_forwardYou are given a tree T with n vertices, rooted at vertex 1. Each vertex i has an associated value ai , which may be negative. You wish to colour each vertex either red or black. However, you must ensure that for each pair of red vertices, the path between them in T consists only of red vertices.Design an algorithm which runs in O(n) time and finds the maximum possible sum of values of red vertices, satisfying the constraint above.arrow_forward
- Given an undirected weighted graph G with n nodes and m edges, and we have used Prim’s algorithm to construct a minimum spanning tree T. Suppose the weight of one of the tree edge ((u, v) ∈ T) is changed from w to w′, design an algorithm to verify whether T is still a minimum spanning tree. Your algorithm should run in O(m) time, and explain why your algorithm is correct. You can assume all the weights are distinct. (Hint: When an edge is removed, nodes of T will break into two groups. Which edge should we choose in the cut of these two groups?)arrow_forwardConsider eight points on the Cartesian two-dimensional x-y plane. a g C For each pair of vertices u and v, the weight of edge uv is the Euclidean (Pythagorean) distance between those two points. For example, dist(a, h) = V4? + 1² = v17 and dist(a, b) = v22 + 0² = 2. Using the algorithm of your choice, determine one possible minimum-weight spanning tree and compute its total distance, rounding your answer to one decimal place. Clearly show your steps.arrow_forwardConsider the following problem for path finding where S is the source, G is the Goal and O are obstacles. We can only move horizontally and vertically (not diagonally). We will not re-visit an already visited cell. - Simulate the application of Breadth-first search tree to find all paths from S to G. Provide the order of visit for each node. - Simulate the application of Depth-first search tree to find all paths from S to G. Provide the order of visit for each node. S O G Oarrow_forward
- In a lecture the professor said that for every minimum spanning tree T of G there is an execution of the algorithm of Kruskal which delivers T as a result. ( Input is G). The algorithm he was supposedly talking about is: Kruskal() Precondition. N = (G, cost) is a connected network with n = |V| node and m = |E| ≥ n − 1 edges.All edges of E are uncolored. postcondition: All edges are colored. The green-colored edges together with V form one MST by N. Grand Step 1: Sort the edges of E in increasing weight: e1 , e2, . . . , em Grand step 2: For t = 0.1, . . . , m − 1 execute: Apply Kruskal's coloring rule to the et+1 edge i dont really understand this statement or how it is done. can someone explain me what he meant?arrow_forwardDevelop the Branch and Bound tree for the following problem and find the optimal solution. For convenience, always select x1 as the branching variable at node 0.max ? = 2?1 + 3?2 s.t. 5?1 + 7?2 ≤ 354?1 + 9?2 ≤ 36 ?1, ?2 ≥ 0 and integerarrow_forwardLet G = (V, E) be a DAG, where every edge e = ij and every vertex x have positive weighs w(i,j) and w(x), respectively, associated with them. Design an algorithm for computing a maximum weight path. What is the time complexity of your algorithm? (You must start with the correct definitions, and then write a recurrence relation.)arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education