ภาษาโปรแกรมเชิงข้อจำกัด หรือ Constraint programming คืออะไร ?
ภาษาโปรแกรมเชิงข้อจำกัด หรือ Constraint programming (CP) ในทางวิทยาการคอมพิวเตอร์ (Computer Science) เป็นการเขียนโปรแกรมให้คอมพิวเตอร์หาคำตอบจากปัญหา โดยเรากำหนดข้อจำกัดของปัญหาไว้ ถูกนำไปใช้ครั้งแรกในภาษา Prolog III, CLP(R), และ CHIPตัวอย่างโจทย์ที่แก้ได้ด้วยการเขียนภาษาโปรแกรมเชิงข้อจำกัด เช่น
x มีสมาชิก {1,2,3,4,5}อ้างอิง
y มีสมาชิก {1,2,3,4,5}
x+y>9
คำตอบ คือ x=5 y=5
- Constraint Programming http://www.constraint.org/en/intro.html
- Constraint programming - Wikipedia https://en.wikipedia.org/wiki/Constraint_programming
- What is Constraint Programming? https://www.quora.com/What-is-Constraint-Programming
เขียนภาษาโปรแกรมเชิงข้อจำกัดบน Python
เราสามารถเขียนภาษาโปรแกรมเชิงข้อจำกัดบน Python ได้โดยอาศัยโมดูล python-constraint- เป็น BSD 2-Clause "Simplified" License
- รองรับทั้ง Python 2 และ Python 3
- เป็น pure Python
ก่อนอื่นให้ทำการติดตั้ง python-constraint ด้วยคำสั่ง
pip install python-constraintเสร็จแล้ว เรามาลองเขียนโปรแกรมเชิงข้อจำกัด เพื่อหาคำตอบจากโจทย์ปัญหาของเรากัน
โจทย์ มีเลข 1 - 100 ผมต้องการหาจำนวนที่สามารถ หาร 2 ลงตัว และหาร 7 เหลือเศษ 1
ก่อนใช้งานให้ทำการเรียกใช้งานโมดูล python-constraint ก่อน ด้วยคำสั่ง
from constraint import *จากนั้นสร้างตัวแปร problem แทนคลาส Problem เพื่อแทนปัญหาของเรา
problem = Problem()แล้วทำการสร้างตัวแปรชื่อ a เก็บค่าทั้งหมดในโดเมนปัญหา ในกรณีนี้เลข 1 - 100 ของเรา
problem.addVariable("a",[i for i in range(1,101)]) # ลูปเอา 1 - 100 ออกมาเป็น listจากนั้น เขียนฟังก์ชัน lambda สำหรับแก้ไขปัญหาหาจำนวนในช่วง 1 - 100 ที่สามารถ หาร 2 ลงตัว และหาร 7 เหลือเศษ 1
problem.addConstraint(lambda a: a%2 == 0 and a%7 == 1,("a")) # % คือ mod หารเอาเศษเสร็จแล้วหาผลลัพธ์กัน
problem.getSolutions()ผลลัพธ์
[{'a': 92}, {'a': 78}, {'a': 64}, {'a': 50}, {'a': 36}, {'a': 22}, {'a': 8}]ดังนั้น จำนวนในช่วง 1 - 100 ที่สามารถ หาร 2 ลงตัว และหาร 7 เหลือเศษ 1 คือ 8 , 22 , 36 , 50 , 64 , 78 และ 92
โค้ดฉบับเต็ม
from constraint import *
problem = Problem()
problem.addVariable("a",[i for i in range(1,101)])
problem.addConstraint(lambda a: a%2 == 0 and a%7 == 1,("a"))
problem.getSolutions()หลังจากเราแก้ไขปัญหาข้างบนไปได้แล้ว ต่อไปเรามาแก้ไขโจทย์ปัญหาหลักที่อยู่บนหัวบทความกัน
ก่อนอื่น เราเดาขอบเขต ประมาณไว้ว่าน่าจะอยู่ในช่วง -100 ถึง 100 เราจึงเขียนค่า x และ y ได้ดังนี้
problem = Problem()
problem.addVariable("x",[i for i in range(-100,101)])
problem.addVariable("y",[i for i in range(-100,101)])จากนั้น เราทำการเขียนเงื่อนไขปัญหาให้อยู่ในฟังก์ชัน lambda เป็นข้อจำกัดปัญหาเพื่อหาคำตอบ
problem.addConstraint(lambda x,y: x - (2*y) == 9 and (4*x) - (3*y) == 6,("x","y"))จากนั้นหาคำตอบกัน
problem.getSolutions()ผลลัพธ์
[{'x': -3, 'y': -6}]ดังนั้น ค่า x และ y ที่ทำให้ x - 2y = 9 และ 4x - 3y = 6 คือ x = -3 และ y = -6
โค้ดฉบับเต็ม
from constraint import *
problem = Problem()
problem.addVariable("x",[i for i in range(-100,101)])
problem.addVariable("y",[i for i in range(-100,101)])
problem.addConstraint(lambda x,y: x - (2*y) == 9 and (4*x) - (3*y) == 6,("x","y"))
problem.getSolutions()นอกจากนั้น เรายังสามารถเขียนโปรแกรมเพื่อแก้โจทย์เกมซูโดกุได้ สามารถดูได้ที่ ตัวอย่างการแก้โจทย์โปรแกรมเกมซูโดกุ
อ่านรายละเอียดเพิ่มเติมได้ที่ https://github.com/python-constraint/python-constraint
0 ความคิดเห็น:
แสดงความคิดเห็น
แสดงความคิดเห็นได้ครับ :)