ฉันต้องการแก้ไขปัญหาต่อไปนี้โดยใช้ข้อจำกัด แต่จริงๆ แล้วฉันไม่รู้ว่าจะเริ่มต้นจากตรงไหน ดังนั้นฉันจึงตัดสินใจโพสต์ไว้ที่นี่เพื่อขอความช่วยเหลือ
*** Fitting squares ***
Given the set of black squares of Figure 1 (a 2x2, 3x3, 4x4 and a 5x5 square),
fit them all into the white rectangle of Figure 1 (a 7x9 rectangle), and this in
such a way that there is no overlap between the squares.
Note that the black squares can only be put on integer coordinates.
Formulate the problem above as a constraint problem. Come up with a useful
representation of the problem in terms of the constraint processing tool.
Provide an explanation of indices, variables and domains. Furthermore,
provide for every introduced constraint,
the meaning of the constraint in natural language.
โปรดนี่ไม่ใช่การบ้าน เพราะฉันแก้ปัญหาการเพิ่มสี่เหลี่ยมและวงกลมด้วยตัวเองแล้ว แต่อันนี้ฉันไม่รู้ว่าจะเริ่มอย่างไรและตรงไหน ฉันกำลังเรียนรู้ข้อจำกัดนี้ตั้งแต่ยังเป็นมือใหม่ และไม่รู้วิธีแก้ไขปัญหานี้เลย และต้องการความช่วยเหลือ ฉันควรใช้ไวยากรณ์ต่อไปนี้เพื่อกำหนดตัวแปรและข้อจำกัด:
* ตัวแปร*
1)
ชื่อต้องขึ้นต้นด้วยตัวพิมพ์ใหญ่ [A-Z] และใช้เฉพาะ [A-Za-z0-9_] ตัวอย่าง: X หรือ MyVar_1
2)
โดเมนคือเซตของจำนวนเต็มทั้งหมดในช่วง [จาก,...,ถึง] ตรวจสอบให้แน่ใจว่าตั้งแต่ ≤ ถึง
3)
ดัชนีหมายถึงดัชนี (เดี่ยว!) ของตัวแปรที่จัดทำดัชนี ตัวอย่างเช่น หากคุณป้อนช่วงดัชนีตั้งแต่ 1 ถึง 8 สำหรับตัวแปร "X" ดังนั้น "X(1)", "X(2)", ..., "X(8)" แต่ละตัวจะเป็นตัวแปรปกติ ด้วยโดเมนเดียวกัน ระบุช่วงดัชนีตั้งแต่ ≤ ถึง หากคุณเว้นช่อง "ดัชนี" ว่างไว้ ตัวแปรของคุณจะถือว่าเป็นตัวแปรที่ไม่ได้จัดทำดัชนี (หมายเหตุ: การใช้ from = to เป็นไปได้ แม้ว่าจะไม่สมเหตุสมผลมากนัก คุณสามารถใช้ตัวแปรที่ไม่มีการจัดทำดัชนีแทนได้) อย่าใช้ชื่อเดียวกันสองครั้ง ห้ามใช้ชื่อเดียวกันสองครั้ง ห้ามใช้ชื่อเดียวกันสำหรับชื่อปกติและอีกครั้งสำหรับ ตัวแปรที่จัดทำดัชนีแล้ว! และอย่านำส่วนหนึ่งของชื่อตัวแปรมาใช้ซ้ำ เช่น หากคุณมี MyVar_1 อยู่แล้ว อย่าใช้ Var ด้วย
ข้อจำกัด
คุณสามารถป้อนข้อจำกัดทางคณิตศาสตร์ได้ หากจำเป็นพร้อมกับข้อกำหนดช่วงสำหรับดัชนีที่ใช้ ข้อจำกัดทางคณิตศาสตร์อยู่ในรูปแบบ Expr ∼ Expr โดยที่ Expr คือนิพจน์ที่ใช้จำนวนเต็ม ตัวแปรที่ประกาศ และเลขคณิตบางตัว และโดยที่ ∼ เป็นตัวดำเนินการเชิงสัมพันธ์
1)
เมื่อใช้ตัวแปรที่จัดทำดัชนี จะต้องกำหนดดัชนี
- ในรูปแบบ MyVar(index) เช่น ใช้ "(" และ ")" ด้านหลังชื่อตัวแปร และไม่มีช่องว่างระหว่างกัน
- โปรดทราบว่าดัชนีจะต้องเป็นตัวแปร ดังนั้นจึงไม่อนุญาตให้ใช้บางอย่างเช่น MyVar(37) เขียน MyVar(i) แทน และป้อนช่วง i=37
- นอกจากนี้ ดัชนีจะต้องปรากฏในช่อง "ช่วง" คำแนะนำ: หากข้อจำกัดของคุณต้องคงไว้ตลอดช่วงดัชนี เช่น i=1..10 จากนั้นเพียงป้อนช่วงที่น่าพอใจเล็กน้อย เช่น i>0
- ชื่อดัชนีสามารถปรากฏตามที่อยู่ในข้อจำกัด กล่าวคือ ไม่ใช่เป็นดัชนี
- อนุญาตให้ใช้รูปแบบ MyVar(index+x) หรือ MyVar(index-x) โดยที่ x เป็นจำนวนเต็ม อย่าใช้ช่องว่างก่อนหรือหลัง '+' หรือ '-'! 2)
เลขคณิตใช้ตัวดำเนินการ '+', '-', '*', '/', 'mod' โดยที่ 'X / Y' คือผลหารของ X และ Y (ปัดเศษลง) นอกจากนี้ยังอนุญาตให้ใช้ 'min(X,Y)', 'max(X,Y)', 'abs(X)' ได้ด้วย
3) ตัวดำเนินการเชิงสัมพันธ์ที่ใช้ได้คือ '=', '\=', '‹', '>', '=‹', '>=' โดยมีความหมายที่ชัดเจน
4) ใช้วงเล็บเหลี่ยมเพื่อชี้แจง! ตัวอย่าง: X(i) + Y(j) ‹ 12 หรือ min(X(i),X(j)) \= Z หรือ X(i) * i = 20
นอกจากนี้ยังสามารถใช้นิพจน์บูลีนได้อีกด้วย การเชื่อมต่อแบบบูลีนที่อนุญาตคือ '‹=>', '=>', '/\' และ '\/' สำหรับการเทียบเท่า การมีความหมาย การเชื่อม และการแตกแยก ตามลำดับ
ช่วงคือนิพจน์ที่ประกอบด้วยแต่ละดัชนีที่ใช้ในข้อจำกัด ตัวอย่าง: i ‹ j หรือ i = j หรือ (i = j /\ k \= l) นิพจน์ช่วงไม่ควรมี '‹=>', '=>' หรือ '\/' หมายเหตุ: ช่วงเป็นนิพจน์เชิงตรรกะ (โดยปริยายเป็นปริมาณสากล) ไม่ใช่นิพจน์ที่กำหนดเช่น i=1..10!
ตัวอย่างต่อไปนี้ใช้ไวยากรณ์ข้างต้น:
You can solve, e.g., some linear integer equations using normal variables only:
Name: X, domain: 1..10000
Name: Y, domain: 1..10000
Name: Z, domain: 1..1000000
Constraint: 29*X + 43*Y = Z
Constraint: X * Y = Z
Another example is the N-queens problem which uses index variables:
Name: Q(i), i=1..4, domain: 1..4
Constraint: Q(i) \= Q(j), range: i < j
Constraint: abs(Q(i) - Q(j)) \= j - i, range: i < j
ขอบคุณสำหรับความช่วยเหลือของคุณ.
