การทำความรู้จักกับ Greedy Algorithm ผ่าน Haskell

 

ในโลกของการเขียนโปรแกรมและโครงสร้างข้อมูล เรามีเทคนิคการแก้ปัญหามากมาย หนึ่งในนั้นคือ Greedy Algorithm (อัลกอริธึมแบบตะกละ) ที่มักถูกใช้เพื่อแก้ปัญหาที่ต้องเลือกคำตอบที่ดีที่สุดโดยมองจากข้อมูลในแต่ละขั้นตอน ซึ่งจะเป็นการตัดสินใจ "ในตอนนั้น" โดยไม่สนใจผลลัพธ์ในอนาคตมากนัก แต่แน่นอนว่าไม่ใช่ว่าอัลกอริธึมทุกอะไรก็จะทำงานได้ดีโดยใช้ Greedy Algorithm เสมอ

 

Greedy Algorithm คืออะไร?

Greedy Algorithm เป็นแนวทางการพัฒนาอัลกอริธึมที่มุ่งเป้าไปที่การเลือกทำทางเลือกที่ดีที่สุดในแต่ละขั้นตอน โดยตั้งอยู่บนหลักการถือว่าการเลือกในปัจจุบันจะทำให้เกิด "ผลลัพธ์ที่ดีที่สุดในอนาคต" โดยไม่ต้องพิจารณาเงื่อนไขหรือทางเลือกในอนาคต ตัวอย่างเช่น ในปัญหาใส่สัมภาระในกระเป๋า (Knapsack Problem) หากเราเลือกสิ่งของที่มีค่าน้ำหนักน้อยลงในแต่ละขั้นตอน แทนที่จะพิจารณาทุกตัวเลือกในระยะยาว

Use Case ของ Greedy Algorithm

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

 

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

เราจะเริ่มต้นด้วยตัวอย่างเบื้องต้นของ Greedy Algorithm ซึ่งคือปัญหาเสื้อผ้าที่มีการเช่า โดยเราต้องการหาค่าใช้จ่ายรวมที่น้อยที่สุดในการเช่าเสื้อผ้าดังกล่าว

 import Data.List (sortBy)
import Data.Ord (comparing)

data Item = Item { value :: Int, weight :: Int } deriving (Show)

-- ฟังก์ชันคำนวณค่า Ratio ของ value ต่อ weight
valueDensity :: Item -> Double
valueDensity item = fromIntegral (value item) / fromIntegral (weight item)

-- ฟังก์ชันแก้ไขปัญหาด้วย Greedy Algorithm
greedyKnapsack :: Int -> [Item] -> Double
greedyKnapsack capacity items = go capacity sortedItems 0
  where
    sortedItems = sortBy (comparing (negate . valueDensity)) items
    go _ [] totalVal = totalVal
    go cap (x:xs) totalVal
      | weight x <= cap = go (cap - weight x) xs (totalVal + fromIntegral (value x))
      | otherwise = totalVal -- สถานการณ์ที่ไม่สามารถใส่ไอเทมได้

-- ตัวอย่างการใช้
main :: IO ()
main = do
    let items = [Item 60 10, Item 100 20, Item 120 30]
    let capacity = 50
    print $ greedyKnapsack capacity items

ในโค้ดนี้ เรามีการสร้างแบบข้อมูลของ `Item` ที่ประกอบด้วย `value` (ค่า) และ `weight` (น้ำหนัก) จากนั้นเราจะเริ่มใช้ฟังก์ชัน `greedyKnapsack` ในการคำนวณการประมาณค่าใช้จ่ายที่น้อยที่สุดตามโควต้า (capacity) โดยจะเรียงตามอัตราส่วนของค่าและน้ำหนัก

 

วิเคระห์ความซับซ้อน

เวลา (Time Complexity)

Greedy Algorithm มักจะทำงานใน O(n log n) ในกรณีที่นี่ใช้การจัดเรียงรายการแรก และ O(n) สำหรับการวนลูปในการคำนวณ

พื้นที่ (Space Complexity)

พื้นที่ซับซ้อนส่วนใหญ่จะขึ้นอยู่กับข้อมูลที่ถูกใช้ในการจัดเรียงดังนั้นอาจจะอยู่ในระดับ O(n) ในการจัดเก็บข้อมูลชั่วคราว

 

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

ข้อดี

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

ข้อเสีย

1. ไม่แน่นอน: ไม่สามารถรับประกันว่าผลลัพธ์จะดีที่สุดเสมอไป 2. ขอบเขตแคบ: บางครั้งอาจจะไม่เหมาะกับปัญหาที่มีหลายปัจจัยหรือการพิจารณาระยะยาว

 

สรุป

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

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

 

 

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