อัลกอริทึม Ford-Fulkerson ปรับปรุงโซลูชันการหา Max Flow ด้วยภาษา Golang

ในยุคที่ข้อมูลและการเชื่อมต่อของเครือข่ายกลายเป็นส่วนสำคัญของชีวิตเรา การวิเคราะห์และการจัดการการไหลของข้อมูลนั้นเป็นเรื่องที่ไม่อาจมองข้ามได้ วันนี้เราจะมาพูดถึงอัลกอริทึมที่มีอิทธิพลในการแก้ไขปัญหาการหา Maximum Flow (Max Flow) ในเครือข่าย นั่นคืออัลกอริทึม Ford-Fulkerson โดยเราจะชำแหละและทดลองการใช้งานด้วยภาษา Golang ซึ่งเป็นภาษาที่มีความปลอดภัยสูงและมีประสิทธิภาพเหมาะสมกับการประมวลผลคำนวณที่ท้าทายเช่นนี้

Ford-Fulkerson Algorithm คืออะไร?

Ford-Fulkerson Algorithm คืออัลกอริทึมที่ใช้หาค่าสูงสุดของการไหลในเครือข่าย (Max Flow) โดยมองเครือข่ายเป็นกราฟที่มีจุดเริ่มต้น(source) และจุดปลายทาง(sink) แต่ละขอบในกราฟมีความจุเป็นจำกัด อัลกอริทึมนี้จะพยายามหาเส้นทางที่สามารถเพิ่มการไหลให้ได้มากที่สุดจาก source ไปยัง sink

หลักการทำงาน:

1. เริ่มต้นด้วยการกำหนดการไหลทั้งหมดเป็น 0

2. ใช้ Depth-First Search(DFS) หรือ Breadth-First Search(BFS) หาเส้นทางที่ยังสามารถเพิ่มการไหลได้ (augmenting path) จาก source ไปยัง sink

3. เพิ่มการไหลในเส้นทางนั้นที่มีความจุสูงสุดที่เป็นไปได้ (bottleneck capacity)

4. ทำซ้ำกระบวนการ 2-3 จนไม่สามารถหา augmenting path ได้อีก

การใช้งานใน Golang

package main

import (
    "fmt"
    "math"
)

const V = 6  // จำนวน Vertices ในกราฟ

// BFS เป็นส่วนหนึ่งของ Ford-Fulkerson Algorithm
// ใช้หาว่ามี Augmenting Path หรือไม่ระหว่าง source และ sink
func BFS(rGraph [V][V]int, s int, t int, parent []int) bool {
    visited := make([]bool, V)
    queue := []int{}

    queue = append(queue, s)
    visited[s] = true
    parent[s] = -1

    for len(queue) != 0 {
        u := queue[0]
        queue = queue[1:]

        for v := 0; v < V; v++ {
            if visited[v] == false && rGraph[u][v] > 0 {
                queue = append(queue, v)
                parent[v] = u
                visited[v] = true
            }
        }
    }

    return (visited[t] == true)
}

// FordFulkerson ใช้แก้ปัญหา max flow ในกราฟโดยใช้ BFS
func FordFulkerson(graph [V][V]int, s int, t int) int {
    var u, v int

    rGraph := graph  // residual graph
    parent := make([]int, V)
    maxFlow := 0

    for BFS(rGraph, s, t, parent) {
        pathFlow := math.MaxInt64
        for v = t; v != s; v = parent[v] {
            u = parent[v]
            pathFlow = Min(pathFlow, rGraph[u][v])
        }

        for v = t; v != s; v = parent[v] {
            u = parent[v]
            rGraph[u][v] -= pathFlow
            rGraph[v][u] += pathFlow
        }

        maxFlow += pathFlow
    }
    return maxFlow
}

func Min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func main() {
    graph := [V][V]int{{0, 16, 13, 0, 0, 0},
                        {0, 0, 10, 12, 0, 0},
                        {0, 4, 0, 0, 14, 0},
                        {0, 0, 9, 0, 0, 20},
                        {0, 0, 0, 7, 0, 4},
                        {0, 0, 0, 0, 0, 0}}
    source := 0
    sink := 5
    maxFlow := FordFulkerson(graph, source, sink)

    fmt.Printf("The maximum possible flow is %d \n", maxFlow)
}

Usecase ในโลกจริง

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

Complexity และ ข้อดีข้อเสีย

Complexity ของ Ford-Fulkerson ขึ้นอยู่กับ จำนวน augmenting path ที่พบและการไหลสูงสุดที่เป็นไปได้ (O(Ef) โดยที่ E คือจำนวนขอบ และ f คือการไหลสูงสุด) ซึ่งอาจไม่เหมาะกับกรณีที่การไหลมีค่าสูงมากๆ

ข้อดีคือ เป็นอัลกอริทึมที่เข้าใจได้ง่าย และมักจะทำงานได้ดีในปัญหาขนาดเล็กถึงปานกลาง ข้อเสียคือ ไม่มีการรับประกันว่าจะเป็นไปในรูปของ polynomial time เพราะในบางกรณีอาจใช้เวลานานเกินไปในการคำนวณ

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

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