Branch and Bound Algorithm in JavaScript

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

Branch and Bound Algorithm คืออะไร

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

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

อัลกอริทึมนี้มักจะถูกใช้ในปัญหาที่ต้องการหาค่าสูงสุดหรือค่าต่ำสุด อย่างเช่น ปัญหากระเป๋าเป้ (Knapsack Problem), ปัญหาตัวแทนการขายส่ง (Travelling Salesman Problem), ปัญหากำหนดการงาน (Job Assignment Problem) และอื่นๆ นอกจากนี้ยังรวมไปถึงปัญหาที่มีการจำกัดขอบเขตเช่นปัญหาการจำลอง (Simulation) และการวางแผนทรัพยากร (Resource Planning)

ตัวอย่างโค้ด Branch and Bound Algorithm ด้วย JavaScript

เราจะยกตัวอย่างการใช้ Branch and Bound Algorithm กับปัญหากระเป๋าเป้ (0/1 Knapsack Problem) ที่เป้าหมายคือการเลือกสิ่งของหลายๆ อย่างใส่ในกระเป๋าเป้ให้ได้มูลค่าสูงสุดโดยที่น้ำหนักของสิ่งของรวมกันไม่เกินขีดจำกัดที่กระเป๋าเป้สามารถรับไหว นี่เป็นหนึ่งในสถานการณ์ที่เราจะมีหลายทางเลือก และต้องการคำตอบที่เหมาะสมที่สุด

// รหัสตัวอย่าง Branch and Bound algorithm สำหรับปัญหากระเป๋าเป้

function knapsack(items, capacity) {
    // เริ่มต้นสร้าง node รากของ tree
    let rootNode = {
        level: -1,
        profit: 0,
        weight: 0,
        bound: 0,
    };

    // คิดคำนวณ upper bound (คำนวณจาก node ปัจจุบันเพื่อได้ค่าสูงสุดที่เป็นไปได้หากเราเลือกทางนั้น)
    function bound(node) {
        if (node.weight >= capacity) {
            return 0;
        }
        let profitBound = node.profit;
        let j = node.level + 1;
        let totWeight = node.weight;

        while (j < items.length && totWeight + items[j].weight <= capacity) {
            totWeight += items[j].weight;
            profitBound += items[j].value;
            j++;
        }

        // หากยังมีความพร้อมที่จะใส่ได้อีก
        if (j < items.length) {
            profitBound += (capacity - totWeight) * (items[j].value / items[j].weight);
        }

        return profitBound;
    }

    // ฟังก์ชันการทำงานจริงๆของ branch and bound
    function branchAndBound() {
        let maxProfit = 0;
        let queue = [];

        // เริ่มด้วยการดัน node รากลงไปใน queue
        queue.push(rootNode);

        while (queue.length) {
            let node = queue.shift();

            // ถ้าเรายังไม่ได้ไปถึงสุดขอบ level เราจะทำการสร้างสาขาออกไป
            if (node.level === items.length - 1) {
                continue;
            }

            // สร้างโหนด child ที่ "รวม" item นั้นๆ (Include)
            let include = {
                level: node.level + 1,
                profit: node.profit + items[node.level + 1].value,
                weight: node.weight + items[node.level + 1].weight,
                bound: 0,
            };

            // อัพเดท เฉพาะเมื่อมูลค่ามากกว่า maxProfit
            if (include.weight <= capacity && include.profit > maxProfit) {
                maxProfit = include.profit;
            }

            // คำนวณ bound หากมูลค่า bound ของ include ยังน่าสนใจ เพิ่มลง queue
            include.bound = bound(include);
            if (include.bound > maxProfit) {
                queue.push(include);
            }

            // สร้างโหนด child ที่ "ไม่รวม" item นั้นๆ (Exclude)
            let exclude = {
                level: node.level + 1,
                profit: node.profit,
                weight: node.weight,
                bound: bound(node),
            };

            // คำนวณ bound หากมูลค่า bound ของ exclude ยังน่าสนใจ เพิ่มลง queue
            if (exclude.bound > maxProfit) {
                queue.push(exclude);
            }
        }

        return maxProfit;
    }

    // เรียกใช้ฟังก์ชันและคืนค่ากลับ
    return branchAndBound();
}

// ตัวอย่างของการใช้งาน
const items = [
    { weight: 2, value: 3 },
    { weight: 3, value: 4 },
    { weight: 4, value: 5 },
    { weight: 5, value: 6 },
];

const capacity = 5;

console.log("Maximum possible profit: ", knapsack(items, capacity));

ในปัญหากระเป๋าเป้นี้ ข้อดีของ Branch and Bound Algorithm คือมันช่วยให้เราสามารถจัดการปัญหาที่มีขนาดใหญ่หลายมิติได้โดยไม่ต้องทดลองทุกความเป็นไปได้ ส่วนข้อเสียคือการที่มันอาจจะใช้เวลานานในกรณีที่ปัญหามีรูปแบบที่ซับซ้อนและมีการแบ่งสาขาออกไปมาก และที่สำคัญคือประสิทธิภาพขึ้นอยู่กับการคำนวณ bound ที่ดี

Usecase ในโลกจริง

Branch and Bound Algorithm มีการนำไปใช้ในหลายสาขา เช่น ในอุตสาหกรรมการผลิตเพื่อหาวิธีการเพิ่มประสิทธิภาพในการใช้ทรัพยากร หรือการจำกัดจำนวนเครื่องจักรในโรงงานเพื่อประหยัดค่าใช้จ่ายในการผลิต, การวางแผนเดินทางของรถบรรทุกให้ได้ระยะเดินทางที่สั้นและค่าใช้จ่ายน้อยที่สุด, การจัดการพื้นที่จัดเก็บสินค้าในคลังสินค้า หรือแม้แต่ในการวิเคราะห์เครือข่ายสื่อสารเพื่อหาเส้นทางการส่งข้อมูลที่รวดเร็วที่สุด

ในการวิเคราะห์ความซับซ้อน (Complexity) ของ Branch and Bound Algorithm นั้นอาจจะนับเป็น O(b^d) ซึ่ง b คือการแตกสาขาและ d คือความลึกระดับของต้นไม้การคำนวณ แต่ความจริงแล้วมันเป็นสิ่งที่ยากที่จะประเมินตายตัว เพราะมันขึ้นอยู่กับการเลือกสาขาและการกำหนดเขตของแต่ละโจทย์ที่แตกต่างกัน

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

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