การทำความเข้าใจ Branch and Bound Algorithm ด้วยภาษา Objective-C**

 

ในโลกของการเขียนโปรแกรมและวิทยาการคอมพิวเตอร์ อัลกอริธึม (Algorithms) มีบทบาทสำคัญในการแก้ไขปัญหาที่ซับซ้อน โดยเฉพาะในด้านการค้นหาและการเพิ่มประสิทธิภาพ ในบทความนี้ เราจะพูดถึง Branch and Bound Algorithm ซึ่งเป็นอัลกอริธึมที่ใช้ในการค้นหาค่าเหมาะสมที่สุดในปัญหาต่างๆ เช่น ปัญหาการจัดกลุ่ม (Knapsack Problem) และปัญหาการค้นหาทางที่สั้นที่สุด (Traveling Salesman Problem) โดยเฉพาะอย่างยิ่งในภาษา Objective-C

 

Branch and Bound Algorithm คืออะไร?

Branch and Bound (B&B) เป็นเทคนิคที่ใช้ในการหาคำตอบที่ดีที่สุดของปัญหาการตัดสินใจ (Decision Problems) ที่มีลักษณะเป็นการค้นหาในรูปแบบของต้นไม้ (tree structure) โดยที่อัลกอริธึมนี้จะแบ่งปัญหาออกเป็นส่วนย่อย ๆ (Branching) และใช้การประเมินผลเพื่อกำจัดตัวเลือกที่ไม่เหมาะสม (Bounding) ออกจากการพิจารณา

 

การทำงานของ Branch and Bound

1. Branching: แบ่งปัญหาออกเป็นหลาย ๆ สาขา โดยแต่ละสาขาจะแสดงถึงการเลือกหรือไม่เลือกในบางจุด 2. Bounding: ใช้แนวทางการประเมินผลเพื่อหาค่าต่ำสุดหรือค่าสูงสุดที่อาจจะได้จากการเลือกที่ดำเนินไป 3. Pruning: ยกเลิกการพิจารณาสาขาที่ไม่สามารถทำให้ได้คำตอบที่เหมาะสมที่สุดได้

 

Use Case ในโลกจริง

ตัวอย่างที่เด่นชัดของการใช้ B&B คือการแก้ปัญหาการวางแผนการขนส่งสินค้า (Transportation Problem) ที่เกิดขึ้นในบริษัทลอจิสติกส์ ปัญหานี้สามารถมองได้ว่าเป็นการหาค่าที่เหมาะสมในการขนส่งสินค้า 3 ชนิดจาก 3 โรงงานไปยัง 3 ร้านค้า โดยต้องการลดค่าใช้จ่ายในการขนส่งให้ต่ำที่สุด

 

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

ในตัวอย่างนี้ เราจะใช้ Branch and Bound เพื่อแก้ปัญหาการจัดกลุ่ม (Knapsack Problem) ซึ่งเป็นปัญหาที่เราต้องการเลือกสิ่งของจำนวนหนึ่งให้มีน้ำหนักไม่เกินค่าใดค่าหนึ่ง และมีค่าใช้จ่ายสูงที่สุด

 #import <Foundation/Foundation.h>

@interface Item: NSObject
@property (nonatomic, assign) int value;
@property (nonatomic, assign) int weight;
- (instancetype)initWithValue:(int)value weight:(int)weight;
@end

@implementation Item
- (instancetype)initWithValue:(int)value weight:(int)weight {
    if (self = [super init]) {
        _value = value;
        _weight = weight;
    }
    return self;
}
@end

@interface Node: NSObject
@property (nonatomic, assign) int level;
@property (nonatomic, assign) int profit;
@property (nonatomic, assign) int weight;
@property (nonatomic, assign) float bound;
- (instancetype)initWithLevel:(int)level profit:(int)profit weight:(int)weight bound:(float)bound;
@end

@implementation Node
- (instancetype)initWithLevel:(int)level profit:(int)profit weight:(int)weight bound:(float)bound {
    if (self = [super init]) {
        _level = level;
        _profit = profit;
        _weight = weight;
        _bound = bound;
    }
    return self;
}
@end

float bound(Node *node, int n, int W, NSArray<Item *> *items) {
    if (node.weight >= W) return 0;
    float profitBound = (float)node.profit;
    int j = node.level + 1;
    int totalWeight = node.weight;

    while (j < n && totalWeight + items[j].weight <= W) {
        totalWeight += items[j].weight;
        profitBound += items[j].value;
        j++;
    }

    if (j < n) {
        profitBound += (W - totalWeight) * (float)(items[j].value) / (float)(items[j].weight);
    }
    return profitBound;
}

int knapsack(int W, NSArray<Item *> *items) {
    int n = (int)items.count;
    NSMutableArray<Node *> *queue = [NSMutableArray array];

    Node *root = [[Node alloc] initWithLevel:-1 profit:0 weight:0 bound:0];
    root.bound = bound(root, n, W, items);
    [queue addObject:root];

    int maxProfit = 0;

    while (queue.count > 0) {
        Node *node = queue.firstObject;
        [queue removeObjectAtIndex:0];

        if (node.level == -1) {
            node.level++;
        }

        if (node.level < n) {
            Node *nextNode = [[Node alloc] initWithLevel:node.level + 1 profit:node.profit weight:node.weight bound:0];

            // Include the next item
            nextNode.weight += items[nextNode.level].weight;
            nextNode.profit += items[nextNode.level].value;

            if (nextNode.weight <= W && nextNode.profit > maxProfit) {
                maxProfit = nextNode.profit;
            }

            nextNode.bound = bound(nextNode, n, W, items);
            if (nextNode.bound > maxProfit) {
                [queue addObject:nextNode];
            }

            // Exclude the next item
            nextNode = [[Node alloc] initWithLevel:node.level + 1 profit:node.profit weight:node.weight bound:0];
            nextNode.bound = bound(nextNode, n, W, items);
            if (nextNode.bound > maxProfit) {
                [queue addObject:nextNode];
            }
        }
    }
    return maxProfit;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSArray<Item *> *items = @[
            [[Item alloc] initWithValue:60 weight:10],
            [[Item alloc] initWithValue:100 weight:20],
            [[Item alloc] initWithValue:120 weight:30]
        ];
        int W = 50; // maximum weight

        int maxProfit = knapsack(W, items);
        NSLog(@"Maximum profit: %d", maxProfit);
    }
    return 0;
}

 

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

- เวลาการทำงาน (Time Complexity): Branch and Bound มีความเวลาความซับซ้อนอยู่ที่ O(2^n) ในกรณีเลวร้าย แต่สามารถถูกปรับปรุงได้ด้วยเทคนิคการเลือกที่เหมาะสม - พื้นที่การทำงาน (Space Complexity): P(B&B) สูงสุดเป็น O(n) เชื่อมโยงกับการเก็บรักษาข้อมูลของแต่ละ Knot

 

ข้อดีข้อเสียของ Algorithm นี้

ข้อดี

:

- สามารถหาราคาที่ดีที่สุดในกรณีที่มีขนาดเล็กได้

- ยืดหยุ่นต่อประเภทของปัญหาอันหลากหลายในการค้นหา

- ใช้ประโยชน์จากแนวทางการประเมิน (Bounding) เพื่อกำจัดไปได้อย่างรวดเร็ว

ข้อเสีย

:

- ไม่สามารถใช้กับปัญหาที่ขนาดใหญ่ได้ดี เนื่องจากความซับซ้อนที่สูง

- การเลือก Bounding Function ที่เหมาะสมอาจใช้เวลานาน

 

สรุป

Branch and Bound Algorithm เป็นเครื่องมือที่ทรงพลังในการจัดการปัญหาความเหมาะสมสูงในหลายพื้นที่ ตั้งแต่วงการคอมพิวเตอร์ไปจนถึงธุรกิจ หากคุณสนใจในการศึกษาการเขียนโปรแกรมและการแก้ปัญหาที่ซับซ้อนแบบนี้ EPT (Expert-Programming-Tutor) ยินดีต้อนรับทุกคนที่ต้องการพัฒนาทักษะทางด้านการเขียนโปรแกรมในที่เรียนรู้จากผู้เชี่ยวชาญ โดยอาจเริ่มจากการลองสร้างโปรแกรมที่ใช้ B&B ในแอปพลิเคชันของคุณเอง!

 

 

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