การค้นหาด้วยวิธี Depth First Search (DFS) ในภาษา Scala

 

 

แนะนำเกี่ยวกับ Depth First Search (DFS)

Depth First Search (DFS) เป็นหนึ่งในอัลกอริธึมที่ใช้ค้นหาหรือสำรวจโครงสร้างข้อมูลประเภทกราฟ (Graph) และต้นไม้ (Tree) ซึ่งทำงานได้โดยการสำรวจเส้นทางลงไปให้ลึกที่สุดในกราฟก่อนที่จะกลับขึ้นมา และสำรวจเส้นทางอื่น ๆ ที่ยังไม่ได้สำรวจ จนกว่าทุกโหนดในกราฟจะถูกสำรวจ

DFS เป็นอัลกอริธึมที่มีประโยชน์ในหลายด้าน เช่น การค้นหาความเชื่อมโยงในกราฟ การจัดอันดับผู้ใช้ในเกมที่มีหลายเลเวล การค้นหาทางเลือกในเกมแนวหาคำตอบ เป็นต้น

 

โครงสร้างพื้นฐานของ DFS

วิธีการทำงาน

1. เริ่มจากโหนดเริ่มต้น (Starting Node)

2. เยี่ยมชมโหนด (Visit Node)

3. สำรวจโหนดที่ยังไม่ถูกเยี่ยมชม (Unvisited Nodes)

4. ถ้าเจอโหนดลูก ให้เดินทางไปยังโหนดนั้น

5. ทำขั้นตอนนี้ซ้ำจนกว่าจะไม่มีโหนดที่ยังไม่ได้เยี่ยมชม

6. กลับไปยังโหนดพ่อ (Backtrack)

7. ทำขั้นตอนข้างต้นซ้ำจนโหนดทั้งหมดถูกสำรวจ

 

ตัวอย่างโค้ดในภาษา Scala

ก่อนที่จะไปที่โค้ด ตัวอย่างกราฟที่เราจะใช้มีโหนดจำนวน 6 โหนด และเชื่อมโยงกันดังนี้:

     1
   / \
  2   3
 / \   \
4   5   6

มาดูโค้ด Scala สำหรับ DFS กันดีกว่า:

 import scala.collection.mutable

object DepthFirstSearch {

  // ฟังก์ชันสำหรับการค้นหาแบบ DFS
  def dfs(graph: Map[Int, List[Int]], start: Int): List[Int] = {
    // ใช้ mutable Set เพื่อเก็บโหนดที่เยี่ยมชมแล้ว
    val visited = mutable.Set[Int]()
    // ฟังก์ชัน recursive
    def dfsHelper(node: Int): List[Int] = {
      if (visited.contains(node)) Nil // ถ้าเยี่ยมชมแล้ว คืนค่า Nil
      else {
        visited.add(node) // เพิ่มโหนดใน visited
        node :: graph.getOrElse(node, Nil).flatMap(dfsHelper) // ค้นหาและคืนค่าโหนดที่เยี่ยมชม
      }
    }

    dfsHelper(start)
  }

  def main(args: Array[String]): Unit = {
    // สร้างกราฟ
    val graph = Map(
      1 -> List(2, 3),
      2 -> List(4, 5),
      3 -> List(6),
      4 -> Nil,
      5 -> Nil,
      6 -> Nil
    )

    // เรียกใช้ DFS จากโหนด 1
    val result = dfs(graph, 1)
    println("ผลลัพธ์การค้นหา DFS คือ: " + result)
  }
}

คำอธิบายโค้ด

ในโค้ดด้านบน เราสร้างฟังก์ชัน `dfs` ที่รับพารามิเตอร์เป็นกราฟในรูปแบบของ `Map` และโหนดเริ่มต้น จากนั้นเราใช้ `mutable.Set` เพื่อจัดเก็บโหนดที่เราได้เยี่ยมชมแล้ว เพื่อไม่ให้เยี่ยมชมโหนดเดิมซ้ำ

ฟังก์ชัน `dfsHelper` เป็นฟังก์ชันแบบ recursive ที่ทำการเยี่ยมชมโหนดต่าง ๆ โดยถ้าโหนดนั้นยังไม่ถูกเยี่ยมชม มันจะถูกเพิ่มเข้าใน `visited` และทำการเรียกเยี่ยมชมโหนดลูกต่อไป ซึ่งเมื่อไม่มีลูกให้สำรวจแล้ว ก็จะย้อนกลับขึ้นมา

 

Use Cases ในโลกจริง

1. การค้นหาทางในเกม: DFS เป็นอัลกอริธึมที่เหมาะสำหรับการสำรวจแผนที่ต่าง ๆ ในเกม เช่น การค้นหาวัตถุหรือตัวละครในโลกเสมือน 2. การวิเคราะห์โครงสร้างเครือข่าย: DFS สามารถใช้วิเคราะห์เครือข่ายเซิร์ฟเวอร์ หรือการเชื่อมโยงระหว่างสมาชิกในโครงสร้างสังคมออนไลน์ 3. การสร้าง AI ในเกม RPG: อัลกอริธึมนี้สามารถใช้ในการสร้างบอทที่สามารถสำรวจแผนที่และค้นหาสิ่งต่าง ๆ ได้อย่างมีประสิทธิภาพ 4. การแก้ปัญหาปริศนา: เช่น Sudoku หรือปริศนาผีเสื้อ โดยการใช้ DFS ในการค้นหาว่าฝ่ายไหนสามารถจับคู่ได้บ้าง

 

การวิเคราะห์เวลาและพื้นที่ Complexity

1. Time Complexity: O(V + E) โดยที่ V คือจำนวณโหนด (Vertices) และ E คือจำนวนขอบ (Edges) ในกราฟ 2. Space Complexity: O(V) เนื่องจากจะต้องเก็บโหนดที่เยี่ยมชมแล้ว ซึ่งอาจจะมีจำนวนสูงถึง V ในกรณีที่กราฟเป็นลักษณะเส้นตรง

 

ข้อดีและข้อเสียของ DFS

ข้อดี

- ง่ายต่อการใช้งานและไม่ซับซ้อน

- สามารถใช้ในการค้นหาทางเริ่มต้นได้อย่างรวดเร็วในกราฟที่มีขนาดเล็ก

- ใช้พื้นที่น้อยเมื่อเปรียบเทียบกับบางอัลกอริธึมที่ต้องการใช้งานหน่วยความจำมาก

ข้อเสีย

- อาจจะเข้าสู่สุญญากาศ (Infinite loops) หากกราฟมีการเชื่อมโยงกลับ (Cycles)

- ไม่สามารถหาทางที่สั้นที่สุดในกราฟที่มีน้ำหนัก (Weight) ได้

- อาจมีความเสี่ยงที่จะใช้เวลาเพิ่มขึ้นเมื่อพยายามค้นหาทางในกราฟที่มีขนาดใหญ่หรือมีโหนดมาก

 

สรุป

Depth First Search (DFS) เป็นอัลกอริธึมที่มีความสำคัญและทำงานได้มีประสิทธิภาพในหลาย ๆ กรณี รวมถึงการแก้ปัญหาในโลกจริง แต่การเข้าใจถึงข้อดีและข้อเสียจะช่วยให้คุณเลือกใช้หลุดดีเมื่อต้องเผชิญกับปัญหาต่าง ๆ

หากคุณสนใจเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมและการใช้กราฟในภาษา Scala หรือภาษาอื่น ๆ อย่าลืมเข้าร่วมศึกษากับเราที่ EPT (Expert Programming Tutor) เพื่อทำให้คุณเป็นโปรแกรมเมอร์ที่ดีที่สุดในสายอาชีพนี้!

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง