ทำความรู้จักกับ Branch and Bound Algorithm ด้วย Groovy

 

ในแวดวงการเขียนโปรแกรมและการพัฒนาอัลกอริธึม มีหลายวิธีที่จะช่วยแก้ปัญหาที่ซับซ้อน แต่หนึ่งในวิธีที่ได้รับความนิยมอย่างมากคือ Branch and Bound Algorithm ซึ่งเป็นอัลกอริธึมที่ใช้ในการหาค่าที่ดีที่สุด (optimal solution) ในปัญหาที่มีโครงสร้างเป็นกราฟ หรือปัญหาที่เกี่ยวข้องกับการค้นหา (search problems) อัลกอริธึมนี้จะเข้ามาช่วยให้เราหาโซลูชันที่ดีที่สุดแม้ว่าเป็นโจทย์ที่เยอะมากก็ตาม

 

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

Branch and Bound เป็นเทคนิคในการค้นหาที่มุ่งเน้นการลดปริมาณการค้นหาที่จำเป็น โดยการแบ่งปัญหาออกเป็นหลาย ๆ ส่วน (Branch) และทำให้เป็น Bound เพื่อให้เราสามารถตัดสิ่งที่ไม่จำเป็นออกได้ การทำงานของ Branch and Bound จะแบ่งออกเป็น 2 ขั้นตอนหลัก ได้แก่

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

 

วิธีใช้ Branch and Bound Algorithm ในการแก้ปัญหา

Branch and Bound สามารถนำมาใช้ในการแก้ปัญหาหลายประเภท เช่น:

- ปัญหาการเดินทางของพ่อค้า (Traveling Salesman Problem – TSP)

- ปัญหา Knapsack

- ปัญหาการจัดตารางเวลา (Job Scheduling)

ตัวอย่างปัญหาการจัดอันดับของ Knapsack

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

#### ตัวอย่างโค้ดด้วย Groovy

 class Item {
    int value
    int weight

    Item(int value, int weight) {
        this.value = value
        this.weight = weight
    }
}

class Node {
    int level, profit, bound, weight

    Node(int level, int profit, int weight, int bound) {
        this.level = level
        this.profit = profit
        this.weight = weight
        this.bound = bound
    }
}

def bound(Node u, int n, int W, List<Item> items) {
    if (u.weight >= W) return 0
    int profitBound = u.profit
    int j = u.level + 1
    int totalWeight = u.weight

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

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

    return profitBound
}

def knapsack(int W, List<Item> items) {
    int n = items.size()
    Node maxNode = new Node(-1, 0, 0, 0)
    Queue<Node> queue = new PriorityQueue<Node>(Comparator.comparingInt(a -> -a.bound))

    maxNode.bound = bound(maxNode, n, W, items)
    queue.add(maxNode)

    int maxProfit = 0

    while (!queue.isEmpty()) {
        Node u = queue.poll()

        if (u.level == -1) {
            u.level = 0
        }

        if (u.level == n) continue

        Node v = new Node(u.level + 1, u.profit, u.weight, u.bound)

        // Take the current item
        v.weight += items[u.level].weight
        v.profit += items[u.level].value

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

        v.bound = bound(v, n, W, items)
        if (v.bound > maxProfit) queue.add(v)

        // Not take the current item
        v = new Node(u.level + 1, u.profit, u.weight, u.bound)
        v.bound = bound(v, n, W, items)
        if (v.bound > maxProfit) queue.add(v)
    }

    return maxProfit
}

def main() {
    List<Item> items = [
        new Item(60, 10),
        new Item(100, 20),
        new Item(120, 30)
    ]
    int W = 50

    println("Maximum profit: ${knapsack(W, items)}")
}

main()

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

ในแง่ของเวลา, Branch and Bound มักจะมีความซับซ้อนที่สูงมากในกรณีที่เลวร้าย แต่ด้วยการตัดที่มีประสิทธิภาพ จะช่วยลดจำนวนการประมวลผลในหลาย ๆ กรณี โดยทั่วไปมันมีความซับซ้อนที่สามารถพัฒนาเป็น O(2^n) แต่ในหลาย ๆ กรณีอาจจะมีความเร็วในการทำงานที่ดีกว่านั้น

ข้อดีและข้อเสียของ Branch and Bound Algorithm

#### ข้อดี

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

#### ข้อเสีย

1. ใช้เวลาในการประมวลผลนานในปัญหาที่ใหญ่: ในกรณีที่เลวร้าย, อาจใช้เวลานานสาหัสในการค้นหา 2. ซับซ้อนในการ Implement: ผู้เขียนอาจพบว่าการเขียนโค้ดเพื่อตระหนักถึงแนวทาง Branch and Bound นั้นอาจเป็นเรื่องท้าทาย

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

 

 

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