การบังคับ
การบังคับ
เทคนิคที่เกี่ยวข้อง
ใช่การเดาหรือไม่? ข้อถกเถียงเกี่ยวกับ โซ่บังคับ
โซ่บังคับ ไม่ใช่การเดาเมื่อใช้เป็นเทคนิคพิสูจน์ คุณจะตรวจสอบทุกทางเลือกจากจุดเริ่มต้นที่เลือกไว้ชั่วคราว ขยายแต่ละทางอย่างมีเหตุผล และเก็บเฉพาะข้อสรุปที่ทุกทางเลือกสนับสนุน หรือข้อสรุปที่บังคับโดยข้อขัดแย้ง
ความแตกต่างสำคัญจากเดาคือการมีความมุ่งมั่น ในการเดา จะเลือกทางเดียวแล้วดำเนินต่อไปโดยสมมติว่าเป็นจริง แต่ในโซ่บังคับจะเปรียบเทียบทางเลือกที่เกี่ยวข้องทั้งหมดจากจุดเริ่มต้น และดำเนินการเฉพาะเมื่อการเปรียบเทียบพิสูจน์อะไรบางอย่างได้
โซ่บังคับ ไม่หรูหรานักเมื่อเปรียบเทียบกับเทคนิคที่ใช้รูปแบบ แต่ข้อสรุปของมันถูกพิสูจน์ได้ว่าถูกต้องเมื่อทุกทางเลือกได้รับการตรวจสอบอย่างถูกต้อง
ช่อง โซ่การบังคับ
เริ่มจากช่องที่มีค่าสองค่า ช่อง {A, B} วิเคราะห์ผลลัพธ์จากแต่ละทางเลือก แล้วเปรียบเทียบผลลัพธ์
ขัดแย้ง: ทางเลือกหนึ่งไม่ถูกต้อง ดังนั้น ช่อง ต้องเป็นค่าอีกค่าหนึ่ง
การรวมกันที่ตำแหน่ง: ทั้งสองทางเลือกบังคับให้ใส่ตัวเลขเดียวกันลงในช่อง ช่อง ที่อยู่ไกลกัน
การรวมกันที่การตัดออก: ทั้งสองทางเลือกตัดค่าเดียวกันออกจากรูปแบบ ช่อง ที่เหมือนกัน
โซ่การบังคับภูมิภาค (โซ่การบังคับตัวเลข)
เริ่มจากตำแหน่ง 2-3 ของตัวเลขในกลุ่ม สำรวจแต่ละตำแหน่งเป็นสาขา ใช้ประเภทการอนุมานสามประเภทเดียวกัน
ช่อง การบังคับมีประสิทธิภาพเมื่อเซลล์ที่มีค่าสองค่ามีผลกระทบอย่างกว้างขวาง ภูมิภาคการบังคับมีประสิทธิภาพเมื่อตำแหน่งของตัวเลขมีผลกระทบต่อเนื่องกันอย่างรุนแรง
การเชื่อมต่อแรงดัน: การขยายจำนวนกิ่ง
ช่อง การเชื่อมต่อการบังคับ: ช่องที่มีตัวเลือก 3-6 ตัว ช่องการบังคับตามภูมิภาค: ช่องที่มีตำแหน่ง 4-6 ตำแหน่งสำหรับตัวเลขหนึ่งตัว จำนวนกิ่งก้านมากขึ้น ใช้พลังงานมากขึ้น แต่สามารถค้นหาข้อสรุปที่ โซ่บังคับ ไม่สามารถทำได้
ตรรกะเหมือนกัน เพียงแค่จำนวนกิ่งก้านที่แตกต่างกัน
เครื่องยนต์การแพร่กระจาย
แต่ละสาขาจะแพร่กระจายผ่านตัวเลือกเดี่ยวที่มองเห็นได้ ตัวเลือกเดี่ยวที่ซ่อนอยู่ ผู้สมัครที่ถูกล็อก และคู่เดี่ยว ซ้ำไปซ้ำมาจนกว่าจะคงที่ หนึ่งสมมติฐานสามารถส่งผลต่อขั้นตอนกลางหลายสิบขั้นตอนทั่วทั้งบอร์ด
เมื่อสองสาขาไปสู่ข้อสรุปเดียวกันผ่านเส้นทางที่แตกต่างกันอย่างสิ้นเชิง การรวมตัวกันนี้พิสูจน์ได้ว่าข้อสรุปมีความแน่นอน
สามประเภทของการอนุมาน
ขัดแย้ง: Zweig สร้างสถานะที่ไม่ถูกต้อง สมมติฐานนี้จึงเป็นเท็จ พบบ่อยที่สุด
การรวมตัวที่ตำแหน่ง: ทุกสาขาบังคับให้ใส่ตัวเลขเดียวกันลงในช่องเดียวกัน ช่อง พบน้อยกว่าแต่ชัดเจน
การรวมตัวที่การตัดออก: ทุกสาขาตัดตัวเลือกเดียวกันออกจากรูปเดียวกัน ช่อง ประเภทที่ซับซ้อนที่สุด
ใช้เทคนิคบังคับเมื่อใด
ทางเลือกสุดท้ายที่ใช้ได้ ใช้หลังจากเทคนิคตามรูปแบบและโซ่ที่สะอาดล้มเหลว
โซ่บังคับ ที่มีกิ่ง 2-3 ทางจะถูกลองก่อน สำหรับการเชื่อมต่อที่บังคับ (Forcing Nets) ที่มีกิ่ง 3-6 ทางจะมีต้นทุนสูงกว่า และมักถูกเก็บไว้ใช้ในภายหลัง ทั้งสองวิธีอยู่ในระดับ 12 (ขั้นสูงมาก)
สำหรับโปรแกรมแก้ปัญหาคอมพิวเตอร์ การบังคับที่มีข้อจำกัด (bounded forcing) เป็นเครื่องมือพิสูจน์ที่ทรงพลัง แต่ไม่ได้สมบูรณ์โดยอัตโนมัติ ความสมบูรณ์จะเกิดขึ้นก็ต่อเมื่อการค้นหาได้ขยายไปไกลพอเพื่อครอบคลุมสมมติฐานที่ต้องการ ซึ่งจะเข้าใกล้การกลับไปทบทวนทั้งหมด (exhaustive backtracking) ในทางปฏิบัติ การบังคับที่มีข้อจำกัดถือว่าเป็นการค้นหาตรรกะที่ควบคุมได้ มากกว่าการรับประกันว่าเครื่องมือที่มีความลึกคงที่สามารถแก้ปัญหาทุกข้อได้
ข้อสังเกตทางปรัชญาเกี่ยวกับความงดงามและความสมบูรณ์
เทคนิคที่อิงจากรูปแบบช่วยเปิดเผยความสัมพันธ์ทางโครงสร้าง และมีความสวยงามมากกว่า แต่ก็มีปริศนาที่ถูกต้องซึ่งต้องใช้ตรรกะระดับการบังคับ เทคนิคการบังคับเป็นเครื่องมือป้องกันที่จับทุกปัญหาที่เทคนิคแบบรูปแบบไม่สามารถจัดการได้
แนวทางที่ให้ความพึงพอใจที่สุด: ลองใช้เทคนิคแบบรูปแบบทั้งหมดก่อน แล้วจึงใช้การบังคับก็ต่อเมื่อปัญหาต้องการจริงๆ
สรุป
โซ่บังคับ และการเชื่อมต่อแบบบังคับอยู่ในกลุ่มเทคนิคตรรกะที่ทรงพลังที่สุด ระดับ 12 (ขั้นสูงสุด) พวกเขาจะสำรวจทุกทางเลือกจากจุดเริ่มต้นที่เลือกไว้ ขยายผลลัพธ์ และเปรียบเทียบผลลัพธ์ ข้อสรุปเกิดจากการขัดแย้ง การรวมกันของตำแหน่ง หรือการรวมกันของการตัดออก พวกเขาเป็นทางเลือกสุดท้ายก่อนการกลับไปทีละขั้นแบบดิบ ถ้าขยายโดยไม่มีข้อจำกัดทางปฏิบัติ จะกลายเป็นหลักฐานการค้นหาทั้งหมด แต่การใช้งานแบบมนุษย์ที่มีข้อจำกัดยังคงเป็นเทคนิคขั้นสูงที่มีเป้าหมายชัดเจน
เทคนิคที่เกี่ยวข้อง