สนุกกับ “อัลกอริทึมแบบประมาณ”

💡 ไอเดียเด็ด

แทนที่จะรอคำตอบที่ดีที่สุดเป็นล้านปี เราออกแบบวิธีที่ให้คำตอบ “ดีพอ” ได้ในพริบตา

สิ่งที่เจ๋งคือ เราจะ การันตีเป็นตัวเลข ได้เลยว่าคำตอบของเราแย่กว่าคำตอบที่ดีที่สุด ไม่เกินกี่เท่า ตัวเลขนี้เรียกว่า อัตราการประมาณ (α)

เช่น α = 2 แปลว่า “คำตอบของเราอาจยาวเป็น 2 เท่าของทางที่สั้นที่สุด แต่ไม่เกินนั้นแน่นอน”

💡 ไอเดียเด็ด: “น้องโลภ” (Greedy)

กฎง่ายมาก: เลือกสถานีที่ครอบคลุมหมู่บ้าน “ใหม่” ได้เยอะที่สุดก่อนเสมอ แล้วทำซ้ำจนครบ

เหมือนเวลาเก็บของเล่นเข้ากล่อง เราหยิบกองที่ใหญ่ที่สุดก่อน จะได้เสร็จไวๆ

💡 ไอเดียเด็ด

วิธีโลภ (List): ใครว่างก่อน (งานน้อยสุด) รับงานชิ้นต่อไป

งานใหญ่ก่อน (LPT): เรียงงานจากใหญ่ไปเล็กก่อน แล้วค่อยแจก — ฉลาดกว่าเยอะ!

การค้นหาเฉพาะที่ (Local Search): เริ่มจากการแบ่งมั่วๆ แล้ว “สลับงาน” ทีละนิดถ้าทำให้ดีขึ้น เหมือนค่อยๆ ปีนขึ้นเขาทีละก้าว

💡 ไอเดียเด็ด

การหาคำตอบเป๊ะๆ ช้ามากเมื่อ “คุณค่า” เป็นตัวเลขใหญ่ๆ

เคล็ดลับคือ ปัดตัวเลขคุณค่าให้หยาบลง (เช่น ปัดเป็นหลักสิบ) ทำให้คอมคิดเร็วขึ้นมหาศาล แต่คำตอบที่ได้ยัง เกือบดีที่สุด เหมือนปัดราคาสินค้าจาก 197 เป็น 200 เพื่อคิดเลขในใจง่ายๆ

💡 ไอเดียเด็ด

โปรแกรมเชิงเส้น (LP) คือการ “โกง” นิดหน่อย: เรายอมให้คำตอบเป็น เศษส่วน ได้ก่อน เช่น “เปิดร้าน 0.7 ร้าน” ฟังดูแปลก แต่คอมแก้แบบนี้ได้ เร็วมาก

จากนั้นเรา ปัดเศษ กลับเป็นจริง เช่น 0.7 → เปิดจริง (1), 0.2 → ไม่เปิด (0)

💡 ไอเดียเด็ด

ลองง่ายสุด: ให้แต่ละคนโยนเหรียญ ออกหัวไปห้อง A ออกก้อยไปห้อง B

น่าทึ่งมาก: โดยเฉลี่ยแล้ว วิธีมั่วๆ นี้จะแยกคู่แกล้งกันได้ ถึงครึ่งหนึ่ง ของจำนวนเส้นทั้งหมดเสมอ!

💡 ไอเดียเด็ด (รางวัลโนเบลแห่งวงการ!)

แทนคนแต่ละคนด้วย ลูกศรชี้ทิศ บนลูกบอล โดยพยายามให้คู่ที่แกล้งกัน ชี้คนละทาง

จากนั้น สุ่มหั่นลูกบอลด้วยมีดบางๆ (เส้นตรงสุ่ม) ใครอยู่ฝั่งไหนก็ไปห้องนั้น เรขาคณิตช่วยให้แยกคู่แกล้งกันได้เยอะกว่าการโยนเหรียญเฉยๆ!

💡 ไอเดียเด็ด

คิดเหมือน การประมูล/ต่อราคา: แต่ละเมืองค่อยๆ “เพิ่มงบ” ของตัวเองขึ้นเรื่อยๆ (เหมือนวงกลมที่ขยายออก) พอ งบของสองฝั่งมาเจอกันที่สายเส้นไหน และมัน “คุ้ม” เราก็ ซื้อสายเส้นนั้น

ความเจ๋งคือ “งบ” ที่เพิ่มขึ้นกลายเป็น ใบรับรอง พิสูจน์ได้ว่าคำตอบเราดีจริง โดยไม่ต้องเทียบกับคำตอบที่ดีที่สุด

💡 ไอเดียเด็ด

เปลี่ยน “ความสัมพันธ์” ให้กลายเป็น ระยะทางบนแผนที่ (เรียกว่า metric) จุดที่ควรอยู่ห้องเดียวกันให้ “ใกล้กัน” จุดที่ควรแยกให้ “ไกลกัน”

พอเป็นแผนที่ระยะทางแล้ว เราก็แค่ ขีดเส้นแบ่งเขต ตรงที่บางที่สุด — ง่ายขึ้นเยอะ!