วันจันทร์ที่ 24 สิงหาคม พ.ศ. 2558
Constraint Satisfaction Problems (ความพึงพอใจของปัญหาข้อจำกัด)
- ค้นหาปัญหามาตรฐาน:
-สถานะ,เป้าหมาย,การกระทำ,ฟังก์ชั่นการแก้ปัญหาที่มีโดเมนที่เฉพาะเจาะจง
- CSP:
-เป้าหมายการดำเนินการฟังก์ชั่นการแก้ปัญหาที่มีโดเมนที่เฉพาะเจาะจง
-สถานะเป้าหมายการดำเนินการเป็นไปตามมาตรฐานการแสดง
-ขั้นตอนวิธีการค้นหาสามารถใช้ประโยชน์จากโครงสร้างของรัฐและใช้งานทั่วไปมากกว่าการวิเคราะห์พฤติกรรมปัญหาที่เฉพาะเจาะจง
-สถานะจะถูกกำหนดโดยตัวแปร Xi ด้วยค่าจากDi
-ชุดของข้อจำกัด ที่อนุญาตระบุรวมกันของค่าสำหรับย่อยของตัวแปร
-วิธีการแก้ปัญหาให้กับ CSP เป็นรัฐที่ตอบสนองข้อ จำกัด ทั้งหมด
-อัลกอริทึมที่มีประโยชน์ช่วยให้วัตถุประสงค์ทั่วไปมีอำนาจมากขึ้นขั้นตอนวิธีการค้นหากว่ามาตรฐาน
การระบายสีแผนที่ให้ใช้สีที่น้อยที่สุดแสดงแผนที่
- ตัวแปร:WA, NT, Q,NSW, V, SA, T
- ขอบเขตที่สนใจ:Di = {สีแดง, สีเขียว, สีฟ้า}
- ข้อจำกัด:ภูมิภาคที่อยู่ติดกัน ต้องมีที่แตกต่างกัน สีเช่น WA ≠ NT
- วิธีการแก้ปัญหา:มีการมอบหมายงานที่สมบูรณ์และสอดคล้องกัน
- เสร็จสมบูรณ์: ตัวแปรทั้งหมดที่ได้รับมอบหมายค่า
- สอดคล้อง: ตอบสนองการกำหนดข้อจำกัด
Constraint graph
- Binary CSP: แต่ละข้อจำกัดที่เกี่ยวข้องกับสองตัวแปร
- Constraint graph: โหนดเป็นตัวแปรโค้งที่มีข้อจำกัด
ชนิดของข้อจำกัด
Unary constraints: ที่เกี่ยวข้องกับเอกตัวแปรเดียว
e.g., SA ≠ green
Binary constraints :-ข้อจำกัดเกี่ยวข้องกับคู่ของตัวแปร
e.g., SA ≠ WA
Higher-order: ข้อจำกัดที่เกี่ยวข้องกับมากกว่า3ตัวแปรขึ้นไป
ปัญหาที่ได้รับมอบหมายReal-world CSPs
=เช่นสิ่งที่สอนในชั้นเรียน
ปัญหา timetabling
=เช่น ระดับที่จะถูกนำเสนอเมื่อใดและที่ไหน
- การจัดตารางเวลาการขนส่ง
- การตั้งเวลาโรงงาน
- ขอให้สังเกตว่าปัญหาที่แท้จริงของโลกจำนวนมากที่เกี่ยวข้องกับมูลค่าที่แท้จริงตัวแปร
ค้นหาสูตรมาตรฐาน (เพิ่มขึ้น)Standard search formulation (incremental)
วิธีธรรมดาในการค้นหา
สถานะจะถูกกำหนดโดยค่าที่ได้รับมอบหมายเพื่อให้ห่างไกล
สถานะจะถูกกำหนดโดยค่าที่ได้รับมอบหมายเพื่อให้ห่างไกล
- สถานะเริ่มต้น: การกำหนดที่ว่างเปล่า {}
- ฟังก์ชั่นตัวตายตัวแทน (การกระทำ): กำหนดค่าให้ตัวแปรที่ไม่ได้กำหนดว่าไม่ขัดแย้งกับที่ได้รับมอบหมายในปัจจุบัน
-->ล้มเหลวถ้าไม่มีการกำหนดตามกฎ
- การทดสอบเป้าหมาย: การกำหนดปัจจุบันเสร็จสมบูรณ์
- ค่าใช้จ่ายในเส้นทาง: ค่าใช้จ่ายคงที่ (เช่น 1) สำหรับทุกขั้นตอนนี้จะเหมือนกันสำหรับ CSPs ทั้งหมด
วิธีการแก้ปัญหาทุกคนจะปรากฏขึ้นที่ระดับความลึก n กับตัวแปร n
-->ใช้การค้นหาความลึกแรก
ย้อนรอยการค้นหา (Backtracking search)
- ค้นหาความลึกเป็นครั้งแรกสำหรับ CSPs กับการกำหนดตัวแปรเดียวที่เรียกว่าการค้นหาย้อนรอย(backtracking search)
- เลือกค่าตัวแปรหนึ่งที่เวลาและย้อนรอยเมื่อตัวแปรมีค่าไม่เหลือทางกฎหมายที่จะกำหนด
- ค้นหา backtracking เป็นอัลกอริทึมไม่รู้ขั้นพื้นฐานสำหรับ CSPs
ย้อนรอยการปรับปรุงประสิทธิภาพ(Improving backtracking efficiency)
- วิธีการใช้งานทั่วไปมีความเร็วมากในการรับ:
- ซึ่งตัวแปรควรจะกำหนดต่อไปหรือไม่
- ในสิ่งที่เรียงลำดับตามค่าที่พยายาม?
- เราสามารถตรวจสอบความล้มเหลวที่หลีกเลี่ยงไม่ได้ในช่วงต้น?
ตัวแปรที่จำกัดมากที่สุด
ตัวแปรที่จำกัดมากที่สุด:เลือกตัวแปรที่มีค่าน้อยที่สุดตามกฎหมายที่
-a.k.a. ค่าขั้นต่ำที่เหลืออยู่ (MRV) การแก้ปัญหา
- หากมีตัวแปร X กับค่าศูนย์ตามกฎหมายที่เหลือ แก้ปัญหา MRV จะเลือก X และความล้มเหลวที่จะถูกตรวจพบ ทันทีที่หลีกเลี่ยงการค้นหาจุดหมายผ่านอื่น ๆ ตัวแปรซึ่งท้ายที่สุดก็จะล้มเหลวต่อไป
- ส่วนใหญ่ constraining ตัวแปร (หรือปริญญาแก้ปัญหา)
- เลือกตัวแปรที่มีข้อ จำกัด มากที่สุดในตัวแปรที่เหลือ
- พยายามที่จะลดปัจจัยที่แตกแขนงเกี่ยวกับทางเลือกในอนาคต
-จะมีประโยชน์เป็นผูกเบรกหลัง MRV แก้ปัญหา
ค่า constraining น้อย(Least constraining value)
Given ตัวแปรเลือกค่า constraining น้อย:- the หนึ่งที่ออกกฎทางเลือกน้อยที่สุดสำหรับตัวแปรที่เหลือ
It พยายามที่จะออกจากความยืดหยุ่นสูงสุดสำหรับการกำหนดตัวแปรที่ตามมา
การตรวจสอบไปข้างหน้า(Forward checking)
เมื่อใดก็ตามที่ตัวแปร X ที่มีการกำหนดขั้นตอนการตรวจสอบไปข้างหน้ามีลักษณะที่แต่ละ Y ตัวแปรที่ไม่ได้กำหนดที่เชื่อมต่อกับ X โดยข้อ จำกัด และลบจากY’s domainค่าใด ๆ ที่ไม่สอดคล้องกับค่าที่เลือกสำหรับปX.
การตรวจสอบไปข้างหน้า(Forward checking)
ความคิด:
- รูปที่1
- ติดตามเหลือค่าตามกฎสำหรับตัวแปรที่ไม่ได้กำหนด
- ยุติ (และ backtrack) ค้นหาเมื่อตัวแปรใดที่มีทางและค่าตามกฎ
- รูปที่2
- ติดตามเหลือค่าตามกฎสำหรับตัวแปรที่ไม่ได้กำหนด
- ยุติ (และ backtrack) ค้นหาเมื่อตัวแปรใดที่มีทางและค่าตามกฎ
- รูปที่3
- ติดตามเหลือค่าตามกฎสำหรับตัวแปรที่ไม่ได้กำหนด
- ยุติ (และ backtrack) ค้นหาเมื่อตัวแปรใดที่มีทางและค่าตามกฎ
- รูปที่4
- ติดตามเหลือค่าตามกฎสำหรับตัวแปรที่ไม่ได้กำหนด
- ยุติ (และ backtrack) ค้นหาเมื่อตัวแปรใดที่มีทางและค่าตามกฎ
- รูปที่5
- เมื่อเทียบกับไม่มีการตรวจสอบไปข้างหน้า: ตรวจพบปัญหาหลังจากที่ขั้นตอนที่5ได้รับมอบหมาย
การขยายพันธุ์อย่างจำกัด(Constraint propagation)
- การตรวจสอบการส่งต่อแพร่กระจายข้อมูลจากได้รับมอบหมายให้ตัวแปรที่ไม่ได้กำหนด แต่ไม่ได้ให้ตรวจสอบเริ่มต้นสำหรับความล้มเหลวทั้งหมด:
- NT และ SA ไม่สามารถทั้งเป็นสีฟ้า!
- การขยายพันธุ์อย่างจำกัด(Constraint propagation) ซ้ำบังคับใช้ข้อจำกัดในประเทศ มันแพร่กระจายผลกระทบของข้อจำกัด ในตัวแปรหนึ่งบนตัวแปรอื่น ๆ
Arc consistency(สอดคล้อง)
- รูปแบบที่ง่ายของการขยายพันธุ์ที่ทำให้โค้งแต่ละที่สอดคล้อง (consistent)กัน
- X--> Y ถ้ามีความสอดคล้อง
- สำหรับทุกค่า x ของ X มีบาง y ที่ได้รับอนุญาต
- การตรวจสอบความArc consistency ต้องใช้ซ้ำ ๆ จนกระทั่งไม่มีความไม่สอดคล้องกันมากขึ้นยังคงอยู่
- ถ้า x สูญเสียค่าใกล้เคียงของ X จะต้องมีการเดินทาง
- เช่นเมื่อ V สูญเสียค่าจะต้องตรวจสอบค่าของNSW และ SA’s จากนั้นจะต้องตรวจสอบค่าของNSW’s and SA’s และอื่น ๆ
simple and clear.Keep updating Artificial Intelligence Online Training
ตอบลบ