Constraint Satisfaction Problem (CSP) เป็นโจทย์ประเภทต้องลองไปเรื่อย ๆ เพื่อค้นหาคำตอบ
โดยรูปแบบที่จะให้ลองมีจำกัด (ไม่ว่าจะมากแค่ไหนก็ตาม)
โดยที่มีข้อกำหนดบางอย่างที่บอกว่าคำตอบนั้นถูกต้อง
ตัวอย่างของ CSP เช่น Sudoku, 8 Queens Puzzle, Einstein's Puzzle

วิธี Solve ปัญหาประเภทนี้แบบง่ายที่สุด เราเรียกว่า Generate and Test (GT)
GT เป็นการสร้างคำตอบก่อน แล้วค่อยทดสอบว่าถูกต้องหรือเปล่า
GT จะเหมาะกับปัญหาประเภท Search space ไม่ใหญ่มาก
ประมาณว่าสั่งแล้วคำตอบต้องออกมาภายในไม่กี่วิ
ผมเคยใช้ GT ตอน Solve 180 IQ
คือ เอาตัวเลขทั้งหมดมาบวก ลบ คูณ หาร กันให้ครบทุกรูปแบบ
แล้วค่อยตรวจดูว่าคำตอบถูกหรือเปล่า

บางที GT ก็ใช้กับ Search space ที่ใหญ่มาก
ถ้าปัญหาไม่สามารถลด Search space ได้ ก็ช่วยไม่ได้ที่ต้องใช้ GT
เช่น จะ Hack password วิธีการที่ลองทีละตัวอักษรเพื่อหาว่า Password ไหนเข้าได้ ก็เป็น GT
ซึ่งบางครั้ง GT มัน Run นานมาก ๆ เค้าเลยเรียกกันว่า Bruteforce (แปลว่า บ้าพลัง )

GT แบบที่พัฒนาขึ้น เรียกกันว่า Backtracking (BT)
BT ลด Search space โดยการ Test ขณะสร้างคำตอบ
ปัญหา CSP ส่วนใหญ่ จะเหมาะกับ BT เพราะ BT ตัด Search space ได้มากพอแล้วในหลาย ๆ กรณี แถมใช้ Memory น้อย
ผมใช้ BT บ่อยมาก เช่น Solve 8 queens, Impossible puzzle, Knight tour
(BT ในชีวิตจริงก็พวกจัดตารางการผลิต, การวาง Layout เพื่อให้ผลิตได้มากที่สุด, การจัด Package ใส่ Container)
ซึ่งวิธีการหาคำตอบที่ผมเขียนด้วย Linq
ใน 180 IQ ซึ่งเป็น GT ผมมีแค่ Linq Statement เดียวก็ Solve ได้แล้ว
แต่ BT เช่น Impossible puzzle ต้องใช้หลาย Linq ประกอบกัน
หรือใน 8 queens กับ Knight tour ต้องใช้ Recursive Function ในการหาคำตอบ
สรุปคือ BT เร็วกว่า แต่ยุ่งยากกว่า GT
(ผมเคยเขียน Class เพื่อ ลดความยุ่งยากของ BT ลอง Download ไปใช้ดู class ชื่อ Backtracker)


(รูปแบบการใช้ BT solve 4 queens รูปจาก Guide to constraint programming)

รูปแบบที่ Advance กว่า BT เรียกว่า Forward Checking (FC)
ต่างจาก BT ตรงที่ ขณะที่เลือกตัวเลือกเพื่อหาคำตอบ FC จะตัด Choice ที่ไม่ใช่ของตัวที่ยังไม่ได้เลือกทันที
เช่น Sudoku ถ้าคุณอาจจะเขียนเลข 1-9 ตัวเล็ก ๆ ในช่องที่ยังไม่ได้ใส่ตัวเลข
และสมมติคุณเติมเลข 1 เข้าไปในช่องแรก คุณสามารถตัดเลข 1 ออกจากช่องในแถวเดียวกัน
รูปแบบการตัด Search space ของ FC มีหลายแบบ ลองไปอ่านต่อดู ที่นี่
หลัก ๆ คือ ตัดตัวเลือกที่ไม่ใช่ออกให้เร็วที่สุด อาจจะตัดตั้งแต่แรก หรือตัดขณะเลือกตัวเลือกปัจจุบัน

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


(รูปแบบการใช้ FC solve 4 queens รูปจาก Guide to constraint programming)

ยังมีที่ Advance กว่า FC คือ Lookahead (LA)
LA จะทำการ Test Consistency ของตัวเลือกถัดไปด้วย
เมื่อ Test แล้ว ก็จะเจอทางตันเร็วขึ้นอีก
และเพราะว่า LA มีการ Test ตัวเลือกด้วย เลยสามารถทำ Value Ordering ได้
โดยส่วนใหญ่จะเลือก Value ที่มี Conflict ที่น้อยที่สุดมาทำก่อน
(ผมเขียน Class สำหรับทำ Lookahead แถมใช้ง่ายด้วย ลองอ่าน Post เก่า ดูครับ )


(รูปแบบการใช้ FC solve 4 queens รูปจาก Guide to constraint programming)

คุณคิดว่า LA นี่สุด ๆ หรือยังครับ 
สำหรับ Search space ที่กว้างมาก ๆๆๆ
ต่อให้ใช้ LA ก็ไม่สามารถ หาคำตอบได้ในเวลาที่ต้องการ
คุณมี 2.75 วิธีในการหาคำตอบ

1. Heuristics คือ การใช้ Weight ในการจัดลำดับคำตอบ
    ในเวลาที่จำกัด Heuristics จะได้ คำตอบที่ดีที่สุดในตอนนั้นออกมา แต่ไม่ Guarantee ว่าเป็นคำตอบที่ดีที่สุด
    (เรื่องของ Heuristics ยังมีอีกเยอะ ไว้จะเล่าให้ฟัง)
2. Optimization คือ การใช้ Math หรือ Algorithm (ที่เป็น PTIME) ในการช่วย Solve
    ข้อจำกัดคือ คุณต้องสามารถ Reduce ปัญหา ให้เป็น PTIME ให้ได้
    (ไว้จะเล่าให้ฟังเหมือนกัน แล้วคุณจะรู้ว่า Math ที่เรียนมา มันไม่สูญเปล่า )
2.5 Dynamic Programming คือ การ Reduce ปัญหาเป็น Sub problem แล้วใช้เทคนิค Memoization ในการ Optimize
    ที่ไม่เป็นข้อ 3 เพราะ DP เป็น Subset ของ Optimization
    (เรื่องของ DP ก็อยากเขียนมาตั้งนานละ แต่ในบทความเก่า ๆ ก็มีใช้ DP อยู่หลายตอนนะ 1 2)
2.75 Solve P=NP ก็แค่พิสูจน์ให้ได้ว่า P=NP แค่นี้แหละ คุณก็จะสามารถ Reduce ปัญหาทั้งหมดให้เป็น PTIME
    แล้วก็รับเงิน 1 ล้านเหรียญ เป็นรางวัล 
    (ถ้าคุณ Solve ได้ 1 ล้านเหรียญ นี่แค่ค่าขนมแน่นอน)

Create Date : 09 สิงหาคม 2553
Last Update : 17 ตุลาคม 2553 1:25:42 น.		3 comments
Counter : 3963 Pageviews.
Share Tweet