เข้าใจ Algorithm: Branch and Bound ด้วยภาษา Ruby

 

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

 

Branch and Bound คืออะไร?

*Branch and Bound* เป็นอัลกอริธึมที่ใช้ในการหาโซลูชันที่ดีที่สุดของปัญหาที่เป็นแบบ Optimization โดยเฉพาะปัญหาที่มีการตัดสินใจที่ซับซ้อน เช่น ปัญหา Traveling Salesman Problem (TSP), Knapsack Problem, และอื่น ๆ

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

 

Use Case ที่น่าสนใจ

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

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

ต่อไปนี้เป็นตัวอย่างโค้ดที่ใช้โครงสร้าง Branch and Bound ในการแก้ปัญหา Knapsack Problem:

 class Item
  attr_accessor :value, :weight

  def initialize(value, weight)
    @value = value
    @weight = weight
  end
end

class Node
  attr_accessor :level, :profit, :bound, :weight

  def initialize(level, profit, weight, bound)
    @level = level
    @profit = profit
    @weight = weight
    @bound = bound
  end
end

def bound(node, n, W, items)
  return 0 if node.weight >= W

  profit_bound = node.profit

  j = node.level + 1
  total_weight = node.weight

  while j < n && total_weight + items[j].weight <= W
    total_weight += items[j].weight
    profit_bound += items[j].value
    j += 1
  end

  if j < n
    profit_bound += (W - total_weight) * items[j].value / items[j].weight
  end

  profit_bound
end

def knapsack(W, items)
  items.sort_by! { |item| -item.value.to_f / item.weight } # Sort by value/weight ratio

  n = items.length
  queue = []
  root = Node.new(-1, 0, 0, 0)
  root.bound = bound(root, n, W, items)
  queue.push(root)

  max_profit = 0

  while !queue.empty?
    node = queue.shift

    if node.level == -1
      level = 0
    else
      level = node.level + 1
    end

    if level < n
      # Include the next item
      with_item = Node.new(level, node.profit + items[level].value, node.weight + items[level].weight, 0)
      if with_item.weight <= W && with_item.profit > max_profit
        max_profit = with_item.profit
      end
      with_item.bound = bound(with_item, n, W, items)
      if with_item.bound > max_profit
        queue.push(with_item)
      end

      # Exclude the next item
      without_item = Node.new(level, node.profit, node.weight, 0)
      without_item.bound = bound(without_item, n, W, items)
      if without_item.bound > max_profit
        queue.push(without_item)
      end
    end
  end

  max_profit
end

# ตัวอย่างการใช้งาน
items = [Item.new(60, 10), Item.new(100, 20), Item.new(120, 30)]
W = 50
puts "Maximum profit is: #{knapsack(W, items)}"

ในโค้ดข้างต้น เราได้สร้างคลาส `Item` เพื่อเก็บค่าของสินค้าแต่ละชิ้น มีคุณสมบัติเป็นมูลค่าและน้ำหนัก จากนั้นใช้คลาส `Node` เพื่อกำหนดต้นไม้ในการตัดสินใจ จากนั้นก็มีฟังก์ชัน `bound` ที่คำนวณขอบเขตของมูลค่า และฟังก์ชัน `knapsack` ที่จะใช้คิวในการสำรวจแนวทางต่าง ๆ

 

วิเคราะห์ Complexity

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

 

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

ข้อดี:

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

ข้อเสีย:

1. อาจมีความซับซ้อนในขั้นตอนการประเมิน: ในบางครั้งการตั้งขอบเขตอาจไม่ชัดเจน 2. ต้องการหน่วยความจำสูง: การใช้คิวในการเก็บสถานะที่เกิดขึ้นอาจทำให้หน่วยความจำสูงขึ้นในบางกรณี

 

สรุป

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

 

 

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