กราฟอันประกอบด้วยปมและเส้นเชื่อมที่เชื่อมคู่ปมที่มีความสัมพันธ์กัน เป็นตัวแบบในการจำลองปัญหามากมาย เมื่อเราสามารถจำลองปัญหาที่สนใจด้วยกราฟ จะทำให้มองการแก้ไขปัญหาได้อย่างมีระบบ โดยอาศัยฐานความรู้ทางทฏษฎีกราฟที่มีผู้วิจัยค้นคว้ากันนาน บทนี้ขอนำเสนออัลกอริทึมพื้นฐานที่ใช้กับกราฟ อันได้แก่ การท่องไปตามปมต่าง ๆ ในกราฟสองวิธีคือ การค้นตามแนวกว้างและตามแนวลึก การทดสอบคุณสมบัติการเชื่อมต่อกันของปมในกราฟ การหาต้นไม้ทอดข้ามต่ำสุดของกราฟ และการหาวิถีสั้นสุดระหว่างปมในกราฟ อัลกอริทึมพื้นฐานต่าง ๆ เหล่านี้ได้รับนำไปประยุกต์ใช้แก้ไขปัญหาอื่น ๆ ที่จำลองด้วยกราฟมากมาย
การค้นในปริภูมิสถานะ
ปัญหาต่างๆ ที่เราได้ศึกษาและออกแบบอัลกอริทึมกันมา เป็นปัญหาที่มีอัลกอรึมที่หาคำตอบได้รวดเร็ว แต่ก็มีมากมายหลากหลายปัญหาในทางปฏิบัติที่คำตอบของปัญหาได้มาจากวิธีแจกแจงและตรวจสอบผลเฉลย แต่การแจกแจงและตรวจสอบเช่นนี้ใช้เวลานานมาก (แม้กับข้อมูลขาเข้าที่มีปริมาณไม่มาก) ดังนั้นจึงไม่ควรอย่างยิ่งที่จะแจกแจงและตรวจสอบทุก ๆ กรณี การแจกแจงและตรวจสอบนั้น เปรียบได้กับ การค้นคำตอบในปริภูมิสถานะผลเฉลยที่มีขนาดใหญ่ จะค้นไปทางไหน อย่างไร หากกระทำอย่าง "ฉลาด" ย่อมพบคำตอบได้เร็วขึ้น บทนี้นำเสนอกลวิธีการค้นคำตอบในปริภูมิสถานะ ได้แก่ การค้นตามแนวลึกและแนวกว้าง ซึ่งสามารถเพิ่มกลวิธีการย้อนรอย (backtracking) ที่มีฟังก์ชันการตรวจสอบความมีแววของปมสถานะ ถ้าไม่มีแววว่าจะนำไปสู่คำตอบ ก็อย่าค้นต่อจากปมนั้น ผนวกกับการค้นตามต้นทุนต่ำสุด ที่จะนำการค้นไปสู่คำตอบได้ถูกทิศถูกทาง นอกจากนี้ยังมีกลวิธีขยายและจำกัดเขต (branch and bound) ที่ใช้กับปัญหาการหาคำตอบดีสุดที่เรียกว่า optimization problems
ไม่มีความคิดเห็น:
แสดงความคิดเห็น