程序代写代做代考 CSP Example.

CSP Example.
§ There are three different
musicians: John, Mark, and Sam.
§ They each come from a different country; one comes from the United States, one from Australia, and one from Japan.
§ They each play a different musical instrument; one plays the piano, one the saxophone, and one the violin.

CSP Example.
§ They take turns playing a solo piece of music (that is, they take turns playing alone) and each musician plays a solo only once.
§ The pianist plays first.
§ John plays the saxophone and plays before the Australian.
§ Mark comes from the United States and plays before the violinist.
1. What is the order the instruments are played. 2. Who plays what instrument
3. What is the nationality of each player

CSP Example
• Solve this by setting it up as a CSP and then using backtracking search to solve it.
• CSP Formulation
• Want the order the instruments are played
• One variable for each instrument violin, sax, piano
• Domain of values for each of these variables = {1, 2, 3} • The value indicates the order the instrument is played. • E.g., violin = 1 indicates that the violin is played first.
CSC384, University of Toronto
3

CSP Example
• CSP Formulation
• Want the order the instruments are played
• One variable for each instrument violin, sax, piano
• Domain of values for each of these variables = {1, 2, 3}
• The value indicates the order the instrument is played.
• E.g., violin = 1 indicates that the violin is played first.
• What about who plays what instrument
• One variable for each player john, mark, sam
• Domain of values
• {violin, sax, piano} is intuitive but this won’t work in a CSP formulation. Values cannot be variables!
• Use {1, 2, 3} instead. E.g. john = 1 indicates that John plays first.
• A CSP solution is an assignment of every variable. So if in the solution john = 1 and piano = 1, we can conclude that John plays the piano!
CSC384, University of Toronto
4

CSP Example
• CSP Formulation
• Want the order the instruments are played
• One variable for each instrument violin, sax, piano
• Domain of values for each of these variables = {1, 2, 3}
• The value indicates the order the instrument is played.
• E.g., violin = 1 indicates that the violin is played first.
• What about who plays what instrument
• One variable for each player john, mark, sam
• Domain of values
• {violin, sax, piano} is intuitive but this won’t work in a CSP formulation. Values cannot be variables!
• Use {1, 2, 3} instead. E.g. john = 1 indicates that John plays first.
• A CSP solution is an assignment of every variable. So if in the solution john = 1 and piano = 1,
we can conclude that John plays the piano!
• Finally we use the same logic for the countries • One variable for each country aust, us, japan
• Domain of values {1, 2, 3}
• E.g., japan = 1 indicates that the Japanese plays first
CSC384, University of Toronto
5

CSP Example
• CSP Formulation
• Variables john, mark, sam, violin, sax, piano, aust, us, japan.
• Domain of each variable = {1, 2, 3}
• Constraints:
1. Each musician, instrument, and country is different:
john ≠ mark, john ≠ sam, sam ≠ mark violin ≠ sax, violin ≠ piano, sax ≠ piano aust ≠ us, aust ≠ japan, us ≠ japan
2. The pianist plays first. Unary constraint. We can account for that by removing from the domain of piano all values that violate the constraint Dom[piano] = {1}
CSC384, University of Toronto
6

CSP Example
• CSP Formulation
• Variables john, mark, sam, violin, sax, piano, aust, us, japan.
• Domain of each variable = {1, 2, 3} • Constraints:
4. John plays the saxophone and plays before the Australia 4a: john = sax
4b: john < aust 5. Mark comes from the United States and plays before the violinist. 5a: mark = us 5b: mark < violin CSC384, University of Toronto 7 CSP Example • CSP Formulation • Variables john, mark, sam, violin, sax, piano, aust, us, japan. • Domain of each variable except piano = {1, 2, 3} • Dom[piano] = {1} • Constraints: 1. john ≠ mark, john ≠ sam, sam ≠ mark 2. violin ≠ sax, violin ≠ piano, sax ≠ piano 3. aust ≠ us, aust ≠ japan, us ≠ japan 4. john = sax 5. john < aust 6. mark = us 7. mark < violin CSC384, University of Toronto 8 CSP Example ≠ mark John ≠ sam ≠ violin ≠ sax aust ≠ japan ≠ ≠ us ≠ ≠ piano CSC384, University of Toronto 9 CSP Example • Solve by Forward Checking (all binary constraints so good for FC) + MRV (minimum remaining values Root piano = 1 sax = {2,3}, violin={2,3} japan = 2 sax = 2 violin = 3 john = 2 mark = 1 sam = 3 us = 1 aus = 3 violin={3}, john={2} mark = {1,2} mark = {1} sam = {1,3}, aus={3} sam = {3}, us={1} japan = {2,3} japan = {2} CSC384, University of Toronto 10