CoE KKU

ในกรณีที่เรามี equivalence relation ~, แล้วจะมีปัญหาพื้นฐานที่ต้องตอบเสมอ คือ สำหรับ a และ b ใด ๆ แล้ว a ~ b หรือไม่ ถ้าความสัมพันธ์นี้ได้รับการจัดเก็บในรูปของอะเรย์ 2 มิติของค่า Boolean แล้วเราก็จะได้คำตอบทันที่ด้วยเวลาที่เป็นค่าคงที่ แต่ปกติแล้วความสัมพันธ์ระหว่างมันไม่ได้มีแสดงตัวตนของมันออกมาอย่างชัดเจน

ดังเช่น ถ้ากำหนด equivalence relation, ~ ให้กับเซตที่มีสมาชิก 5 ตัว คือ { a1, a2, a3, a4, a5 } นั่นคือ ประกอบด้วยสมาชิก 25 คู่ ซึ่งแต่ละคู่อาจจะสัมพันธ์กันหรือไม่ก็ได้ และถ้า a1 ~ a2, a3 ~ a4, a5 ~ a1, a4 ~ a2 แล้วก็จะอนุมาณได้ว่าทุกคู่สัมพันธ์กัน สิ่งที่ต้องการคือ เราจะอนุมานคำตอบนี้ อย่างรวดเร็วได้อย่างไร

Equivalence class ของสมาชิกตัวหนึ่งคือ a ∈ S คือ เซตย่อย (subset) ของ S ที่ประกอบด้วยสมาชิกทั้งหมดที่สัมพันธ์กับ a จะเห็นว่า equivalence classes ทำให้เกิด partition ของ S คือ สมาชิกแต่ละตัวของ S ปรากฏอยู่ใน equivalence class เดียวเท่านั้น เพื่อที่จะหาว่า a ~ b หรือไม่ เราเพียงแต่ตรวจสอบว่า a และ b อยู่ใน equivalence class เดียวกันหรือไม่เท่านั้น ซึ่งสิ่งนี้คือ วิธีที่เราใช้ในการแก้ปัญหา equivalence problem นั่นเอง

ถ้าให้อินพุตเริ่มต้นเป็นกลุ่มของเซตจำนวน N เซต แต่ละเซตมีสมาชิกหนึ่งตัว เซตในสภาวะเริ่มต้นแบบนี้ก็หมายความว่า relations ทั้งหมด (ยกเว้น reflexive relations) เป็น false และเนื่องจากแต่ละเซตมีสมาชิกที่แตกต่างกัน ดังนั้น Si ∩ Sj = Ø; ซึ่งเป็น sets disjoint

อนุญาตให้มีการดำเนินการได้สองอย่าง คือ การดำเนินการแรกคือการทำงาน find ซึ่งให้ค่ากลับเป็นชื่อของเซต (ซึ่งก็คือ equivalence class) ที่ บรรจุสมาชิกตัวที่กำหนดอยู่ การดำเนินการที่สอง คือ การทำงานการเพิ่มความสัมพันธ์ (adds relations) ถ้าเราต้องการเพิ่มความสัมพันธ์ a ~ b ก็ต้องตรวจดูก่อนว่า a และ b มีความสัมพันธ์กันอยู่เดิมแล้วหรือไม่ ซึ่งทำได้ด้วยการใช้ finds กับ a และ b เพื่อหาว่ามันอยู่ใน equivalence class เดียวกันหรือไม่ ถ้าไม่ เราก็ใช้การทำงาน union อันเป็นการควบรวม equivalence class ทั้งสองที่มีสมาชิก a และที่มีสมาชิก b อยู่เข้าด้วยกันเป็น equivalence class ใหม่ที่มีสมาชิกทั้งสอง ในแง่ของเซตแล้ว ผลของการทำ union คือการสร้างเซตใหม่ Sk = Si ∪ Sj, และทำลายเซตเดิมและคงสภาพความเป็น disjointness ของเซตทั้งหมด อัลกอริทึมที่ใช้เพื่อการดำเนินการนี้เรียกว่า disjoint set union/find algorithm

อัลกอริทึมดังกล่าวนี้เป็นอัลกอริทึมที่มีพลวัตมาก กล่าวคือในระหว่างทางของการทำงานของอัลกอริทึม เซตต่าง ๆ จะมีการเปลี่ยนแปลงเนื่องการการทำงานของ union อีกทั้งการทำงานของอัลกอริทึมต้องเป็นแบบ on-line คือขณะทำงาน find นั้น มันต้องให้คำตอบเสียก่อนที่จะทำงานต่อไปได้ มีความเป็นไปได้ที่จะทำงานแบบ off-line อัลกอริทึมแบบ off-line ทำให้เรามองเห็นลำดับการทำงานทั้งหมดของการทำงาน union และการทำงาน find ความแตกต่างระหว่างอัลกอริทึมแบบ on-line และแบบ off-line นั้นเทียบได้กับการสอบข้อเขียนที่ต้องเขียนคำตอบลงในกระดาษ (เทียบได้กับการการทำงานแบบ off-line ที่เราต้องตอบคำถามให้เสร็จสิ้นภายในเวลาที่กำหนด) และการสอบปากเปล่า (เทียบได้กับการทำงานแบบ on-line คือต้องตอบคำถามขณะนั้นก่อนที่จะถามคำถามต่อไปได้)

จะเห็นว่าอัลกอริทึมที่กล่าวมานั้นไม่ได้ใช้การเปรียบเทียบค่าของสมาชิกระหว่างกัน สิ่งที่ต้องการเป็นเพียงที่อยู่ของสมาชิกเท่านั้น ด้วยเหตุนี้เองเราจึงสามารถกำหนดให้สมาชิกแต่ละตัวมีหมายเลขกำกับเรียงลำดับเป็นจาก 0 ถึง N – 1 ซึ่งทำได้ง่ายด้วยการใช้ hashing ดังนั้น เราจะกำหนดให้ค่าเริ่มต้นมี Si = { i } ที่ i = 0 ถึง N – 1

นอกจากนี้ยังเห็นได้ว่า ชื่อของเซตที่ได้จากการทำงาน find นั้นก็ไม่มีกฎเกณฑ์ใด ๆ สิ่งที่ต้องการคือ find(a) == find(b) มีค่าเป็น true ถ้า a และ b อยู่ในเซตเดียวกันเท่านั้น

มีวิธีการแก้ปัญหาดังกล่าวข้างบนอยู่สองวิธี วิธีการแรกเป็นการทำงานที่ทำให้การทำงาน find ด้วยเวลาคงที่ในกรณี worst-case และอีกวิธีคือทำให้การทำงาน union ด้วยเวลาคงที่ในกรณี worst-case และจนบัดนี้ยังไม่มีวิธีที่ทำให้การทำงานทั้ง find และ union ให้ได้เวลาคงที่ในกรณี worst-case ได้พร้อมกันทั้งสองการทำงาน

กล่าวโดยย่อสำหรับวิธีการแรก เพื่อให้สามารถทำงาน find ได้อย่างรวดเร็ว เราจะเก็บชื่อของ equivalence class สำหรับสมาชิกแต่ละตัวไว้ภายในอะเรย์ ดังนั้นการทำงาน find จึงใช้เวลา $O(1)$ ในการตรวจสอบ ในการทำงาน union(a, b) ถ้าสมมุติให้ a อยู่ใน equivalence class i และ b อยู่ใน equivalence class j แล้ว เราก็จะทำการ scan ไปในอะเรย์และเปลี่ยนสมาชิกของ i ทั้งหมดไปเป็นของ j แต่การ scan ใช้เวลาเป็น $\Theta(N)$ และต้องทำงานนี้ทั้งสิ้น N – 1 unions (ซึ่งเป็นจำนวนสูงสุดเนื่องจากแต่ละตัวอยู่ในเซตแยกจากกันหนึ่งเซต) ดังนั้นจึงต้องใช้เวลา $\Theta(N^2)$ ถ้าเรามีการทำงาน find เป็นจำนวน $\Omega(N^2)$ ครั้งแล้วประสิทธิภาพการทำงานนี้ก็เป็นที่ยอมรับได้ เนื่องจาก running time รวมจะเป็น $O(1)$ สำหรับแต่ละการทำงาน union หรือ find ตลอดการทำงานของอัลกอริทึม แต่ถ้ามีการทำงาน finds น้อยกว่าแล้วประสิทธิภาพที่ได้ก็ยอมรับไม่ได้

แนวทางหนึ่งที่ใช้คือ การเก็บสมาชิกทั้งหมดที่อยู่ใน equivalent class เดียวกันไว้ใน linked list ซึ่งทำให้ประหยัดเวลาในการ update เนื่องจากเราไม่ต้องค้นหาในอะเรย์ทั้งอะเรย์ อย่างไรก็ตามมันไม่ได้ช่วยลด asymptotic running time เนื่องจากเป็นไปได้ที่ต้องใช้เวลาในการทำงาน update เป็นจำนวน $\Theta(N^2)$ ครั้งตลอดการทำงานของอัลกอริทึม

ในกรณีที่เราเก็บข้อมูลแสดงขนาดของ equivalent class ไว้ด้วยและขณะเมื่อทำงาน union เราจะเปลี่ยนชื่อของ equivalent class ที่มีขนาดเล็กกว่าไปเป็นของตัวที่มีขนาดใหญ่กว่าแล้วนั่นก็คือ เวลาทั้งหมดที่ใช้ในการควบรวมจำนวน N – 1 ครั้ง ก็จะเป็น $O(N\ log\ N)$ เนื่องจากสมาชิกแต่ละตัวจะสามารถเปลี่ยน equivalent class ของมันได้มากที่สุดคือ $log\ N$ ครั้ง เพราะแต่ละครั้งที่ class ของมันถูกเปลี่ยนไปนั้นจะทำให้ equivalent class ตัวใหม่ของมันมีขนาดใหญ่ขึ้นเป็นสองเท่าของตัวเก่าเป็นอย่างน้อย ด้วยกรรมวิธีดังที่กล่าวนี้ ลำดับการทำงาน find จำนวน M ครั้ง และใช้การทำงาน union จำนวน N – 1 ครั้ง จึงใช้เวลาอย่างมากที่สุดเป็น $O(M + N\ log\ N)$

ต่อจากนี้ไปจะกล่าวถึงการแก้ปัญหา union/find ที่เป็นการใช้ union ได้อย่างง่ายดายแต่การทำงาน find จะยุ่งยาก แต่ running time ของลำดับการทำงาน find ที่สูงสุด M ครั้งและการทำงาน union สูงสุด N – 1 ครั้ง ก็ยังคงใช้เวลามากกว่า $O(M + N)$ เพียงเล็กน้อยเท่านั้น