ดูต้นฉบับสำหรับ การค้นหาแบบจำกัดความลึก

'''การค้นแบบจำกัดความลึก''' หรือ '''การค้นหาแบบจำกัดความลึก''' ({{langx|en|depth limited search}}) เป็น[[ขั้นตอนวิธี]]ทาง[[วิทยาการคอมพิวเตอร์]]ที่ใช้ในการหาปมบน[[กราฟ (คณิตศาสตร์)|กราฟ]]ซึ่งได้ปรับปรุงจาก[[การค้นหาเชิงลึก]] (depth first search) เพื่อใช้ในงานค้นหากราฟ ที่ต้องการประสิทธิภาพสูงขึ้น โดยขั้นตอนวิธีนี้ เป็นพื้นฐานของ [[Iterative deepening depth-first search]] ซึ่งเป็นขั้นตอนวิธีสำหรับ[[การค้นหาสถานะ]] (state space search) ที่อาศัยการค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึกไปเรื่อยๆ เพื่อหาคำตอบที่ดีที่สุด

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

== ขั้นตอนวิธี ==

# ระบุจุดยอดที่จะเริ่มการค้นหา และระบุความลึกสูงสุดที่ควรจะเป็น
# ตรวจสอบว่าจุดยอดนั้นเป็นคำตอบหรือไม่
#* ถ้าใช่ก็คืนค่าคำตอบนั้น
#* ถ้าไม่ใช่ก็ทำต่อไปยังข้อ 3
# ตรวจสอบว่าจุดยอดนั้นมีความลึกเกินค่าที่กำหนดหรือไม่
#* ถ้าเกินก็ไม่ต้องทำอะไร (ไม่มีคำตอบในวิถีนี้)
#* ถ้าไม่เกินก็ให้ทำการเรียกซ้ำข้อ 2 ตามปลายทางเส้นเชื่อมของกราฟในจุดยอดนั้นทั้งหมด เพื่อหาในความลึกในระดับถัดไปเรื่อย

== รหัสเทียม ==

 '''DLS'''(node, goal, depth) {
   if ( depth >= 0 ) {
     if ( node == goal )
       return node

     for each child in expand(node)
       '''DLS'''(child, goal, depth-1)
   }
 }

== คุณสมบัติ ==

=== ความซับซ้อนด้านพื้นที่ ===
จะมีความซับซ้อนด้านพื้นที่เป็น O(<math>\vert V \vert</math>) (โดย <math>\vert V \vert</math> คือจำนวนจุดยอดบนกราฟ) เนื่องจากใช้โครงสร้างแบบเดียวกันกับการค้นหาเชิงลึก

=== ความซับซ้อนด้านเวลา ===
จะมีความซับซ้อนด้านเวลาเป็น O(<math> \vert V \vert + \vert E \vert </math>) ( <math>\vert V \vert</math> คือจำนวนจุดยอดบนกราฟ และ <math>\vert E \vert</math> คือจำนวนเส้นเชื่อมบนกราฟ) โดยเท่ากับกับแบบการค้นหาเชิงลึก เนื่องจากใช้โครงสร้างแบบเดียวกัน แต่ทว่าการค้นแบบด้วยกระบวนการนี้จะค้นหากราฟภายในระยะที่กำหนดไว้ ไม่ได้ค้นหากราฟทั้งหมด

=== ความสมบูรณ์ (Completeness) ===
ถึงแม้ว่าการค้นหาแบบนี้จะทำไม่สามารถเดินตามเส้นเชื่อมของกราฟไปอย่างไม่มีที่สิ้นสุด หรือติดอยู่ในวังวนของกราฟเนื่องจากมีการกำหนดขอบเขตก็ตาม ความสมบูรณ์ของคำตอบนั้นจะขึ้นอยู่กับการกำหนดขอบเขตของความลึก หากกำหนดค่าความลึกไว้น้อยเกินไปก็อาจจะไม่ได้คำตอบ หรือหากกำหนดมากไป ก็อาจจะได้คำตอบที่ไม่ดีที่สุด

=== การได้คำตอบเหมาะสมที่สุด (Optimality) ===
คำตอบที่ได้จากการค้นหาแบบนี้อาจจะยังไม่เหมาะสมที่สุด เนื่องจากยังคงมีปัญหาจากการค้นหาเชิงลึก ที่บางกรณีที่หากการไล่ค้นหากราฟนั้นเริ่มเดินทางจากเส้นเชื่อมที่ไม่ใช่เส้นเชื่อมที่ดีที่สุด แล้วค้นเจอคำตอบที่ต้องการ

== ตัวอย่าง ==
พิจารณากราฟ

[[ไฟล์:graph.traversal.example.svg|200px]]

จากกราฟ หากเราเริ่มค้นหาจากจุดยอด A และต้องการค้นหาจุดยอด C การค้นหาด้วย Depth First Search โดยไม่ได้มีการจำว่าแวะผ่านจุดยอดใดไปแล้วบ้าง นั้นจะทำการค้นหาใน[[วิถี (ทฤษฎีกราฟ)|วิถี]] A -> B -> D -> F -> E -> A -> B -> D -> F -> E -> A -> และวนไปเรื่อยๆ หาจุดยอดที่ต้องการไม่พบ แต่หากกำหนดว่าความลึกของเราจะไม่เกิน 3 เราจะได้การค้นหาเป็น A -> B -> D -> F -> E -> C ซึ่งเป็นจุดยอดที่ต้องการ โดยมีวิถีคือ A -> C

แต่อย่างไรก็ตาม หากเรากำหนดความลึกไว้ไม่เหมาะสม ก็อาจจะทำให้คำตอบที่ได้นั้นไม่เป็นคำตอบที่ดีที่สุด เช่น กำหนดความลึกไว้ที่ 3 และหาจุดยอด E เราจะได้การค้นว่าเป็น A -> B -> D -> F -> E ซึ่งจะได้วิถีของคำตอบคือ A -> B -> F -> E ซึ่งไม่ใช่วิถีที่ดีที่สุด ( A -> E) เป็นต้น

== การประยุกต์ใช้ ==
การค้นหาแบบจำกัดความลึก ใช้ในงานหลายๆ ด้าน แต่ส่วนมากนั้นจะใช้ในเรื่องเกี่ยวกับการทำ[[ปัญญาประดิษฐ์]] (Artificial Intelligence) เช่นการจำลองการเล่นหมากรุก โดยใช้งานร่วมที่ใช้ขั้นตอนวิธีอื่นๆ เพิ่มเติม เช่น minimax (วิธีการหาวิธีที่ดีที่สุด) หรือ alpha-beta (ขั้นตอนวิธีที่ใช้ลดการหาที่ไม่จำเป็น)

ขั้นตอนวิธีหนึ่งที่เกี่ยวข้องคือ Iterative deepening depth-first search ซึ่งเป็นขั้นตอนวิธีสำหรับการค้นหาสถานะ (state space search) ที่อาศัยการค้นหาแบบจำกัดความลึก โดยเพิ่มจำนวนความลึก ไปเรื่อยๆ จนกระทั่งเจอคำตอบ ซึ่งวิธีนี้จะทำให้สามารถรับประกันได้ว่าคำตอบที่เราได้มานั้นเป็นคำตอบที่ดีที่สุด (จะได้วิถีผ่านที่น้อยที่สุด เนื่องจากเราพิจารณาจากวิถีน้อยไปมากขึ้นเรื่อยๆ)

== สรุป ==
ขั้นตอนวิธีนี้ เกิดจากปรับปรุงแก้ไขจากการค้นหาเชิงลึก เพื่อทำให้ประสิทธิภาพของขั้นตอนวิธีดีขึ้น กล่าวคือ ไม่เกิดการวนซ้ำไปเรื่อยๆ จนไม่มีที่สิ้นสุด แต่อย่างไรก็ตาม ยังมีข้อจำกัดอยู่ที่ว่าเราจะต้องเลือกความลึกของการค้นหาให้เหมาะสม จึงจะทำให้เกิดประสิทธิภาพ กำหนดความลึกไว้น้อย ก็อาจไม่เจอคำตอบ หรือกำหนดความลึกมาก ก็อาจจะได้คำตอบที่ยังไม่ดีที่สุด ซึ่งขั้นตอนวิธีนี้ได้ถูกแก้ไขปรับปรุงเป็น Iterative deepening depth-first search โดยอาศัยหลักการของ[[ขั้นตอนวิธีเชิงละโมบ]] ที่ค่อยๆ หาจากการกำหนดขีดความลึกไว้ที่ 0 แล้วเพิ่มขึ้นเรื่อยๆ จนกว่าเราจะเจอคำตอบต้องการได้

== ดูเพิ่ม ==
* [[Iterative deepening depth-first search|การค้นหาเชิงลึกจำกัดแบบวนเพิ่มความลึก]] ([[:en:Iterative deepening depth-first search|Iterative deepening depth-first search]])

== อ้างอิง ==
* 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://chessprogramming.wikispaces.com/Depth-First Depth-First: Chess Programming Wiki ] {{Webarchive|url=https://web.archive.org/web/20110810022124/http://chessprogramming.wikispaces.com/Depth-First |date=2011-08-10 }}

== แหล่งข้อมูลอื่น ==
* [http://ultrastudio.org/en/Depth_first_search#Limited_depth_search ตัวอย่างการทำงาน] {{Webarchive|url=https://web.archive.org/web/20110701230939/http://ultrastudio.org/en/Depth_first_search#Limited_depth_search |date=2011-07-01 }}
* [http://aima-java.googlecode.com/svn/trunk/aima-core/src/main/java/aima/core/search/uninformed/DepthLimitedSearch.java ตัวอย่างการนำไปใช้ในภาษา Java] {{Webarchive|url=https://web.archive.org/web/20110901074710/http://aima-java.googlecode.com/svn/trunk/aima-core/src/main/java/aima/core/search/uninformed/DepthLimitedSearch.java |date=2011-09-01 }}

[[หมวดหมู่:ขั้นตอนวิธีการค้นหา]]
[[หมวดหมู่:ทฤษฎีกราฟ]]