Question 2 [35 points] CSP- Search Consider a CSP, where there are eight variables A, B,...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Question 2 [35 points] CSP- Search Consider a CSP, where there are eight variables A, B, C, D, E, F, G, H, each with domain {1, 2, 3, 4). Suppose the constraints are: A>G ● ● ● ● ● |G-C| = 1 D != C G != F |E-FI is odd ● X=t Y=t failure ● Y=f Z-t solution Z-f failure X=f Y=t Z-t failure Z-f solution. ● . ● Y=f failure ASH |H-CI is even E != C H!= F ● a) [25 points] Use DFS with pruning to solve this problem, using the variable ordering A, B, C, D, E, F, G, H. To do this you will write (and then run) a program that generates the search tree (see below) reports all solutions (models) found, if any reports the number of failing consistency checks (i.e. failing branches) in the tree |F-B|=1 H = D E<D-1 C!= F ● You can use whatever programming language you like. Make sure to make your code as readable as possible (good variable naming, plenty of comments, good indentation, etc.). . To draw the search tree, you may want to write it in text form with each branch on one line. For example, suppose we had variables X, Y and Z with domains {t, f} and constraints X != Y, Y !=Z. The corresponding search tree, with the order X, Y, Z, can be written as: G<H D≥G E != H-2 DI F-1 Your tree output doesn't have to follow this exact format, but it should be readable enough to allow you to check your work. Do not include the generated search tree in your submission. Include all of the following in your submission: The solutions found The number of failing branches Your code (do this by simply copying and pasting your code into your submission document; a fixed-width font like Courier New will help the code remain readable) If you do not include all three of these items in your submission, you will get zero marks for this question. BONUS [10 points]: Design your program such that you can search using any variable ordering without having to make changes to your code. The one allowed exception is if you initialize your ordering as a hard-coded list that you then input into a program function. For example, if you initialize your list as follows: ordering = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] then you may edit that initialization when using different variable orderings. b) [5 points] Come up with a simple variable selection heuristic (also called a "degree heuristic" in lecture) that results in a smaller tree than in part (a), and report the following: Your variable selection heuristic A variable ordering that you obtain using this heuristic How many failing consistency checks there are for a tree obtained from this variable ordering. Note: you are not being asked to find the smallest possible tree. c) [5 points] Explain why you expect the heuristic in part (b) to be reasonable. Question 2 [35 points] CSP- Search Consider a CSP, where there are eight variables A, B, C, D, E, F, G, H, each with domain {1, 2, 3, 4). Suppose the constraints are: A>G ● ● ● ● ● |G-C| = 1 D != C G != F |E-FI is odd ● X=t Y=t failure ● Y=f Z-t solution Z-f failure X=f Y=t Z-t failure Z-f solution. ● . ● Y=f failure ASH |H-CI is even E != C H!= F ● a) [25 points] Use DFS with pruning to solve this problem, using the variable ordering A, B, C, D, E, F, G, H. To do this you will write (and then run) a program that generates the search tree (see below) reports all solutions (models) found, if any reports the number of failing consistency checks (i.e. failing branches) in the tree |F-B|=1 H = D E<D-1 C!= F ● You can use whatever programming language you like. Make sure to make your code as readable as possible (good variable naming, plenty of comments, good indentation, etc.). . To draw the search tree, you may want to write it in text form with each branch on one line. For example, suppose we had variables X, Y and Z with domains {t, f} and constraints X != Y, Y !=Z. The corresponding search tree, with the order X, Y, Z, can be written as: G<H D≥G E != H-2 DI F-1 Your tree output doesn't have to follow this exact format, but it should be readable enough to allow you to check your work. Do not include the generated search tree in your submission. Include all of the following in your submission: The solutions found The number of failing branches Your code (do this by simply copying and pasting your code into your submission document; a fixed-width font like Courier New will help the code remain readable) If you do not include all three of these items in your submission, you will get zero marks for this question. BONUS [10 points]: Design your program such that you can search using any variable ordering without having to make changes to your code. The one allowed exception is if you initialize your ordering as a hard-coded list that you then input into a program function. For example, if you initialize your list as follows: ordering = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] then you may edit that initialization when using different variable orderings. b) [5 points] Come up with a simple variable selection heuristic (also called a "degree heuristic" in lecture) that results in a smaller tree than in part (a), and report the following: Your variable selection heuristic A variable ordering that you obtain using this heuristic How many failing consistency checks there are for a tree obtained from this variable ordering. Note: you are not being asked to find the smallest possible tree. c) [5 points] Explain why you expect the heuristic in part (b) to be reasonable.
Expert Answer:
Answer rating: 100% (QA)
a Solution Here is the Python code to solve the given CSP problem using DFS with pruning ... View the full answer
Related Book For
Posted Date:
Students also viewed these programming questions
-
solve a somewhat larger problem whose solution incorporates the programming concepts that you have been studying: Variables, Data Types, Control Structures (if-then, if-then-else, loops, switch,...
-
if we choose statistic as our keyword, our cipher would be determined as follows: method i. write the word statistic without the repeated letters. then complete the cipher with the unused alphabet...
-
Your friend recently attended a local mail fraud trial. In your conversation about the case, she described the cross-examination of the expert witness as follows: After his counsels questioning was...
-
You recently purchased a stock that is expected to earn 12 percent in a booming economy, 7 percent in a normal economy and lose 5 percent in a recessionary economy. There is a 17 percent probability...
-
The joint density function for random variables X and Y is (a) Find the value of the constant C. (b) Find P(X < 2, Y > 1). (c) Find P(X + Y < 1). C(x + y) if 0 < x < 3, 0 < y < 2 otherwise f(x, y)
-
A piece of cloth is discovered in a burial pit in the southwestern United States. A tiny sample of the cloth is burned to CO 2 , and the 14 C/ 12 C ratio is 0.250 times the ratio in todays...
-
On May 31, 2010, James Logan Company had a cash balance per books of $6,781.50. The bank statement from Farmers State Bank on that date showed a balance of $6,404.60. A comparison of the statement...
-
4. A monopolist is faced with the inverse demand function P(Q) denoting the price when output is Q. The monopolist has a constant average cost k per unit produced. (a) Find the profit function (Q),...
-
One-dimensional steady-state conduction, with no internal heat generation, occurs across a plane wall having a constant thermal conductivity of 30 W/m K. The material is 30 cm thick. For each case...
-
During the pandemic, an insurance company surveyed the distances (in kilome- tres) driven by a random sample of its customers in February and then again in April. The data is listed below. 151 146 94...
-
Discuss the importance of utilizing business and project plans in the health care industry. How does this differ from other business environments? Describe common elements used in most standard...
-
Add more static methods to the Future Value application In this exercise, you'll add two more static methods to the Future Value application that you saw at the end of this chapter. When you're done,...
-
Project L requires an initial outlay at t = 0 of $35,000, its expected cash inflows are $8,000 per year for 9 years, and its WACC is 12%. What is the project's NPV? Do not round intermediate...
-
Skillet Industries has a debtequity ratio of 1.7. Its WACC is 9.2 percent, and its cost of debt is 6.2 percent. The corporate tax rate is 35 percent. a. What is the companys cost of equity capital?...
-
This map illustrates the cities where Disney theme parks are located. Your task is to determine where Disney should build next. Reply to this discussion with what country and city where you believe...
-
The following information was available: spot rate for Japanese Yen: $0.009618; 1,460-day forward rate for Japanese Yen: $0.013560 (assume a 365 day year); U.S. risk-free rate: 2.00 percent; Japanese...
-
Imagine you are the HR manager at a company, and a female employee came to you upset because she felt a male coworker was creating a hostile work environment by repeatedly asking her out on dates...
-
A hospital administration wants to estimate the mean time spent by patients waiting for treatment at the emergency room. The waiting times (in minutes) recorded for a random sample of 35 such...
-
Find the value of t from the t distribution table for each of the following. a. Confidence level = 99% and df = 13 b. Confidence level = 95% and n = 36 c. Confidence level = 90% and df = 16
-
A history teacher has given her class a list of seven essay questions to study before the next test. The teacher announced that she will choose four of the seven questions to give on the test, and...
-
Explain the FAIR approach to ethical business communications.
-
Watch at least three videos of interviews with executives talking about corporate values. In four to five paragraphs, summarize what you learned. Consider the following options for gathering...
-
As a former chair of the U.S. Federal Reserve once said, Rules cannot take the place of character. In two to three paragraphs, explain what you think he meant by this statement.
Study smarter with the SolutionInn App