การค้นหาแบบ Depth First Search (DFS) ด้วยภาษา Ruby

 

 

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

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

การทำงานของ DFS จะใช้โครงสร้างข้อมูลที่เรียกว่า Stack ซึ่ง Link Stack เป็นโครงสร้างที่เหมาะสมเพราะเราสามารถย้อนกลับไปยังโหนดก่อนหน้าได้ง่าย ๆ

ใช้อะไรในการแก้ปัญหา

DFS มักจะใช้ในหลาย ๆ การค้นหาหรือการแก้ปัญหาที่เกี่ยวข้องกับโครงสร้างข้อมูล เช่น:

- การค้นหาทางในเกม (Pathfinding)

- การหาเรื่องราวในอัลกอริธึมกราฟ

- การจัดการกับปัญหาการสร้างกลุ่ม (Clustering) โดยการค้นหาในข้อมูลเช่น networking

- การพัฒนา Engine ถอดความสัมพันธ์ระหว่างข้อมูลในฐานข้อมูล

 

การเข้ารหัสด้วยภาษา Ruby

แนวทางการใช้ DFS เพื่อค้นหาทางจากโหนดหนึ่งไปยังอีกโหนดหนึ่งในกราฟสามารถทำได้ดังนี้:

 class Graph
  attr_accessor :vertices

  def initialize
    @vertices = {}
  end

  def add_edge(vertex, edge)
    @vertices[vertex] ||= []
    @vertices[vertex] << edge
  end

  def dfs(start_vertex, visited = {})
    return if visited[start_vertex]

    visited[start_vertex] = true
    puts start_vertex # แสดงโหนดที่เราไปถึง

    @vertices[start_vertex].each do |neighbor|
      dfs(neighbor, visited)
    end
  end
end

# สร้างกราฟตัวอย่าง
graph = Graph.new
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('B', 'E')
graph.add_edge('C', 'F')

# เริ่มต้นการค้นหา
graph.dfs('A') # จะพิมพ์ A B D E C F

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

1. Graph Class: คลาสนี้เก็บข้อมูลของกราฟที่มีโหนดและเชื่อมต่อกันโดยใช้ Hashmap โดยที่ key เป็นโหนดและ value เป็น Array ของโหนดเชื่อมต่อ 2. add_edge Method: ใช้สำหรับสร้าง edges ระหว่างโหนดต่าง ๆ 3. dfs Method: เป็นเมธอดในการค้นหาด้วย DFS โดยใช้ arguments คือ โหนดเริ่มต้นและ Hashmap ที่มีค่า true สำหรับโหนดที่มีการเยี่ยมชมแล้ว 4. การพิมพ์ผล: โค้ดจะแสดงผลโหนดที่ถูกสำรวจในลำดับที่ได้เยี่ยมชม

 

Use Cases ในโลกจริง

1. การวางแผนเส้นทางในเกม

ในเกมหรือการจำลองสถานการณ์เช่น "Minecraft" หรือเกม RPG บางชนิด เมื่อผู้เล่นต้องการสำรวจแผนที่หรือค้นหา item ที่ซ่อนอยู่ อัลกอริธึม DFS สามารถช่วยให้ผู้เล่นสามารถค้นหาทางจากจุดหนึ่งไปยังอีกจุดหนึ่งได้อย่างมีประสิทธิภาพ

2. เว็บ Crawling

เมื่อค้นหาเว็บเพจต่าง ๆ บนอินเทอร์เน็ต เว็บ Crawlers จะใช้ DFS เพื่อสำรวจลิงก์ทั้งหมดในเว็บเพจหนึ่ง อาจจะรวบรวมข้อมูลจากหลาย ๆ หน้าเว็บไซต์ได้

3. การพัฒนา Social Network

ในเป็นส่วนหนึ่งที่ช่วยที่จะค้นหาความสัมพันธ์ระหว่างผู้ใช้ในเครือข่ายสังคมออนไลน์ DFS สามารถใช้เพื่อค้นหาเพื่อนที่เชื่อมต่อกันในระดับหลายระดับ

 

วิเคราะห์ Complexity

1. Time Complexity: O(V + E)

- V คือจำนวนโหนด (vertices) และ E คือจำนวนเชื่อมต่อ (edges) หากพิจารณาจากกราฟทั้งหมด การเยี่ยมชมทุกโหนดและเชื่อมต่อจึงมีเวลา O(V + E)

2. Space Complexity: O(V)

- เนื่องจากต้องมีการเก็บข้อมูลสำหรับโหนดที่ถูกเยี่ยมชมและ Stack ที่ใช้ในการเก็บโหนดที่ยังไม่เยี่ยมชม ซึ่งอาจจะเป็นจำนวนของโหนดทั้งหมด

 

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

ข้อดี

- สามารถใช้ในการสำรวจทางในกราฟที่ใหญ่ได้

- สามารถใช้ Memory น้อยกว่าการค้นหาแบบ Breadth First Search (BFS) ในบางกรณี

ข้อเสีย

- อาจทำให้ไม่พบเส้นทางที่ใกล้ที่สุด (Shortest Path) ในบางกรณี

- ถ้ากราฟมีลูปไม่สิ้นสุด (Infinite Loop) อาจทำให้เกิดการทำงานวนนานเกินไปถ้าไม่มีการป้องกัน

 

สรุป

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

หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรม หรือต้องการพัฒนาทักษะของคุณในด้านการเขียนโปรแกรมและอัลกอริธึม สามารถลงทะเบียนเรียนที่ EPT เพื่อเข้าถึงหลักสูตรที่มีคุณภาพและอาจารย์ที่มีประสบการณ์ เพื่อพาคุณไปสู่ความสำเร็จในโลกของการเขียนโปรแกรม!

 

 

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