การค้นหาในแนวลึกแบบวนเพิ่มความลึก

ลักษณะทั่วไป

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

ขั้นตอนวิธีการทำงาน

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

รหัสเทียม

IDDFS(ราก, เป้าหมาย){
 ความลึก = 0
 ตราบใดที่ (ยังไม่พบเป้าหมาย){
   เป้าหมาย = DLS(ราก, เป้ามหมาย, ความลึก)
   ความลึก = ความลึก + 1
   }
 คืนค่า เป้าหมาย
}

DLS(ปม, เป้าหมาย, ความลึก){
 ถ้า ( ความลึก >= 0 ){
   ถ้า ( ปม == เป้าหมาย )
     คืนค่า ปม
      สำหรับแต่ละปมลูกที่ถูกค้น(ปม)
        DLS(ปมลูก, เป้าหมาย, ความลึก-1)
  }
}

ประสิทธิภาพด้านพื้นที่ (Space complexity)

ประสิทธิภาพด้านพื้นที่ (Space complexity) ของการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) เป็น :O(bd) ซึ่ง b คือ ปัจจัยการแตกกิ่ง และ d คือ ความลึกของเป้าหมายที่ต้องการค้นหา ซึ่งการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) นั้นอาจจะต้องค้นปมเดิมซ้ำๆหลายครั้ง ซึ่งอาจจะทำให้สิ้นเปลืองพื้นที่ แต่ในความจริงแล้วมันก็ไม่ได้สิ้นเปลืองขนาดนั้น เนื่องจากปมต่างๆของต้นไม้ส่วนใหญ่อยู่ในระดับล่างๆ ทำให้การค้นหาปมต่างๆในต้นไม้ที่อยู่ระดับบนหลายๆครั้งไม่มีผล

การได้คำตอบที่เหมาะสม (Optimality)

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

ความสมบูรณ์ (Completeness)

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

การนำไปประยุกต์ใช้

มีขั้นตอนวิธีที่คล้ายกับ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) คือ iterative lengthening search ซึ่งเป็นขั้นตอนวิธีที่มีการเพิ่มน้ำหนักของเส้นทาง (edge) ของระดับความลึกในชั้นต่างๆ ซึ่งการซ้ำการค้นปมๆต่างในระดับต่างๆนั้นจะมีค่าน้ำหนักบนเส้นทาง (edge) ไปยังปมต่างๆเหล่านั้นเพิ่มขึ้นด้วย เพราะฉะนั้นเป้าหมายแรกที่ได้จะเป็นเส้นทางที่มีค่ารวมของน้ำหนักบนเส้นทางดีที่สุด คือถูกที่สุดนั่นเอง แต่ iterative lengthening ก็ยังมีปัญหาอยู่มากทำให้ เป็นวิธีการค้นหาที่ยังไม่ดีเท่าการค้นเชิงลึกจำกัดแบบวนเพิ่มความลึก
การค้นหาแบบ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) จะใช้ได้ในงานหลายๆ ด้าน เช่น ในเรื่องเกี่ยวกับการทำปัญญาประดิษฐ์ เช่นการจำลองการเล่นหมากรุก
การค้นหาแบบ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) จะนำไปใช้ใน game tree เช่น killer heuristicand , alpha-beta pruning (ขั้นตอนวิธีที่ใช้ลดการหาที่ไม่จำเป็น) ซึ่งมากไปด้วยการประมาณความถูกต้องของคะแนนของปมต่างๆกันที่ปลายทางความลึกที่สามารถเกิดขึ้นได้ และการค้นหาจะเสร็จได้รวดเร็ว

สรุป

Iterative Deepening Depth-First Search (IDDFS) หรือ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก เป็นขั้นตอนวิธีที่ดัดแปลงหรือพัฒนามากจากการค้นแบบจำกัดความลึก โดยอาศัยหลักการของขั้นตอนวิธีเชิงละโมบ ที่จะค่อยๆ หาคำตอบที่ต้องการจากเริ่มต้นที่กำหนดความลึกที่จะค้นหาไว้ที่ 0 แล้วเพิ่มค่าความลึกขึ้นไปเรื่อยๆ จนกว่าเราจะเจอเป้าหมายคำตอบต้องการได้