13 ธันวาคม 2561

Published 12/13/2561 by with 0 comment

เขียนภาษาโปรแกรมเชิงข้อจำกัดบน Python

สวัสดีผู้อ่านทุกท่านครับ บทความนี้ผมจะพาผู้อ่านไปเขียนภาษาโปรแกรมเชิงข้อจำกัดบน Python กันครับ

ภาษาโปรแกรมเชิงข้อจำกัด หรือ 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
อ้างอิง

เขียนภาษาโปรแกรมเชิงข้อจำกัดบน Python

เราสามารถเขียนภาษาโปรแกรมเชิงข้อจำกัดบน Python ได้โดยอาศัยโมดูล python-constraint
  • เป็น BSD 2-Clause "Simplified" License
  • รองรับทั้ง Python 2 และ Python 3
  • เป็น pure Python
เรามาลองเขียนภาษาโปรแกรมเชิงข้อจำกัดบน 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 ความคิดเห็น:

แสดงความคิดเห็น

แสดงความคิดเห็นได้ครับ :)