Ford-Fulkerson Algorithm: การหาความจุสูงสุดในกราฟ

ในโลกของการเขียนโปรแกรมและวิทยาการคอมพิวเตอร์ มีหลายทางในการแก้ปัญหาที่เกี่ยวข้องกับกราฟ หนึ่งในอัลกอริธึมที่มีประโยชน์และได้รับการใช้งานอย่างกว้างขวางคือ **Ford-Fulkerson Algorithm** ซึ่งใช้สำหรับการหาความจุสูงสุด (Maximum Flow) ในกราฟที่มีทิศทาง โดยอัลกอริธึมนี้ถูกพัฒนาโดย **L.R. Ford Jr.** และ **D.R. Fulkerson** ในปี 1956

อัลกอริธึม Ford-Fulkerson คืออะไร?

อัลกอริธึม Ford-Fulkerson ช่วยเราหาวิธีการผลิตกระแสไหลสูงสุดจากโหนดเริ่มต้น (Source) ไปยังโหนดปลายทาง (Sink) ในกราฟที่มีการเชื่อมโยงกัน โดยการกระจายการไหลจากโหนดหนึ่งไปยังโหนดอื่นผ่านเส้นทางที่ยังมีความสามารถในการไหล (Residual Capacity) อยู่

การทำงานของอัลกอริธึม

การทำงานของ Ford-Fulkerson อิงจากแนวคิดหลักคือการหาทางเดินอย่างต่อเนื่องจากโหนดต้นทางไปยังโหนดปลายทางในกราฟ และเพิ่มกระแสไหลในเส้นทางที่ค้นพบจนกว่าจะไม่มีเส้นทางใดที่สามารถหากระแสไหลที่มากขึ้นได้

ขั้นตอนโดยรวมของอัลกอริธึม

1. เริ่มจากเซ็ตกระแสไหลทั้งหมดเป็น 0

2. หาทางเดิน (Path) จากต้นทางไปยังปลายทางที่ยังมีความสามารถในการไหล

3. เพิ่มกระแสไหลในเส้นทางที่ค้นพบ

4. ทำซ้ำจนไม่สามารถหาทางเดินที่มี Residual Capacity ได้อีก

Use Case ในโลกจริง

อัลกอริธึม Ford-Fulkerson ถูกนำไปใช้ในหลาย ๆ ด้าน เช่น:

- การจัดการทรัพยากรในเครือข่ายคอมพิวเตอร์

- การวางแผนการผลิตในโรงงาน

- การจัดสรรทรัพยากรในระบบขนส่ง

ยกตัวอย่างเช่น ในระบบขนส่งสินค้า บริษัทอาจต้องการส่งของจากคลังสินค้าหลายแห่งไปยังร้านค้าหลายแห่งอย่างมีประสิทธิภาพ การใช้ Ford-Fulkerson Algorithm จะช่วยในการหาวิธีการส่งที่มีประสิทธิภาพที่สุดเมื่อพิจารณาถึงความจุของการขนส่งในเส้นทางต่าง ๆ

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

โค้ดต่อไปนี้คือการใช้ Ford-Fulkerson Algorithm ในการคำนวณกระแสไหลสูงสุดในกราฟโดยใช้ภาษา Ruby:

 class Graph
  attr_reader :vertices, :capacity, :flow

  def initialize(vertices)
    @vertices = vertices
    @capacity = Array.new(vertices) { Array.new(vertices, 0) }
    @flow = Array.new(vertices) { Array.new(vertices, 0) }
  end

  def add_edge(u, v, cap)
    @capacity[u][v] = cap
  end

  def bfs(source, sink, parent)
    visited = Array.new(@vertices, false)
    queue = []

    queue.push(source)
    visited[source] = true

    while !queue.empty?
      u = queue.shift

      for v in (0...@vertices)
        if !visited[v] && @capacity[u][v] - @flow[u][v] > 0
          queue.push(v)
          visited[v] = true
          parent[v] = u
        end
      end
    end

    visited[sink]
  end

  def ford_fulkerson(source, sink)
    parent = Array.new(@vertices, -1)
    max_flow = 0

    while bfs(source, sink, parent)
      path_flow = Float::INFINITY

      s = sink
      while s != source
        path_flow = [path_flow, @capacity[parent[s]][s] - @flow[parent[s]][s]].min
        s = parent[s]
      end

      v = sink
      while v != source
        u = parent[v]
        @flow[u][v] += path_flow
        @flow[v][u] -= path_flow
        v = parent[v]
      end

      max_flow += path_flow
    end

    max_flow
  end
end

# การทดสอบโค้ด
g = Graph.new(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(1, 3, 12)
g.add_edge(2, 1, 4)
g.add_edge(2, 4, 14)
g.add_edge(3, 2, 9)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)

source = 0
sink = 5

puts "The maximum possible flow is #{g.ford_fulkerson(source, sink)}"

วิเคราะห์ Complexity

ความซับซ้อนของอัลกอริธึม Ford-Fulkerson ขึ้นอยู่กับวิธีการค้นหาเส้นทางที่ยังมี Residual Capacity อาจใช้ BFS หรือ DFS ซึ่ง:

- ถ้าใช้ BFS: ความซับซ้อนคือ O(E^2) สำหรับกราฟที่มี E ขอบ

- ถ้าใช้ DFS: ความซับซ้อนคือ O(E*f) โดยที่ f คือความสามารถสูงสุด

ข้อดีและข้อเสียของอัลกอริธึม

ข้อดี:

- เป็นอัลกอริธึมที่เข้าใจง่ายและใช้งานง่าย

- สามารถปรับใช้กับกราฟขนาดใหญ่ได้

ข้อเสีย:

- ความซับซ้อนอาจสูงหากกราฟมีขอบจำนวนมาก

- อาจไม่สามารถหาความจุที่สูงสุดในบางกรณี เช่น เมื่อต้องมีการแก้ไขกราฟระหว่างการคำนวณ

สรุป

Ford-Fulkerson Algorithm เป็นเครื่องมือที่มีประสิทธิภาพในการหาความจุสูงสุดในกราฟ โดยใช้งานได้ทั้งในด้านการจัดการทรัพยากร การขนส่ง และอีกหลายวงการ หากคุณต้องการเรียนรู้อัลกอริธึมนี้อย่างลึกซึ้งและวิธีการนำไปใช้ในโลกจริง ขอเชิญคุณมาเรียนที่ EPT (Expert-Programming-Tutor) ที่นี่ เรามีหลักสูตรและผู้สอนที่เชี่ยวชาญในการสอนเกี่ยวกับอัลกอริธึมและการพัฒนาโปรแกรมในภาษา Ruby รวมถึงภาษาอื่น ๆ อีกมากมาย!

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