อัลกอริทึมแบบผสม (การแก้ปัญหาข้อจำกัด)

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

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

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

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

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

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

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

อีกทางเลือกหนึ่งในการลดเวลาการทำงานของการค้นหาคือการเพิ่มภาระให้กับส่วนของการอนุมาน โดยเฉพาะอย่างยิ่ง การอนุมานจะมีประสิทธิภาพค่อนข้างดีแม้ว่ากราฟของปัญหาจะไม่ใช่กราฟแบบฟอเรสต์ แต่เป็นกราฟที่มีความกว้างที่เหนี่ยวนำได้น้อย สามารถใช้ประโยชน์จากจุดนี้ได้โดยการค้นหาในชุดของตัวแปรที่ไม่ใช่ชุดตัดวงจร แต่เมื่อลบออกแล้ว ปัญหาจะมีค่าความกว้างที่เหนี่ยวนำได้จำกัดด้วยค่าบางค่าชุดตัวแปรดังกล่าวเรียกว่าชุดตัด -cutset ของปัญหา ${\displaystyle b}$${\displaystyle b}$

ความกว้างที่เกิดขึ้นของกราฟหลังจากลบชุดตัวแปรออกไปเรียกว่าความกว้างที่เกิดขึ้นที่ปรับแล้วดังนั้น ความกว้างที่เกิดขึ้นที่ปรับแล้วเมื่อเทียบกับเซตตัดจะมีค่าเท่ากับ เสมอการหาเซตตัดที่มีขนาดเล็กที่สุดโดยทั่วไปทำได้ยาก อย่างไรก็ตามสามารถหาเซตตัดที่มีขนาดไม่เล็กที่สุดได้ง่ายสำหรับลำดับของตัวแปรที่กำหนดไว้ โดยเฉพาะอย่างยิ่ง เซตตัดดังกล่าวจะทำให้กราฟที่เหลืออยู่มีความกว้างที่จำกัดโดยตามลำดับของตัวแปรนั้นๆ ${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$

อัลกอริทึมสำหรับการค้นหาเซตตัดดังกล่าวจะดำเนินการโดยเลียนแบบขั้นตอนการค้นหากราฟเหนี่ยวนำของปัญหาตามลำดับของตัวแปรที่พิจารณา (ขั้นตอนนี้ดำเนินการจากโหนดสุดท้ายในลำดับไปยังโหนดแรก โดยเพิ่มขอบระหว่างโหนดแม่ที่ไม่เชื่อมต่อกันทุกคู่ของทุกโหนด) เมื่อใดก็ตามที่ขั้นตอนนี้พบหรือสร้างโหนดที่มีโหนดแม่มากกว่า โหนดนั้นจะถูกลบออกจากกราฟและเพิ่มลงในเซตตัด ตามคำจำกัดความ กราฟที่ได้จะไม่มีโหนดใดที่มีความกว้างมากกว่าและเซตของโหนดที่ถูกลบจึงเป็นเซตตัด -cutset ${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$

อีกทางเลือกหนึ่งนอกเหนือจากการใช้อัลกอริธึมนี้คือ การให้การค้นหาประเมินตัวแปร แต่ตรวจสอบในแต่ละขั้นตอนว่ากราฟที่เหลืออยู่เป็นป่าหรือไม่ และทำการอนุมานหากเป็นเช่นนั้น กล่าวอีกนัยหนึ่ง แทนที่จะหาชุดตัวแปรในตอนเริ่มต้นและใช้เฉพาะตัวแปรเหล่านั้นในระหว่างการค้นหา อัลกอริธึมจะเริ่มต้นเหมือนกับการค้นหาแบบปกติ ในแต่ละขั้นตอน หากตัวแปรที่กำหนดไว้ก่อให้เกิดเซตตัดของปัญหา จะทำการอนุมานเพื่อตรวจสอบความสามารถในการทำให้เป็นจริง วิธีนี้เป็นไปได้เพราะการตรวจสอบว่าชุดโหนดที่กำหนด เป็น เซตตัดสำหรับค่าคงที่ หรือ ไม่นั้นเป็นปัญหาพหุนาม ${\displaystyle b}$${\displaystyle b}$${\displaystyle b}$

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

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

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

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