Artificial Intelligence: A Modern Approach
3rd Edition
ISBN: 9780136042594
Author: Stuart Russell, Peter Norvig
Publisher: Prentice Hall
expand_more
expand_more
format_list_bulleted
Question
Chapter 3, Problem 28E
Program Plan Intro
Suboptimal solution:
- Suboptimal heuristic search
algorithms such as weighted A* and greedy best-first search are widely use to solve problems for which guaranteed optimal solutions are too expensive to obtain. - To guide their search, these algorithms rely on a heuristic function.
- These algorithms are used because, when constructing the heuristics, the optimal search can fail when considering the suboptimal search.
Explanation of Solution
Proof:
- As given in the problem, suppose
- Consider any node n on a path to an optimal goal. Here,
Expert Solution & Answer
Trending nowThis is a popular solution!
Students have asked these similar questions
Consider the generalization of the rickety bridge crossing puzzle in which we
have n > 1 people whose bridge crossing times are t₁, t2, ..., tn. You may assume that t₁ ≤ t₂
< ... < tn. All the other conditions of the problem remain the same: all begin on the same
side of the bridge, at most two people at the time can cross the bridge (and they move
with the speed of the slower of the two) and they must carry with them the only flashlight
the group has.
Design a greedy algorithm for this problem and find how long it will take to cross the
bridge by using this algorithm. Find an instance with the smallest number of people for
which your greedy algorithm does not yield a minimum crossing time.
P is the set of problems that can be solved in polynomial time.
More formally, P is the set of decision problems (e.g. given a graph G, does this graph G
contain an odd cycle) for which there exists a polynomial-time algorithm to correctly output the
answer to that problem.
What is NP? Consider these five options and determine which option is correct.
O NP is the set of problems that cannot be solved in polynomial time.
NP is the set of problems whose answer can be found in polynomial time.
O NP is the set of problems whose answer cannot be found in polynomial time.
O NP is the set of problems that can be verified in polynomial time.
O NP is the set of problems that cannot be verified in polynomial time.
A graduate student is working on a problem X. After working on it for several days she is unable to find a polynomial-time solution to the problem. Therefore, she attempts to prove that he problem is NP-complete. To prove that X is NP-complete she first designs a decision version of the problem. She then proves that the decision version is in NP. Next, she chooses SUBSET-SUM, a well-known NP-complete problem and reduces her problem to SUBSET-SUM (i.e., she proves X £p SUBSET-SUM). Is her approach correct? Explain your answer.
Chapter 3 Solutions
Artificial Intelligence: A Modern Approach
Ch. 3 - Explain why problem formulation must follow goal...Ch. 3 - Prob. 2ECh. 3 - Prob. 3ECh. 3 - Prob. 4ECh. 3 - Prob. 5ECh. 3 - Prob. 6ECh. 3 - Prob. 8ECh. 3 - Prob. 9ECh. 3 - Prob. 10ECh. 3 - Prob. 11E
Ch. 3 - Prob. 12ECh. 3 - Prob. 13ECh. 3 - Prob. 14ECh. 3 - Prob. 15ECh. 3 - Prob. 16ECh. 3 - Prob. 17ECh. 3 - Prob. 18ECh. 3 - Prob. 20ECh. 3 - Prob. 21ECh. 3 - Prob. 22ECh. 3 - Trace the operation of A search applied to the...Ch. 3 - Prob. 24ECh. 3 - Prob. 25ECh. 3 - Prob. 26ECh. 3 - Prob. 27ECh. 3 - Prob. 28ECh. 3 - Prob. 29ECh. 3 - Prob. 31ECh. 3 - Prob. 32E
Knowledge Booster
Similar questions
- Write a recurrence that would be used in dynamic programming for thefollowing problem: Given a rod of length n and an array A of prices thatcontain all prices of all the pieces smaller than n. Determine the maximumvalue obtained by cutting up the rod and selling the pieces. Note that youcould sell the rod at its original length without cutting it.arrow_forwardQuestion 2: Consider the 0/1 knapsack problem. Given Nobjects where each object is specified by a weight and a profit, you are to put the objects in a bag of capacity C such that the sum of weights of the items in the bag does not exceed Cand the profits of the items is maximized. Note that you cannot use an item type more than once. a. Using dynamic programming, write an algorithm that finds the maximum total value according to the above constraints. b. What is the complexity of your algorithm? c. Show the dynamic programming table for the following data: W= { 2 ,7 , 1} , P={ 3 ,15 , 2 } and C=8.arrow_forwardConsider the problem of making change for n cents using the fewest number of coins. Assume that we live in a country where coins come in k dierent denominations c1, c2, . . . , ck, such that the coin values are positive integers, k ≥ 1, and c1 = 1, i.e., there are pennies, so there is a solution for every value of n. For example, in case of the US coins, k = 4, c1 = 1, c2 = 5, c3 = 10, c4 = 25, i.e., there are pennies, nickels, dimes, and quarters. To give optimal change in the US for n cents, it is sufficient to pick as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and nally give the rest in pennies. Prove that the coin changing problem exhibits optimal substructure. Design a recursive backtracking (brute-force) algorithm that returns the minimum number of coins needed to make change for n cents for any set of k different coin denominations. Write down the pseudocode and prove that your algorithm is correct.arrow_forward
- Consider the problem of making change for n cents using the fewest number of coins. Assume that we live in a country where coins come in k dierent denominations c1, c2, . . . , ck, such that the coin values are positive integers, k ≥ 1, and c1 = 1, i.e., there are pennies, so there is a solution for every value of n. For example, in case of the US coins, k = 4, c1 = 1, c2 = 5, c3 = 10, c4 = 25, i.e., there are pennies, nickels, dimes, and quarters. To give optimal change in the US for n cents, it is sufficient to pick as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and nally give the rest in pennies. Design a bottom-up (non-recursive) O(nk)-time algorithm that makes change for any set of k different coin denominations. Write down the pseudocode and analyze its running time. Argue why your choice of the array and the order in which you fill in the values is the correct one. Notice how it is a lot easier to analyze the running time of…arrow_forwardConsider the problem of making change for n cents using the fewest number of coins. Assume that we live in a country where coins come in k dierent denominations c1, c2, . . . , ck, such that the coin values are positive integers, k ≥ 1, and c1 = 1, i.e., there are pennies, so there is a solution for every value of n. For example, in case of the US coins, k = 4, c1 = 1, c2 = 5, c3 = 10, c4 = 25, i.e., there are pennies, nickels, dimes, and quarters. To give optimal change in the US for n cents, it is sufficient to pick as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and nally give the rest in pennies. Design a bottom-up (non-recursive) O(nk)-time algorithm that makes change for any set of k different coin denominations. Write down the pseudocode and analyze its running time. Argue why your choice of the array and the order in which you ll in the values is the correct one.arrow_forwardI just need the proof for the puzzle problem being NP-Complete.arrow_forward
- There are n ≥ 2 married couples who need to cross a river. They have a boat that can hold no more than two people at a time. To complicate matters, all the husbands are jealous and will not agree on any crossing procedure that would put a wife on the same bank of the river with another woman's husband without the wife's husband being there too, even if there are other people on the same bank. Can they cross the river under such constraints? Solve the problem for n = 2.arrow_forwardPlease assist with the following question as I am struggling. Thank you!arrow_forwardImagine that you have a problem P that you know is N P-complete. For this problem you have two algorithms to solve it. For each algorithm, some problem instances of P run in polynomial time and others run in exponential time (there are lots of heuristic-based algorithms for real N P-complete problems with this behavior). You can’t tell beforehand for any given problem instance whether it will run in polynomial or exponential time on either algorithm. However, you do know that for every problem instance, at least one of the two algorithms will solve it in polynomial time. (a) What should you do? (b) What is the running time of your solution? 564 Chap. 17 Limits to Computation (c) What does it say about the question of P = N P if the conditions described in this problem existed?arrow_forward
- Given A = {1,2,3} and B={u,v}, determine. a. A X B b. B X Barrow_forwardThe following problem is called the coupon collector problem and has many applications in computer science.Consider a bag that contains N different types of coupons (say coupons numbered 1 . . .N. There areinfinite number of each typ of coupon. Each time a coupon is drawn from the bag, it is independent of theprevious selection and equally likely to be any of the N types. Since there are infinite numbers of each type,one can view this as sampling with replacement. Let T denote the random variable that denotes the numberof coupons that needs to be collected until one obtains a complete set of atleast one of each type of coupon.Write a R simulation code to compute the E(T). Plot E(T) as for N = 10, 20, 30, 40, 50, 60. In the same plot show the theoretical value and summarize your observation regarding the accuracy of theapproximation.arrow_forwardCorrect answer will be upvoted else downvoted. Computer science. way from block u to impede v is an arrangement u=x0→x1→x2→⋯→xk=v, where there is a street from block xi−1 to obstruct xi for each 1≤i≤k. The length of a way is the amount of lengths over all streets in the way. Two ways x0→x1→⋯→xk and y0→y1→⋯→yl are unique, if k≠l or xi≠yi for some 0≤i≤min{k,l}. Subsequent to moving to another city, Homer just recollects the two unique numbers L and R yet fails to remember the numbers n and m of squares and streets, separately, and how squares are associated by streets. Be that as it may, he accepts the number of squares ought to be no bigger than 32 (on the grounds that the city was little). As the dearest companion of Homer, if it's not too much trouble, let him know whether it is feasible to view as a (L,R)- constant city or not. Input The single line contains two integers L and R (1≤L≤R≤106). Output In case it is difficult to track down a (L,R)- ceaseless city…arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning