ลดพื้นที่ค้นหาอย่างชาญฉลาด

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

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

ตรึงสมาชิกตัวแรก แล้วใช้ การค้นหาแบบทวิภาค หรือแฮชเพื่อหาสมาชิกคู่ของมัน วิธีนี้เปลี่ยนการไล่ตรวจแบบ O(n ยกกำลังสอง) ให้เป็นประมาณ O(n log n)

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

การเรียงลำดับก่อนมักทำให้คุณ หยุด ลูปได้เร็ว เมื่อค่าต่าง ๆ ผ่านเกณฑ์ที่กำหนด คุณก็ทราบว่าส่วนที่เหลือไม่สามารถช่วยได้

หากการสลับสมาชิกสองตัวให้ผลลัพธ์เหมือนเดิม ให้ค้นหาเพียง ลำดับ เดียว การนับแต่ละกรณีเพียงครั้งเดียวอาจลดงานลงได้ครึ่งหนึ่งหรือมากกว่านั้น

แบ่งสมาชิกออกเป็นสองครึ่ง ไล่ตรวจแต่ละครึ่ง แล้ว รวม ผลลัพธ์เข้าด้วยกัน วิธีนี้ลดการค้นหาจาก 2^n เหลือการทำงานประมาณ 2^(n/2)

หากปัญหาย่อยเดิมปรากฏขึ้นอีกครั้ง ให้จัดเก็บผลลัพธ์ไว้แล้ว นำกลับมาใช้ซ้ำ การจดจำผลลัพธ์จะตัดแขนงที่ต้องทำซ้ำทั้งหมดออกจากการค้นหา

คำนวณ ขอบเขต ในกรณีดีที่สุดสำหรับแขนงหนึ่ง หากแม้แต่กรณีที่ดีที่สุดของแขนงนั้นยังแพ้ ก็ข้ามแขนงนั้นไปทั้งหมดเพื่อประหยัดเวลา

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

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

ลดการค้นหาด้วยการ ตรึง ตัวแปร ตัดแขนงที่ไม่มีทางชนะ ใช้ประโยชน์จากสมมาตร หรือค้นหาจากตรงกลาง ทั้งนี้ต้องทำให้การตัดทอนทุกครั้งปลอดภัย 🚀