การบังคับ

การบังคับ

มาสเตอร์

ใช่การเดาหรือไม่? ข้อถกเถียงเกี่ยวกับ โซ่บังคับ

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

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

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

ช่อง โซ่การบังคับ

เริ่มจากช่องที่มีค่าสองค่า ช่อง {A, B} วิเคราะห์ผลลัพธ์จากแต่ละทางเลือก แล้วเปรียบเทียบผลลัพธ์

ขัดแย้ง: ทางเลือกหนึ่งไม่ถูกต้อง ดังนั้น ช่อง ต้องเป็นค่าอีกค่าหนึ่ง

การรวมกันที่ตำแหน่ง: ทั้งสองทางเลือกบังคับให้ใส่ตัวเลขเดียวกันลงในช่อง ช่อง ที่อยู่ไกลกัน

การรวมกันที่การตัดออก: ทั้งสองทางเลือกตัดค่าเดียวกันออกจากรูปแบบ ช่อง ที่เหมือนกัน

โซ่การบังคับภูมิภาค (โซ่การบังคับตัวเลข)

เริ่มจากตำแหน่ง 2-3 ของตัวเลขในกลุ่ม สำรวจแต่ละตำแหน่งเป็นสาขา ใช้ประเภทการอนุมานสามประเภทเดียวกัน

ช่อง การบังคับมีประสิทธิภาพเมื่อเซลล์ที่มีค่าสองค่ามีผลกระทบอย่างกว้างขวาง ภูมิภาคการบังคับมีประสิทธิภาพเมื่อตำแหน่งของตัวเลขมีผลกระทบต่อเนื่องกันอย่างรุนแรง

การเชื่อมต่อแรงดัน: การขยายจำนวนกิ่ง

ช่อง การเชื่อมต่อการบังคับ: ช่องที่มีตัวเลือก 3-6 ตัว ช่องการบังคับตามภูมิภาค: ช่องที่มีตำแหน่ง 4-6 ตำแหน่งสำหรับตัวเลขหนึ่งตัว จำนวนกิ่งก้านมากขึ้น ใช้พลังงานมากขึ้น แต่สามารถค้นหาข้อสรุปที่ โซ่บังคับ ไม่สามารถทำได้

ตรรกะเหมือนกัน เพียงแค่จำนวนกิ่งก้านที่แตกต่างกัน

เครื่องยนต์การแพร่กระจาย

แต่ละสาขาจะแพร่กระจายผ่านตัวเลือกเดี่ยวที่มองเห็นได้ ตัวเลือกเดี่ยวที่ซ่อนอยู่ ผู้สมัครที่ถูกล็อก และคู่เดี่ยว ซ้ำไปซ้ำมาจนกว่าจะคงที่ หนึ่งสมมติฐานสามารถส่งผลต่อขั้นตอนกลางหลายสิบขั้นตอนทั่วทั้งบอร์ด

เมื่อสองสาขาไปสู่ข้อสรุปเดียวกันผ่านเส้นทางที่แตกต่างกันอย่างสิ้นเชิง การรวมตัวกันนี้พิสูจน์ได้ว่าข้อสรุปมีความแน่นอน

สามประเภทของการอนุมาน

ขัดแย้ง: Zweig สร้างสถานะที่ไม่ถูกต้อง สมมติฐานนี้จึงเป็นเท็จ พบบ่อยที่สุด

การรวมตัวที่ตำแหน่ง: ทุกสาขาบังคับให้ใส่ตัวเลขเดียวกันลงในช่องเดียวกัน ช่อง พบน้อยกว่าแต่ชัดเจน

การรวมตัวที่การตัดออก: ทุกสาขาตัดตัวเลือกเดียวกันออกจากรูปเดียวกัน ช่อง ประเภทที่ซับซ้อนที่สุด

ใช้เทคนิคบังคับเมื่อใด

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

โซ่บังคับ ที่มีกิ่ง 2-3 ทางจะถูกลองก่อน สำหรับการเชื่อมต่อที่บังคับ (Forcing Nets) ที่มีกิ่ง 3-6 ทางจะมีต้นทุนสูงกว่า และมักถูกเก็บไว้ใช้ในภายหลัง ทั้งสองวิธีอยู่ในระดับ 12 (ขั้นสูงมาก)

สำหรับโปรแกรมแก้ปัญหาคอมพิวเตอร์ การบังคับที่มีข้อจำกัด (bounded forcing) เป็นเครื่องมือพิสูจน์ที่ทรงพลัง แต่ไม่ได้สมบูรณ์โดยอัตโนมัติ ความสมบูรณ์จะเกิดขึ้นก็ต่อเมื่อการค้นหาได้ขยายไปไกลพอเพื่อครอบคลุมสมมติฐานที่ต้องการ ซึ่งจะเข้าใกล้การกลับไปทบทวนทั้งหมด (exhaustive backtracking) ในทางปฏิบัติ การบังคับที่มีข้อจำกัดถือว่าเป็นการค้นหาตรรกะที่ควบคุมได้ มากกว่าการรับประกันว่าเครื่องมือที่มีความลึกคงที่สามารถแก้ปัญหาทุกข้อได้

ข้อสังเกตทางปรัชญาเกี่ยวกับความงดงามและความสมบูรณ์

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

แนวทางที่ให้ความพึงพอใจที่สุด: ลองใช้เทคนิคแบบรูปแบบทั้งหมดก่อน แล้วจึงใช้การบังคับก็ต่อเมื่อปัญหาต้องการจริงๆ

สรุป

โซ่บังคับ และการเชื่อมต่อแบบบังคับอยู่ในกลุ่มเทคนิคตรรกะที่ทรงพลังที่สุด ระดับ 12 (ขั้นสูงสุด) พวกเขาจะสำรวจทุกทางเลือกจากจุดเริ่มต้นที่เลือกไว้ ขยายผลลัพธ์ และเปรียบเทียบผลลัพธ์ ข้อสรุปเกิดจากการขัดแย้ง การรวมกันของตำแหน่ง หรือการรวมกันของการตัดออก พวกเขาเป็นทางเลือกสุดท้ายก่อนการกลับไปทีละขั้นแบบดิบ ถ้าขยายโดยไม่มีข้อจำกัดทางปฏิบัติ จะกลายเป็นหลักฐานการค้นหาทั้งหมด แต่การใช้งานแบบมนุษย์ที่มีข้อจำกัดยังคงเป็นเทคนิคขั้นสูงที่มีเป้าหมายชัดเจน