เปลี่ยนแล้วแก้ (Trasform and Conquer)

ดร.บุญญฤทธิ์ อุยยานนวาระ
ภาควิชาคอมพิวเตอร์และเทคโนโลยีสารสนเทศ
สถาบันเทคโนโลยีนานาชาติสิรินธร
มหาวิทยาลัยธรรมศาสตร์


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

การเปลี่ยนสภาพปัญหาพอจะแบ่งแยกได้เป็น 3 ประเภทย่อยด้วยกัน คือ

  • Instance Simplification
    เป็นการเปลียนรูปแบบข้อข้อมูลขาเข้า หรือ input ให้อยู่ในรูปแบบที่จัดการง่ายขึ้น มีระเบียบขึ้น ก่อนที่จะแก้ปัญหานั้น
  • Representation Change
    เป็นการเปลียนรูปแบบข้อข้อมูลขาเข้า หรือ input ให้มีรูปร่างหน้าตาที่ไม่เหมือนเดิม โดยที่รูปร่างใหม่ของ input จะทำให้เราใช้มันในการแก้ปัญหา ได้ง่ายขึ้น
  • Problem Reduction 
    ประเภทที่ 3 นี้ ไม่เพียงแค่ เป็นการเปลียนรูปแบบข้อข้อมูลขาเข้า แต่เราเปลี่ยนทั้งปัญหาเลย เปลี่ยนมันไปเป็นปัญหาใหม่ ที่ไม่เหมือนเดิม โดยปัญหาที่เปลี่ยนไปใหม่ ควรจะเป็นปัญหาที่ได้รับการแก้ได้แล้ว มี algorithm ที่รองรับอยู่แล้ว

เราลองมาดูตัวอย่างของแต่ละรูปแบบของการแก้ปัญหาทั้ง 3 แบบกันครับ

Instance Simplification
ไอเดียของการแก้ปัญหาด้วยการทำให้ input อยู่ในรูปที่ง่ายขึ้น เห็นจะไม่มีตัวอย่างไหนที่ชัดเจนเท่ากับการ ทำ presort (เรียงข้อมูลซะก่อน) เพราะมีปัญหาหลายปัญหาที่สามารถจะแก้ได้ง่ายขึ้นหากข้อมูลอยู่ในแบบที่ได้รับการจัดเรียงแล้วเป็นอย่างดี ยกตัวอย่างเช่น

  • searching
    ปัญหาการค้นหาข้อมูล ลองคิดดูง่ายๆ ว่าถ้าเรามีข้อมูลอยู่ 1,000,000 ตัว และทั้งล้านตัวนี้วางปนกันมั่วไปหมด แล้วเราต้องการจะหาของชิ้นที่ 8954 ว่ามันอยู่ตรงไหนในกองนี้ เราต้องทำการคนหาไปทีละชิ้น ทีละชิ้น ไปจนกว่าจะเจอ ซึ่งถ้าโชคไม่ดีเราก็ต้องหาไปจนชิ้นสุดท้ายเลย
    แต่ถ้าเราทำการ sort ข้อมูลเสียก่อน ซึ่งตรงนี้เรารู้อยู่แล้วว่าใช้ O(n log n) ด้วย Quick Sort แล้วก็ทำการค้นหาด้วย Binary Search ซึ่งตรงนี้จะใช้ O(log n) ถ้าเป็นแบบนั้นแล้ว ประสิทธิภาพของการค้นหาด้วยวิธีนี้คือ

    Presorting & Search = O(n log n) + O(log n) = O(n log n)

    จะเห็นได้ว่าแม้ว่าเราจะทำการ sort ข้อมูลก่อน efficiency class ของกรรมวิธีนี้ก็ไม่ได้เลวร้าย และอยู่ในระดับของ O(n log n) ซึ่งถือว่าดีมาก 

    บางคนอาจจะแย้งว่า เอ! ไม่เห็นต้อง sort ก่อนเลยนี่ การ Search ก็ใช้วิธีหาทื่อๆแบบ sequential search คือไล่หาไปทีละตัว เลวร้ายสุด มันก็ใช้แค่ O(n) แค่นั้นเอง ซึ่งถูกต้องเลยครับ ถ้าหากว่าเราต้องการค้นหาข้อมูลเพียง 1 ตัว และ เพียงครั้งเดียว จากชุดข้อมูล 1,000,000 ชิ้นนี้ ก็ไม่จำเป็นต้องเสียเวลา sort แต่ถ้าหากว่า คุณต้องการ search ข้อมูล ซัก 20 ตัว แค่นี้การทำ presort ก็คุ้มแล้วครับ เพราะ ถ้าไม่ทำ presort คุณก็ใช้เวลาประมาณ 20 x 1,000,000 (หาข้อมูล 1 ชิ้น จาก 1,000,000 ข้อมูล 20 ครั้ง) แต่ถ้าทำ presort ก่อนก็จะเสียเวลาประมาณ 1,000,000 x log (1,000,000) หรือ ~ 1,000,000 x 20 นั่นเอง นั่นแปลว่าถ้าคุณต้องการหาข้อมูลมากกว่า log n ตัว การทำ presort ก็จะคุ้มสุดๆ
  • element uniqueness - checking if all elements are distinct 
    ต้องการจะหาว่ามีข้อมูลซ้ำหรือปล่าว เหมือนเดิม ถ้าเรามีข้อมูล 1,000,000 ตัว ที่ไม่เรียงลำดับ อยู่แบบมั่วๆ แล้วเราต้องการตรวจสอบว่ามีข้อมูลไหนซ้ำกันหรือป่าว ถ้าแก้ปัญหานี้แบบ brute force ทื่อๆถึกๆ ก็ทำได้โดยไล่หาทีละตัวเลย โดยเริ่มจากตัวที่ 1 แล้วเอาไปเปรียบเทียบกับ 999,999 ตัวที่เหลือ ถ้าไม่เจอตัวซ้ำเลยก็จดเอาไว้ว่าตัวที่ 1 ไม่ซ้ำใคร แล้วเราก็ทำจากตัวที่ 2 แล้วเอาไปเปรียบเทียบกับอีก 999,998 ตัวที่เหลือ ถ้าไม่เจอตัวซ้ำเลยก็จดเอาไว้ว่าตัวที่ 2 ไม่ซ้ำใครอีกไปแบบนี้เรื่อยๆ (เอ พอจะบอกได้มั้ยว่า บิ๊กโอ ของวิธีนี้มันอยู่ใน order เท่าไหร่เอ่ย)

    แต่ถ้าหากว่าเรา presort ข้อมูลก่อน ซึ่งแน่นอนว่ามันเสียเวลาไป O(n log n) จาก Quick Sort แล้วเราเพิ่มขั้นตอนการหาว่าตัวไหนซ้ำ ก็ด้วยการ ทำ sequential ดูไปทั้งลิสต์ว่าตัวที่อยู่ติดกันเหมือนกันหรือป่าว (ถ้ามีตัวซ้ำเวลาเอามาเรียงค่าแล้ว ตัวที่ซ้ำกันจะต้องอยู่ติดกันแน่นอน ซึ่งการสแกนทั้งลิสต์นี้ก็ใช้ ไปอีก O(n) แค่นั้นเอง เพราะฉนั้นโดยรวม ถ้าเราทำ presort ก่อนแล้วค่อยหาก็จะเสียเวลาประมาณ O(n log n) เพราะ

    Presorting & Search = O(n log n) + O(ln) = O(n log n)

    ซึ่งดีกว่าไม่ทำ presort ด้วยซ้ำไป

จะเห็นได้ว่าการทำ presort เป็นวิธีหนึ่งที่ทำให้ input อยู่ในรูปที่ง่ายขึ้น ซึ่งทำให้เราแก้ปัญหาได้ดีขึ้นนั่นเอง และจริงๆแล้ว การทำให้ input อยู่ในรูปที่ง่ายขึ้นก็มีหลากหลายวิธีขึ้นอยู่กับรูปแบบของ input ที่เข้ามานั่นเอง


Representation Change
การเปลี่ยน input ไปเป็น tree
Binary Tree
Binary Search Tree

AVL Tree
ลองดูกรณีนี้ ตัวอย่างจาก จิระ (เดี๋ยวทำเป้น graphic)
9
8 12
11 15
14
เมื่อ 14 ถูก insert เข้าไป node ที่มีปัญหาคือ 9 จึงต้องใช้ L(9) เพื่อแก้
บางคนใช้ R(12) ซึ่งอย่างนี้จะทำให้ต้องทำการ rotate หลายรอบ และ จริงๆก็ไม่ใช่ด้วย เพราะหลังจาก insert 14 เข้าไป node 12 ไม่ได้มีปัญหา (ดูจากค่า AVL)


2-3 Tree 

Problem Reduction 
การเปลี่ยนปัญหาเป็นปัญหาของ Graph