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

การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (iterative deepening depth-first search) หรือ IDDFS เป็นขั้นตอนวิธีสำหรับการค้นปริภูมิสถานะ (state space search) ที่อาศัยการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึกไปเรื่อยๆ จนถึงความลึก d เพื่อหาคำตอบที่ดีที่สุดซึ่ง d คือความลึกของสถานะคำตอบเป้าหมายนั้น ในแต่ละรอบของการวนค้นหาเป้าหมายนั้น ขั้นตอนวิธี IDDFS จะค้นเจอปม (node) ต่างๆในต้นไม้ค้นหา (search tree) ในลำดับเดียวกันกับแบบ การค้นหาเชิงลึก แต่ทำการสะสมไว้ว่า ปมที่ความลึกเท่าไหร่จะถูกค้นหา โดยการกระทำวิธีนี้สมมุติว่าต้นไม้ค้นหา เป็นต้นไม้บริบูรณ์ ซึ่งทำให้ได้ผลลัพธ์ที่มีประสิทธิภาพเทียบกับแบบการค้นหาตามแนวกว้าง
== ลักษณะทั่วไป ==
การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก เป็นขั้นตอนวิธีที่รวมการค้นหาตามพื้นที่แนวลึก และ การค้นหาตามพื้นที่แนวกว้างอย่างมีประสิทธิภาพ ขั้นตอนวิธีนี้จึงจะเป็นผลดีเมื่อค่าน้ำหนักของเส้นทาง (edge) การค้นหาไม่เป็นฟังก์ชันที่ลดลงตามความลึกของปมต่างๆ
== ขั้นตอนวิธีการทำงาน ==
การทำงานของขั้นตอนวิธีการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึกนี้จะเป็นการค้นหาตามแนวลึกโดยเริ่มต้นให้กำหนดความลึกที่ใช้ค้นหาเริ่มที่ 1 และเริ่มค้นหาในแนวกว้าง ถ้าการค้นหายังไม่เจอเป้าหมายหรือยังไม่พบคำตอบที่ต้องการ จะเพิ่มความลึกที่ใช้ในการค้นหาไปเรื่อยๆ โดยเพิ่มทีละ 1 จนพบเป้าหมายที่ต้องการ ซึ่งขั้นตอนวิธีนี้จะสามารถหาคำตอบที่ระยะทางสั้นสุดได้ คือ ความลึก (d) ของต้นไม้ค้นหาสั้นที่สุด
300px 330px 370px
== รหัสเทียม ==
IDDFS(ราก, เป้าหมาย){
ความลึก = 0
ตราบใดที่ (ยังไม่พบเป้าหมาย){
เป้าหมาย = DLS(ราก, เป้ามหมาย, ความลึก)
ความลึก = ความลึก + 1
}
คืนค่า เป้าหมาย
}
DLS(ปม, เป้าหมาย, ความลึก){
ถ้า ( ความลึก >= 0 ){
ถ้า ( ปม == เป้าหมาย )
คืนค่า ปม
สำหรับแต่ละปมลูกที่ถูกค้น(ปม)
DLS(ปมลูก, เป้าหมาย, ความลึก-1)
}
}
== คุณสมบัติ ==
=== ประสิทธิภาพด้านพื้นที่ (Space complexity) ===
ประสิทธิภาพด้านพื้นที่ (Space complexity) ของการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) เป็น :O(bd) ซึ่ง b คือ ปัจจัยการแตกกิ่ง และ d คือ ความลึกของเป้าหมายที่ต้องการค้นหา ซึ่งการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) นั้นอาจจะต้องค้นปมเดิมซ้ำๆหลายครั้ง ซึ่งอาจจะทำให้สิ้นเปลืองพื้นที่ แต่ในความจริงแล้วมันก็ไม่ได้สิ้นเปลืองขนาดนั้น เนื่องจากปมต่างๆของต้นไม้ส่วนใหญ่อยู่ในระดับล่างๆ ทำให้การค้นหาปมต่างๆในต้นไม้ที่อยู่ระดับบนหลายๆครั้งไม่มีผล
=== ประสิทธิภาพด้านเวลา (Time complexity) ===
ประสิทธิภาพด้านเวลา (Time complexity) ของ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) ในต้นไม้ที่มีความสมดุลจะมีค่าของประสิทธิภาพด้านเวลาเท่ากับการค้นหาตามแนวลึกเป็น :O(b^{d}) ซึ่งเป็นการค้นหาที่ใช้เวลานาน ในการวนค้นหาตามแนวความลึกนั้น ปมต่างๆในระดับหนึ่งจะมีการถูกค้น หนึ่งครั้ง และเมื่อเพิ่มระดับขึ้น ปมต่างๆที่ถูกค้นในระดับหนึ่งก็จะถูกค้นเพิ่มอีกครั้งหนึ่ง ขึ้นอยู่กับปมรากของต้นไม้ค้นหา ซึ่งปมรากของต้นไม้ค้นหานั้นจะถูกค้น d+1 ครั้ง ดังนั้น ผลรวมของจำนวนการค้นปมต่างๆในการวนค้นหาเชิงความลึกนั้นจะเป็น 
(d + 1)1 + (d)b + (d-1)b^{2} + \cdots + 3b^{d-2} + 2b^{d-1} + b^{d}
\sum_{i=0}^d (d+1-i)b^i
ถ้ากำหนดให้ b = 10 และ d = 5 จะได้
6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456
ส่วนแบบการค้นหาตามแนวลึก จะมีผลรวมของการค้นปมต่างๆเป็น
1 + b + b^{2} + \cdots + b^{d-2} + b^{d-1} + b^{d}
ถ้ากำหนดให้ b = 10 และ d = 5 จะได้
1 + 10 + 100 + 1,000 + …. + 100,000 = 111,111
จากทั้งหมดข้างต้นนั้น การวนค้นหาตามแนวลึก ที่เริ่มจากความลึก 1 ไปถึง ความลึก d จะมีการค้นปมของปมต่างๆ มากกว่าแบบการค้นหาตามแนวกว้าง หรือการค้นแบบจำกัดความลึก ประมาณ 11% ที่ความลึก d และ b = 10 โดยหากปัจจัยในการแตกกิ่งมีค่าสูงจะทำให้ การซ้ำกันของการค้นปมของสถานะที่อยู่ในระดับบนจะมีค่าต่ำแม้ว่าปัจจัยในการแตกกิ่งจะมีค่าเป็น 2 หรือ มากกว่า แต่ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึกจะทำการค้นหา 2 ครั้ง โดยต้องยังคงสภาพ การค้นหาตามแนวกว้างที่สมบูรณ์ หมายความได้ว่าประสิทธิภาพของเวลาการทำงานของการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึกยังมีค่า O(bd) และประสิทธิภาพด้านพื้นที่ยังคงเป็น O(bd) เช่นเดิม .โดยทั่วไปแล้ว การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึกจะเป็นวิธีการค้นหาที่ดีกว่าแบบอื่นๆ เมื่อจำนวนพื้นที่ที่ต้องค้นหามีขนาดใหญ่ และ ไม่ทราบความลึกของคำตอบเป้าหมายที่ต้องการ
500px
=== การได้คำตอบที่เหมาะสม (Optimality) ===
การได้คำตอบที่เหมาะสม (Optimality) คำตอบที่ได้จากการค้นหาแบบ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) จะเหมาะสมก็ต่อเมื่อเส้นทาง (edge) ที่ใช้ผ่านแต่ละปมที่ต้องการค้นหาในต้นไม้ค้นหามีน้ำหนักเท่ากัน คือ 1
ถ้าน้ำหนักของเส้นทาง (edge) การเดินทางของแต่ละปมมีค่าต่างกันที่ไม่ใช่ 1 จะทำให้คำตอบที่มาจากการค้นหาไม่เหมาะสม
=== ความสมบูรณ์ (Completeness) ===
การได้คำตอบหรือการใช้ขั้นตอนวิธีการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึกนั้นจะมีความสมบูรณ์เหมือนกับ การค้นเชิงแนวกว้าง ซึ่งความสมบูรณ์นั้นอยู่ภายใต้ปัจจัยที่ว่า ค่าปัจจัยในการแตกกิ่ง (b) ต้องมีขอบเขตจำกัด (finite) ซึ่งถ้าปัจจัยต่างๆเหมาะสมแล้วขั้นตอนวิธีการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก จะใช้เวลาดีและทำงานได้เร็วกว่าขั้นตอนวิธีการค้นเชิงลึก และ การค้นเชิงแนวกว้าง
== ตัวอย่าง ==
300px
จากกราฟหากเราเริ่มค้นหาตามแนวลึกโดยเริ่มต้นที่จุด A กำหนดให้เส้นทาง (edge) ด้านซ้ายจะถูกเลือกก่อนเส้นทาง (edge) ในด้านขวา และการค้นหาจะจำไว้ว่าก่อนหน้าเคยค้นปมไหนมาแล้วบ้าง และจะไม่ค้นปมนั้นซ้ำอีก ดังนั้นการค้นปมต่างๆในกราฟข้างต้นจะได้เป็นลำดับดังนี้ A, B, D, F, E, C, G
ในอีกแบบหนึ่งผลที่ได้จากการค้นหาตามแนวลึกที่เริ่มต้นที่จุด A แต่จะไม่จำว่าก่อนหน้าเคยค้นพบปมไหนมาก่อน ผลที่ได้จากการค้นหาจะเป็น order A, B, D, F, E, A, B, D, F, E, etc. ซ้ำแบบนี้ไปเรื่อยๆ ซึ่งจะไม่สามารถค้นเจอปม C หรือ G ในกราฟได้
การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก จะป้องกันการเกิด loop แบบด้านบน และจะทำให้ค้นปมต่างๆในแต่ความลึกของปมต่างๆนั้นเอง ซึ่งจะให้ดำเนินการจากซ้ายไปขวาแบบข้างต้น
0: A
1: A (ค้นซ้ำ), B, C, E
(หมายเหตุ : iterative deepening ได้ค้นเจอปม C ซึ่งการค้นหาตามแนวลึกข้างต้นค้นไม่เจอ )
2: A, B, D, F, C, G, E, F
(หมายเหตุ : ยังสามารถค้นเจอปม C แต่คราวนี้เกิดการค้นเจอทีหลัง เนื่องด้วยการค้นเจอปม E ในคนละเส้นทางและ การจะเกิดกสนวนกลับมาค้นเจอปม F ถึงสองครั้ง
3: A, B, D, F, E, C, G, E, F, B
จากกราฟข้างต้น เมื่อเพิ่มความลึก สังเกต 2 วัฏจักร คือ "ABFE" และ "AEFB" จะเจอได้ง่ายและบ่อยครั้ง ก่อนที่ขั้นตอนวิธีจะหยุดและไปค้นหาในเส้นทางอื่นๆ
== การนำไปประยุกต์ใช้ ==
มีขั้นตอนวิธีที่คล้ายกับ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) คือ iterative lengthening search ซึ่งเป็นขั้นตอนวิธีที่มีการเพิ่มน้ำหนักของเส้นทาง (edge) ของระดับความลึกในชั้นต่างๆ ซึ่งการซ้ำการค้นปมๆต่างในระดับต่างๆนั้นจะมีค่าน้ำหนักบนเส้นทาง (edge) ไปยังปมต่างๆเหล่านั้นเพิ่มขึ้นด้วย เพราะฉะนั้นเป้าหมายแรกที่ได้จะเป็นเส้นทางที่มีค่ารวมของน้ำหนักบนเส้นทางดีที่สุด คือถูกที่สุดนั่นเอง แต่ iterative lengthening ก็ยังมีปัญหาอยู่มากทำให้ เป็นวิธีการค้นหาที่ยังไม่ดีเท่าการค้นเชิงลึกจำกัดแบบวนเพิ่มความลึก
การค้นหาแบบ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) จะใช้ได้ในงานหลายๆ ด้าน เช่น ในเรื่องเกี่ยวกับการทำปัญญาประดิษฐ์ เช่นการจำลองการเล่นหมากรุก
การค้นหาแบบ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก (IDDFS) จะนำไปใช้ใน game tree เช่น killer heuristicand , alpha-beta pruning (ขั้นตอนวิธีที่ใช้ลดการหาที่ไม่จำเป็น) ซึ่งมากไปด้วยการประมาณความถูกต้องของคะแนนของปมต่างๆกันที่ปลายทางความลึกที่สามารถเกิดขึ้นได้ และการค้นหาจะเสร็จได้รวดเร็ว
== สรุป ==
Iterative Deepening Depth-First Search (IDDFS) หรือ การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก เป็นขั้นตอนวิธีที่ดัดแปลงหรือพัฒนามากจากการค้นแบบจำกัดความลึก โดยอาศัยหลักการของขั้นตอนวิธีเชิงละโมบ ที่จะค่อยๆ หาคำตอบที่ต้องการจากเริ่มต้นที่กำหนดความลึกที่จะค้นหาไว้ที่ 0 แล้วเพิ่มค่าความลึกขึ้นไปเรื่อยๆ จนกว่าเราจะเจอเป้าหมายคำตอบต้องการได้
== เพิ่มเติม ==
=== ข้อมูลเพิ่มเติม ===
iterative lengthening search
[http://home.hccnet.nl/h.g.muller/deepen.html]
=== ตัวอย่างโปรแกรม ===
[http://www.youtube.com/results?search_query=Iterative+deepening+depth-first+search+example&aq=f]
== อ้างอิง ==
[Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2]
[http://mhesham.wordpress.com/tag/iterative-deepening-depth-first-search/]
www.inc.eng.kmutt.ac.th/course/inc551/551lec03.ppt
[http://www.comp.lancs.ac.uk/computing/research/aai-aied/people/paulb/old243prolog/subsection3_6_4.html]
ขั้นตอนวิธีการค้นหา