ทำความรู้จักกับ Branch and Bound Algorithm และการใช้งานด้วยภาษา Dart

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

Branch and Bound คืออะไร?

Branch and Bound (B&B) เป็นเทคนิคที่ใช้ในการแก้ปัญหาการค้นหา และค้นหาค่าที่ดีที่สุดในกลุ่มปัญหา NP-Hard. วิธีการทำงานหลักๆ ของ B&B คือการตัดสินใจในแต่ละสาขาของปัญหา (Branching) และใช้เกณฑ์ในการตัดสินว่าควรจะขยายสาขานั้นต่อไปหรือไม่ (Bounding) เทคนิคนี้ช่วยให้เราสามารถลดจำนวนกรณีที่ต้องพิจารณาและสามารถหาคำตอบที่ดีที่สุดในเวลาที่เร็วขึ้น

การใช้ Branch and Bound

B&B มักนำมาใช้ในปัญหาการจัดระเบียบเช่น:

ตัวอย่าง Use Case ในโลกจริง

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

ตัวอย่างโค้ดด้วยภาษา Dart

มาดูตัวอย่างโค้ดที่ใช้ Branch and Bound ในการแก้ปัญหา Knapsack Problem กันนะครับ

 class Item {
  final int weight;
  final int value;

  Item(this.weight, this.value);
}

class Node {
  int level;
  int profit;
  int weight;
  double bound;

  Node(this.level, this.profit, this.weight, this.bound);
}

double calculateBound(int n, int W, List<Item> items, Node node) {
  if (node.weight >= W) return 0;

  int profitBound = 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) * items[j].value / items[j].weight;

  return profitBound.toDouble();
}

void branchAndBound(int n, int W, List<Item> items) {
  List<Node> queue = [];
  Node root = Node(-1, 0, 0, 0.0);
  root.bound = calculateBound(n, W, items, root);
  queue.add(root);

  int maxProfit = 0;

  while (queue.isNotEmpty) {
    Node node = queue.removeAt(0);

    if (node.level == n - 1) continue;

    int nextLevel = node.level + 1;

    // Include the next item
    Node includeNode = Node(nextLevel, node.profit + items[nextLevel].value,
                            node.weight + items[nextLevel].weight, 0.0);
    if (includeNode.weight <= W) {
      if (includeNode.profit > maxProfit) maxProfit = includeNode.profit;
      includeNode.bound = calculateBound(n, W, items, includeNode);
      if (includeNode.bound > maxProfit) queue.add(includeNode);
    }

    // Exclude the next item
    Node excludeNode = Node(nextLevel, node.profit, node.weight, 0.0);
    excludeNode.bound = calculateBound(n, W, items, excludeNode);
    if (excludeNode.bound > maxProfit) queue.add(excludeNode);
  }

  print("Maximum Profit: $maxProfit");
}

void main() {
  List<Item> items = [
    Item(1, 1),
    Item(2, 6),
    Item(3, 10),
    Item(5, 12)
  ];

  int W = 5;
  branchAndBound(items.length, W, items);
}

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

วิเคราะห์ Complexity

ในแง่ของความซับซ้อน (Complexity) Normal Branch and Bound อาจมีความซับซ้อนเป็น O(2^n) ในกรณีที่เลวร้ายที่สุด แต่ด้วยการ "ตัด" สาขาที่ไม่สำคัญไป สามารถทำให้ความซับซ้อนไม่สูงมากนักในบริบทการใช้งานจริง

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

ข้อดี

ข้อเสีย

เชิญชวนให้ศึกษา Programming ที่ EPT

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

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