โครงสร้างข้อมูลเซตไม่มีส่วนร่วม

ในวิทยาการคอมพิวเตอร์ โครงสร้างข้อมูลเซตไม่มีส่วนร่วม (Disjoint-set data structure) เป็นโครงสร้างข้อมูลที่ใช้เก็บข้อมูลที่แบ่งเป็นหลาย ๆ เซต โดยที่แต่ละเซตไม่มีส่วนร่วมกันเลย (disjoint, nonoverlapping) โดยมีขั้นตอนวิธียูเนียนและค้นหา (union-find algorithm) เป็นขั้นตอนวิธีที่ดำเนินการบนโครงสร้างข้อมูลนี้ มีจุดประสงค์คือ 1. ต้องการทดสอบว่าสมาชิกสองตัวที่กำหนดให้อยู่ในเซตเดียวกันหรือไม่ 2. ต้องการรวมเซตสองเซตเข้าด้วยกันเป็นเซตใหญ่เพียงเซตเดียว
เพื่อที่ดำเนินการตามจุดประสงค์ จึงมีฟังก์ชันในการดำเนินการ 2 อย่างคือ
ค้นหา (Find) : จุดประสงค์เบื้องต้นเป็นการหาว่าสมาชิกที่ต้องการจะทดสอบอยู่ในเซตชื่ออะไร เพื่อที่จะได้นำมาตอบคำถามว่าสมาชิกสองตัวที่ต้องการจะทดสอบนั้นอยู่ในเซตเดียวกันหรือไม่ เนื่องจากจุดประสงค์ไม่ได้ต้องการชื่อเซตจริง ๆ ในการดำเนินการจึงอาจจะไม่ได้กำหนดชื่อของเซตจริง ๆ แต่ใช้วิธีการบางอย่างเพื่อให้ประมวลผลข้อมูลได้ง่าย
ยูเนียน (Union) : เป็นการรวมสองเซตที่กำหนดให้เข้าด้วยกันเป็นเพียงเซตเดียว
เนื่องจากโครงสร้างข้อมูลเซตไม่มีส่วนร่วมส่วนใหญ่จะดำเนินการด้วยขั้นตอน วิธียูเนียนและค้นหา จึงทำให้มีการเรียกโครงสร้างข้อมูลนี้ว่า โครงสร้างข้อมูลยูเนียนและค้นหา นอกจากนี้ อาจนิยามการดำเนินการ สร้างเซต (MakeSet) ซึ่งจะสร้างเซตตั้งต้นขึ้น โดยเซตตั้งต้นจะมีสมาชิกเพียงแค่ตัวเดียวเท่านั้น (เซตโทน) เมื่อใช้ 3 การดำเนินการนี้ร่วมกันจะสามารถแก้ไขปัญหาการแบ่งบางอย่างได้ (ดูที่หัวข้อการนำไปใช้งาน)
ตามที่ได้เกริ่นมาแล้วว่าจุดประสงค์ของการดำเนินการ ค้นหา อันที่จริงแล้วคือการทดสอบว่าสมาชิกสองตัวที่จะทดสอบนั้นอยู่ในเซตเดียวกันหรือไม่ ชื่อเซตจึงไม่สำคัญ เพื่อให้ประมวลผลข้อมูลได้ง่ายจึงมีการใช้ชื่อของสมาชิกตัวหนึ่งในเซตนั้นมาเป็นชื่อเล่นของเซต กล่าวคือให้สมาชิกตัวนั้นมาเป็นตัวแทนของทั้งเซตไปเลย
== รายการโยงเซตไม่มีส่วนร่วม ==
วิธีการสร้างโครงสร้างข้อมูลเซตไม่มีส่วนร่วมแบบง่ายที่สุดก็คือสำหรับแต่ละเซตให้สร้างรายการโยงขึ้นมา และให้สมาชิกตัวด้านหน้าสุดของรายการโยงเป็นตัวแทนของเซตนั้น
การสร้างเซต ก็คือการสร้างรายการโยงความยาว 1 ขึ้นเป็นจำนวนที่ต้องการ การยูเนียน ก็จะเป็นการนำรายการโยงสองรายการมาต่อกันในเวลาคงที่ ข้อเสียของการอิมพลีเมนต์แบบนี้คือในการค้นหาแต่ละครั้งจะต้องใช้เวลา Ω(n) จากการไล่จากสมาชิกตัวปัจจุบันไปยังสมาชิกตัวหน้าสุดเพื่อหาชื่อเซต
วิธีที่จะทำให้การดำเนินการค้นหาไม่ต้องเสียเวลาไล่ในรายการโยงถึง Ω(n) ก็คือสำหรับทุก ๆ สมาชิกในรายการโยง ให้มีตัวชี้โยงมายังสมาชิกตัวแรกสุดของรายการโยง ซึ่งจะทำให้การดำเนินการค้นหา ใช้เวลาเพียงแค่ O(1) เท่านั้น แต่ข้อเสียของวิธีนี้ก็คือในการยูเนียน จะต้องมาไล่ปรับปรุงตัวชี้ของสมาชิกทั้งหลายใหม่ให้ถูกต้องด้วย ทำให้การยูเนียน เสียเวลา Ω(n) แทน
สำหรับวิธีที่ใช้ตัวชี้มาช่วยนั้น หากมีการเก็บความยาวของรายการโยงไว้ในทุกขณะด้วย จะสามารถเพิ่มความเร็วในการดำเนินการได้โดยใช้ฮิวริสติก weighted-union heuristic ซึ่งมีหลักการว่าแทนที่การยูเนียนจะนำรายการโยงทั้ง 2 มาต่อกันตรง ๆ ให้ตรวจสอบก่อนว่ารายการโยงใดสั้นกว่า แล้วจึงนำรายการโยงที่สั้นไปต่อหลังจากรายการโยงที่ยาว ซึ่งหากทำตามขั้นตอนดังกล่าวจะทำให้การดำเนินการสร้างเซต ค้นหา และยูเนียน รวม m ครั้ง บนโครงสร้างข้อมูลเซตไม่มีส่วนร่วมที่มีสมาชิกทั้งหมด n ตัว ใช้เวลา O(m + n log n) ทั้งนี้หากไม่มีโครงสร้างข้อมูลที่ดีกว่ารายการโยงก็จะไม่สามารถทำให้เวลาในการดำเนินการเร็วกว่านี้ได้
=== วิเคราะห์ ===
สาเหตุที่การใช้ weighted-union heuristic ทำให้เวลาการดำเนินการทั้งหลายใช้เวลา O(m + n log n) มาจากเหตุผลที่ว่าการรวมรายการโยงขนาดสั้น ๆ เข้ากับรายการโยงขนาดยาว ๆ จะเสียเวลาเปลี่ยนตัวชี้ของรายการโยงขนาดสั้นเท่านั้น ดังนั้นกรณีเลวร้ายที่สุดก็จะเกิดจากการที่นำรายการโยงขนาดพอ ๆ กันมาต่อกันเสมอ ซึ่งจะทำให้การต่อแต่ละครั้งเสียเวลา O(n) แต่การที่นำมาต่อกันเช่นนี้ก็ทำให้เซตถูกยูเนียนเข้าด้วยกันอย่างรวดเร็ว ซึ่งโครงสร้างเซตไม่มีส่วนร่วมขนาด n จะมีการ ยูเนียน อย่างเลวร้ายได้มากสุดเพียง log n ครั้งเท่านั้น จึงทำให้เฉพาะการยูเนียนในกรณีเลวร้ายที่สุดเสียเวลา O(n log n)
ในการดำเนินการค้นหา ก็สามารถใช้ตัวชี้เพื่อไปยังสมาชิกตัวด้านหน้าสุดของรายการโยงได้ภายในเวลา O(1) ตามที่กล่าวมาแล้ว
แนวคิดในการนำเซตที่มีขนาดเล็กกว่าไปต่อเซตที่มีขนาดใหญ่กว่ายังปรากฏให้เห็นในโครงสร้างข้อมูลอื่น ๆ เช่นฮีปทวิภาค หรือฮีปฟีโบนัชชีอีกด้วย
== ป่าไม้เซตไม่มีส่วนร่วม ==
ป่าไม้เซตไม่มีส่วนร่วมเป็นโครงสร้างข้อมูลซึ่งจะใช้โครงสร้างข้อมูลต้นไม้ในการแทนแต่ละเซต และโครงสร้างข้อมูลต้นไม้นี้ก็จะจัดเก็บโดยใช้รูปแบบ Spaghetti stack กล่าวคือแต่ละจุดยอดจะโยงไปยังพ่อของตัวมัน ป่าไม้เซตไม่มีส่วนร่วมได้มีการคิดค้นโดย
Bernard A. Galler และ Michael J. Fischer ใน พ.ศ. 2507 โดยที่การวิเคราะห์ประสิทธิภาพของโครงสร้างข้อมูลนี้อย่างละเอียดตามมาหลังจากนั้นหลายปี
ในป่าไม้เซตไม่มีส่วนร่วมจะกำหนดให้ตัวแทนของแต่ละเซตคือจุดยอดที่เป็นรากของต้นไม้ ดังนั้นการดำเนินการค้นหา ก็คือการกระโดดสูงขึ้นไปเรื่อย ๆ จนกว่าจะเจอราก ส่วนการยูเนียนก็คือการดำเนินการค้นหากับต้นไม้ทั้งสองต้นเพื่อหารากของต้นไม้ทั้งสอง และนำรากของต้นไม้หนึ่งไปต่อกับรากของต้นไม้อีกต้น อาจเขียนเป็นรหัสเทียมออกมาได้ดังนี้
function MakeSet(x)
x.parent := x
function Find(x)
if x.parent == x
return x
else
return Find(x.parent)
function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)
xRoot.parent := yRoot
อย่างไรก็ตาม ประสิทธิภาพของป่าไม้เซตไม่มีส่วนร่วมข้างต้นแย่กว่าการใช้รายการโยงเซตไม่มีส่วนร่วมแบบอย่างง่ายเสียอีก เพราะต้นไม้ที่เกิดขึ้นอาจจะไม่สมดุลเป็นอย่างมาก ในกรณีเลวร้ายมากที่สุดอาจถึงขั้นกลายเป็นเส้นตรงเลย ซึ่งจะทำให้การดำเนินการทั้งค้นหาและยูเนียน แต่ละครั้งใช้เวลา O(n) อย่างไรก็ตามขั้นตอนวิธีนี้สามารถเพิ่มประสิทธิภาพได้ 3 วิธี
วิธีแรก เรียกว่า union by height ใช้แนวคิดว่าให้นำต้นไม้ที่มีความสูงต่ำกว่าไปต่อต้นไม้ที่มีความสูงมากกว่าเสมอเหมือนแนวคิดของ weighted-union heuristic ด้วยวิธีนี้จะทำให้ต้นไม้มีความสูงเพิ่มขึ้นก็ต่อเมื่อนำต้นไม้ที่มีความสูงเท่ากันพอดีมายูเนียนกัน และความสูงจะเพิ่มเพียงแค่ 1 ด้วย ดังนั้นเนื่องจากสามารถมีการยูเนียนได้เพียง log n ครั้ง ความสูงของต้นไม้จึงเป็น log n ด้วย ส่งผลให้การดำเนินการทั้งค้นหา และยูเนียน ในแต่ละครั้งใช้เวลา O(log n) สามารถเขียนเป็นรหัสเทียมได้ดังนี้
function MakeSet(x)
x.parent := x
function Find(x)
if x.parent == x
return x
else
return Find(x.parent)
function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)
xRoot.parent := yRoot
วิธีที่สองเรียกว่า การอัดวิถี โดยเป็นการที่พยายามทำให้โครงสร้างต้นไม้แบนราบเมื่อมีการดำเนินการค้นหา แนวคิดมาจากการที่การดำเนินการค้นหาแต่ละครั้งต้องวิ่งไล่ในวิถีผ่านจุดยอดต่าง ๆ จนถึงจุดยอดรากอยู่แล้ว ดังนั้นเมื่อทราบแล้วว่าจุดยอดรากคืออะไร ก็จะเปลี่ยนให้แต่ละจุดยอดบนวิถีดังกล่าวมีพ่อเป็นจุดยอดรากโดยตรงเลย ซึ่งเป็นการเพิ่มความเร็วในการดำเนินการค้นหาในครั้งถัด ๆ มา อย่างเห็นได้ชัด การเปลี่ยนความสัมพันธ์เช่นนี้ไม่ทำให้เกิดปัญหาใด ๆ ทั้งสิ้นเนื่องจากในการเปลี่ยนแปลงนี้ไม่ได้ทำให้จุดยอดรากเปลี่ยนไป ทำให้ตัวแทนเซตยังเหมือนเดิม และจุดยอดในต้นไม้ดังกล่าวก็ยังคงอยู่ในต้นไม้ต้นเดิมหลังเปลี่ยนแปลงโครงสร้างแล้ว ดังนั้นการเปลี่ยนแปลงโครงสร้างจึงทำให้เซตที่แทนออกมามีลักษณะเหมือนก่อนการเปลี่ยนแปลงทุกประการ ตัวอย่างรหัสเทียมของฟังก์ชัน find ที่ใช้ในการดำเนินการค้นหาคือ
function Find(x)
if x.parent != x
x.parent := Find(x.parent)
return x.parent
== การนำไปใช้งาน ==
== ประวัติ ==
== อ้างอิง ==
== แหล่งข้อมูลอื่น ==
C++ implementation , part of the Boost C++ libraries
A Java implementation with an application to color image segmentation, Statistical Region Merging (SRM), IEEE Trans. Pattern Anal. Mach. Intell. 26(11): 1452–1458 (2004)
Java applet: A Graphical Union-Find Implementation, by Rory L. P. McGuire
Wait-free Parallel Algorithms for the Union-Find Problem , a 1994 paper by Richard J. Anderson and Heather Woll describing a parallelized version of Union-Find that never needs to block
Python implementation
ขั้นตอนวิธีการค้นหา
โครงสร้างข้อมูล