ปัญหาการบรรลุข้อจำกัด

ปัญหาการบรรลุข้อจำกัด (Constraint Satisfaction Problem) คือการกำหนดค่าให้กับชุดของตัวแปรที่สอดคล้องกับข้อจำกัดทั้งหมดพร้อมกัน ซึ่งเป็นการนำเสนอที่เป็นแบบแผนสำหรับปัญหาเชิงการจัดหมู่หลายประเภท

Definition

ปัญหาการบรรลุข้อจำกัดประกอบด้วยชุดของตัวแปร โดเมนของค่าที่เป็นไปได้สำหรับแต่ละตัวแปร และชุดของข้อจำกัดที่ระบุการรวมกันของค่าที่อนุญาต การแก้ปัญหาคือการกำหนดค่าที่สมบูรณ์ซึ่งไม่ละเมิดข้อจำกัดใดๆ

Scope

หัวข้อนี้ครอบคลุมรูปแบบของปัญหาการบรรลุข้อจำกัด (CSP) (ตัวแปร, โดเมน, ข้อจำกัด) และอัลกอริทึมที่ใช้ในการแก้ปัญหา: การค้นหาแบบย้อนรอย (backtracking search) พร้อมด้วยฮิวริสติกส์ในการจัดลำดับตัวแปรและค่า, การเผยแพร่ข้อจำกัด (constraint propagation) และเทคนิคความสอดคล้อง (consistency techniques) (ความสอดคล้องของโหนด, ส่วนโค้ง, และเส้นทาง เช่น อัลกอริทึม AC-3) และการใช้ประโยชน์จากโครงสร้างของปัญหา (CSPs แบบโครงสร้างต้นไม้, การปรับสภาพด้วยชุดตัด) หัวข้อนี้เชื่อมโยงกับการค้นหาเฉพาะที่สำหรับ CSPs และการปฏิบัติที่กว้างขึ้นของการเขียนโปรแกรมข้อจำกัด (constraint programming) การกำหนดรูปแบบปัญหาที่คล้ายกันโดยใช้การหาค่าเหมาะที่สุดแบบต่อเนื่อง (continuous-optimization) และการเรียนรู้ (learning-based formulations) อยู่นอกเหนือขอบเขตของหัวข้อนี้

Core questions

• ปัญหาที่หลากหลาย (การจัดตารางเวลา, การระบายสีแผนที่, ปริศนา) ถูกนำเสนอในรูปแบบตัวแปร โดเมน และข้อจำกัดได้อย่างไร?
• การเผยแพร่ข้อจำกัดช่วยลดค่าก่อนและระหว่างการค้นหาเพื่อลดการย้อนรอยได้อย่างไร?
• ฮิวริสติกส์ในการจัดลำดับตัวแปรและค่าใดที่ทำให้การค้นหาแบบย้อนรอยมีประสิทธิภาพ?
• โครงสร้างของกราฟข้อจำกัด (เช่น การมีรูปร่างคล้ายต้นไม้) สามารถนำมาใช้ประโยชน์ในการแก้ปัญหาได้อย่างมีประสิทธิภาพได้อย่างไร?

Key concepts

• ตัวแปร, โดเมน, ข้อจำกัด
• กราฟข้อจำกัด
• การค้นหาแบบย้อนรอย
• การตรวจสอบล่วงหน้า
• ความสอดคล้องของส่วนโค้งและ AC-3
• ฮิวริสติกส์ค่าที่เหลือต่ำสุด
• การเผยแพร่ข้อจำกัด
• CSPs แบบโครงสร้างต้นไม้และการปรับสภาพด้วยชุดตัด

Key theories

ความสอดคล้องของส่วนโค้งและการเผยแพร่ข้อจำกัด

CSP จะมีความสอดคล้องของส่วนโค้งเมื่อทุกค่าของทุกตัวแปรมีคู่ที่สอดคล้องกันในแต่ละตัวแปรข้างเคียง อัลกอริทึมเช่น AC-3 บังคับใช้สิ่งนี้โดยการลบค่าที่ไม่รองรับซ้ำๆ ซึ่งมักจะลดขนาดโดเมนลงอย่างมากก่อนหรือระหว่างการค้นหา

การค้นหาแบบย้อนรอยด้วยฮิวริสติกส์

CSPs ถูกแก้ปัญหาโดยการกำหนดค่าแบบเจาะลึก (depth-first assignment) พร้อมการย้อนรอย ซึ่งทำได้จริงด้วยฮิวริสติกส์ เช่น การเลือกตัวแปรที่มีข้อจำกัดมากที่สุด (ค่าที่เหลือต่ำสุด), ค่าที่จำกัดน้อยที่สุด และโดยการสลับการตรวจสอบล่วงหน้าหรือการเผยแพร่เพื่อตรวจจับทางตันตั้งแต่เนิ่นๆ

การใช้ประโยชน์จากโครงสร้าง

เมื่อกราฟข้อจำกัดเป็นต้นไม้ CSP สามารถแก้ไขได้ในเวลาที่เป็นเชิงเส้นตามจำนวนตัวแปร และโครงสร้างที่ใกล้เคียงกับต้นไม้สามารถลดรูปให้เป็นกรณีนี้ได้ผ่านการปรับสภาพด้วยชุดตัดหรือการแยกส่วนต้นไม้

Clinical relevance

เทคนิค CSP เป็นกลไกสำคัญเบื้องหลังการจัดตารางเวลา, การจัดสรรทรัพยากร, การกำหนดค่าผลิตภัณฑ์, การตรวจสอบฮาร์ดแวร์และซอฟต์แวร์, และการแก้ปริศนาเช่นซูโดกุ ภาษาโปรแกรมข้อจำกัดและตัวแก้ปัญหาที่สร้างขึ้นจากแนวคิดเหล่านี้ถูกนำมาใช้อย่างแพร่หลายในการวางแผนอุตสาหกรรมและการวิจัยการดำเนินงาน

History

เครือข่ายข้อจำกัดเกิดขึ้นในปี 1970 จากงานเกี่ยวกับการติดป้ายฉากและความสอดคล้องเชิงสัมพันธ์ โดยบทความของ Mackworth ในปี 1977 ได้กำหนดรูปแบบความสอดคล้องของโหนด ส่วนโค้ง และเส้นทาง ตลอดช่วงปี 1980-90 สาขาวิชานี้ได้พัฒนาเป็นโปรแกรมข้อจำกัด ซึ่งได้รับการรวบรวมใน Handbook of Constraint Programming ปี 2006 และยังคงเป็นหัวข้อมาตรฐานใน AI

Key figures

• Alan K. Mackworth
• Rina Dechter
• Eugene C. Freuder
• Ugo Montanari

Seminal works

• mackworth1977
• dechter2003
• rossi2006

Frequently asked questions

ปัญหาการบรรลุข้อจำกัดแตกต่างจากปัญหาการค้นหาทั่วไปอย่างไร?

ปัญหาการค้นหาทั่วไปจะพิจารณาสถานะเป็นกล่องดำ แต่ CSP จะเปิดเผยโครงสร้างภายในของสถานะเป็นการกำหนดค่าให้กับตัวแปรภายใต้ข้อจำกัด โครงสร้างนี้ช่วยให้ตัวแก้ CSP สามารถใช้การเผยแพร่ข้อจำกัดและฮิวริสติกส์การจัดลำดับที่การค้นหาทั่วไปไม่สามารถใช้ประโยชน์ได้

ความสอดคล้องของส่วนโค้งทำอะไร?

ความสอดคล้องของส่วนโค้งจะลบค่าออกจากโดเมนของตัวแปรที่ไม่มีค่าที่เข้ากันได้ในตัวแปรข้างเคียง โดยพิจารณาจากข้อจำกัดระหว่างกัน การบังคับใช้สิ่งนี้ก่อนและระหว่างการค้นหาจะช่วยลดพื้นที่การค้นหาและบางครั้งสามารถแก้ปัญหาได้โดยตรงโดยไม่ต้องย้อนรอย