Question 2 [35 points] CSP- Search Consider a CSP, where there are eight variables A, B,...

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.

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