Problem 1: AC-3 Algorithm (9 pts.) Let assume we have the following constraint graph. A HIE...

Transcribed Image Text:

Problem 1: AC-3 Algorithm (9 pts.) Let assume we have the following constraint graph. A HIE a) Write down the binary constraints for the graph. 1. A B 2. Queue B 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 3, 4, 5, 6, 7, 8, 9, 10, 11. C D Arc b) Suppose you only have three colors to color this graph: Red, Blue, and Yellow. Start with node-A, assign the color red; assign the color yellow for node-D; and for node-G, assign the color blue. Run the AC-3 algorithm over the graph. Show the state of the assignment at each step. 1 (A-B) 2 (B-C) E 4, 5, 6, 7, 8, 9, 10, 11. (CB), (A= B) 3 (BD) F G H Resulting Assignment A-R; B (R. B, Y): C-IR. B, Y): D- Y E-(R, B, Y), F (R, B, Y): G-B; H [R. B. Y). 1 - (R, B, Y) A-R: B-(B, Y). C= (R, B, Y); D = Y; E-[R, B, Y): F-[R, B, Y): G-BH- (R. B. Y): I-[R. B. Y A-R. B-(B, Y): C-(R. B. Y): D-Y; E (R. B. Y): F-(R. B. Y); G-B; H- (R. B.Y. 1-(R. B.Y] A-RB B C IR. B. Y); D-Y, E- (R. B. Y: F-IR, B, Y): G-B; H-(R. B.) Y:I-(R. B. Y Problem 1: AC-3 Algorithm (9 pts.) Let assume we have the following constraint graph. A HIE a) Write down the binary constraints for the graph. 1. A B 2. Queue B 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 3, 4, 5, 6, 7, 8, 9, 10, 11. C D Arc b) Suppose you only have three colors to color this graph: Red, Blue, and Yellow. Start with node-A, assign the color red; assign the color yellow for node-D; and for node-G, assign the color blue. Run the AC-3 algorithm over the graph. Show the state of the assignment at each step. 1 (A-B) 2 (B-C) E 4, 5, 6, 7, 8, 9, 10, 11. (CB), (A= B) 3 (BD) F G H Resulting Assignment A-R; B (R. B, Y): C-IR. B, Y): D- Y E-(R, B, Y), F (R, B, Y): G-B; H [R. B. Y). 1 - (R, B, Y) A-R: B-(B, Y). C= (R, B, Y); D = Y; E-[R, B, Y): F-[R, B, Y): G-BH- (R. B. Y): I-[R. B. Y A-R. B-(B, Y): C-(R. B. Y): D-Y; E (R. B. Y): F-(R. B. Y); G-B; H- (R. B.Y. 1-(R. B.Y] A-RB B C IR. B. Y); D-Y, E- (R. B. Y: F-IR, B, Y): G-B; H-(R. B.) Y:I-(R. B. Y

Answer rating: 100% (QA)

Problem 1 AC3 Algorithm Given a constraint graph lets solve the given tasks a Write down the binary constraints for the graph For a constraint graph binary constraints are typically expressed as pairs ... View the full answer