ทำความรู้จักกับ Ford-Fulkerson Algorithm

 

 

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

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

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

 

Use Case ในโลกจริง

ในเชิงปฏิบัติ Ford-Fulkerson Algorithm สามารถนำมาใช้ในหลายสถานการณ์ เช่น:

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

2. การจัดสรรทรัพยากรในโรงงาน: การวางแผนการผลิตและการจัดสรรวัตถุดิบให้สามารถผลิตได้มากที่สุดและเพียงพอกับความต้องการ

3. ระบบโทรคมนาคม: การวิเคราะห์การจราจรของข้อมูลเพื่อหาปริมาณข้อมูลสูงสุดที่สามารถถูกส่งผ่านเครือข่ายได้ในขณะที่คงความมั่นคงของการบริการ

 

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

มาลองดูการใช้งาน Ford-Fulkerson Algorithm ด้วยภาษา Objective-C กันดีกว่า ดังนี้:

 #import <Foundation/Foundation.h>

@interface Graph : NSObject
@property (nonatomic, strong) NSMutableArray<NSMutableArray<NSNumber *> *> *capacity;
@property (nonatomic, strong) NSMutableArray<NSMutableArray<NSNumber *> *> *flow;
@property (nonatomic) NSInteger vertexCount;

// Method declarations
- (instancetype)initWithVertexCount:(NSInteger)count;
- (void)addEdgeFrom:(NSInteger)u to:(NSInteger)v capacity:(NSInteger)cap;
- (NSInteger)fordFulkersonFromSource:(NSInteger)source toSink:(NSInteger)sink;
- (BOOL)bfsWithSource:(NSInteger)source sink:(NSInteger)sink parent:(NSMutableArray<NSNumber *> *)parent;
@end

@implementation Graph

- (instancetype)initWithVertexCount:(NSInteger)count {
    self = [super init];
    if (self) {
        _vertexCount = count;
        _capacity = [NSMutableArray arrayWithCapacity:count];
        _flow = [NSMutableArray arrayWithCapacity:count];

        for (NSInteger i = 0; i < count; i++) {
            _capacity[i] = [NSMutableArray arrayWithCapacity:count];
            _flow[i] = [NSMutableArray arrayWithCapacity:count];
            for (NSInteger j = 0; j < count; j++) {
                _capacity[i][j] = @(0);
                _flow[i][j] = @(0);
            }
        }
    }
    return self;
}

- (void)addEdgeFrom:(NSInteger)u to:(NSInteger)v capacity:(NSInteger)cap {
    self.capacity[u][v] = @(cap);
}

- (NSInteger)fordFulkersonFromSource:(NSInteger)source toSink:(NSInteger)sink {
    NSMutableArray<NSNumber *> *parent = [NSMutableArray arrayWithCapacity:self.vertexCount];
    NSInteger maxFlow = 0;

    while ([self bfsWithSource:source sink:sink parent:parent]) {
        NSInteger pathFlow = NSIntegerMax;

        for (NSInteger v = sink; v != source; v = parent[v].integerValue) {
            NSInteger u = parent[v].integerValue;
            pathFlow = MIN(pathFlow, self.capacity[u][v].integerValue - self.flow[u][v].integerValue);
        }

        for (NSInteger v = sink; v != source; v = parent[v].integerValue) {
            NSInteger u = parent[v].integerValue;
            self.flow[u][v] = @(self.flow[u][v].integerValue + pathFlow);
            self.flow[v][u] = @(self.flow[v][u].integerValue - pathFlow);
        }

        maxFlow += pathFlow;
    }

    return maxFlow;
}

- (BOOL)bfsWithSource:(NSInteger)source sink:(NSInteger)sink parent:(NSMutableArray<NSNumber *> *)parent {
    BOOL visited[self.vertexCount];
    memset(visited, 0, sizeof(visited));

    NSMutableArray<NSNumber *> *queue = [NSMutableArray array];
    [queue addObject:@(source)];
    visited[source] = YES;
    parent[source] = @(source);

    while (queue.count > 0) {
        NSInteger u = [queue.firstObject integerValue];
        [queue removeObjectAtIndex:0];

        for (NSInteger v = 0; v < self.vertexCount; v++) {
            if (!visited[v] && (self.capacity[u][v].integerValue - self.flow[u][v].integerValue > 0)) {
                if (v == sink) {
                    parent[v] = @(u);
                    return YES;
                }
                queue addObject:@(v);
                parent[v] = @(u);
                visited[v] = YES;
            }
        }
    }

    return NO;
}

@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Graph *graph = [[Graph alloc] initWithVertexCount:6];
        [graph addEdgeFrom:0 to:1 capacity:16];
        [graph addEdgeFrom:0 to:2 capacity:13];
        [graph addEdgeFrom:1 to:2 capacity:10];
        [graph addEdgeFrom:1 to:3 capacity:12];
        [graph addEdgeFrom:2 to:1 capacity:4];
        [graph addEdgeFrom:2 to:4 capacity:14];
        [graph addEdgeFrom:3 to:2 capacity:9];
        [graph addEdgeFrom:3 to:5 capacity:20];
        [graph addEdgeFrom:4 to:3 capacity:7];
        [graph addEdgeFrom:4 to:5 capacity:4];

        NSInteger maxFlow = [graph fordFulkersonFromSource:0 toSink:5];
        NSLog(@"The maximum possible flow is %ld", (long)maxFlow);
    }
    return 0;
}

 

การวิเคราะห์ Complexities

- Time Complexity: O(E * f) โดยที่ E คือจำนวนเอจในกราฟ และ f คือค่าการไหลสูงสุดที่สามารถเกิดขึ้นในกราฟ - Space Complexity: O(V^2) โดย V คือจำนวนโหนดในกราฟ เนื่องจากเราต้องเก็บข้อมูลในหลากหลายโครงสร้างข้อมูล

 

ข้อดี

1. ความเรียบง่าย: อัลกอริธึมนี้มีความเข้าใจง่ายและสามารถปรับใช้ได้ง่ายในขนาดกราฟที่ต่างกัน 2. สามารถปรับปรุงได้: สามารถทำให้มีประสิทธิภาพได้โดยการใช้ BFS หรือ DFS ที่เป็นการค้นหาที่เหมาะสม

 

ข้อเสีย

1. เวลาไม่แน่นอน: สำหรับกราฟที่มีการผลิตสูงสุดที่แตกต่างกัน เมื่อต้องการได้ผลลัพธ์ที่แน่นอน อาจต้องใช้เวลานาน 2. ไม่เหมาะสำหรับทุกกรณี: ในกรณีที่กราฟมีวงกลมอาจทำให้ประสิทธิภาพการหาค่าสูงสุดลดลง

 

เข้าศึกษากับ EPT

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

เราขอเชิญชวนทุกคนที่จะลงมือเรียนรู้และพัฒนาทักษะการเขียนโปรแกรมกับเรา EPT ติดตามคอร์สการเรียนการสอนต่าง ๆ จากทีมผู้เชี่ยวชาญของเราได้เลย!

 

 

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