Sidebar
dsa:dsapp
8.7 ตัวอย่างการประยุกต์
ตัวอย่างของการใช้โครงสร้างข้อมูล union/find ที่เสนอนี้เป็นการใช้เพื่อการสร้าง mazes ดังแสดงในรูปที่ 8.19 จุดเริ่มต้นของรูปอยู่ที่ด้านบนและจุดสิ้นสุดอยู่ที่ตำแหน่งด้านล่างรูป เราสามารถมอง maze ได้ว่าเป็นรูปสี่เหลี่ยมที่ประกอบด้วยเซลล์สี่เหลี่ยมขนาดเล็กจำนวนหนึ่งขนาด m-by-n เซลล์ ซึ่งเป็นเซลล์ที่เชื่อมต่อทางเข้ากับทางออด และแต่ละเซลล์แยกจากเซลล์ที่อยู่ติดกันด้วยผนัง
รูปที่ 8.19 Maze
อัลกอริทึมอย่างง่ายที่ใช้ในการสร้าง maze คือให้เริ่มด้วยการสร้าง maze ที่มีผนังทุก ๆ ผนังยกเว้นจุดเริ่มและจุดสิ้นสุด จากนั้นทำการเลือกผนังโดยเลือกแบบสุ่มและทำลายผนังถ้าเซลล์ที่ผนังกั้นอยู่นั้นยังเข้าหากันไม่ได้ ถ้าเราทำอย่างที่กล่าวนี้ไปเรื่อย ๆ จนกว่าเซลล์เริ่มต้นเชื่อมต่อกันได้กับเซลล์สุดท้ายเราก็จะได้ maze
รูปที่ 8.20 เป็นสถานะเริ่มต้นของ maze ขนาด 5×5 เราจะใช้โครงสร้างข้อมูล union/find เพื่อแสดงกลุ่มของเซลล์ที่เชื่อมต่อกัน เริ่มต้นด้วยทุกเซลล์มีผนังกั้นระหว่างกันหมายความว่าแต่ละเซลล์สังกัดใน equivalent class ของตัวมันเอง ให้ทางเข้า - ออก คือช่อง 1 และ 24
{0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} {17} {18} {19} {20} {21} {22} {23} {24}
รูปที่ 8.20 สภาพเริ่มต้นที่มีผนังทุกเซลล์ และแต่ละเซลล์อยู่ในเซตของตัวเอง
รูปที่ 8.21 แสดงสภาวะหลังการทำงานของอัลกอริทึมเมื่อมีการทำลายผนังบางส่วนลง สมมติที่สภาวะนี้ เราเลือก (แบบสุ่ม) ผนังระหว่างเซลล์ 8 และ 13 เนื่องจากว่าเซลล์ 8 และ 13 เชื่อมต่อกันอยู่แล้ว (คือมันอยู่ในเซตเดียวกันอยู่แล้ว) เราจึงไม่ต้องทำลายผนังระหว่างมัน จากนี้เลือก (แบบสุ่ม) เซลล์ 18 และ 13 ด้วยการทำงาน find 2 ครั้ง จะพบว่าเซลล์ทั้งสองนี้ไม่ได้อยู่ในเซตเดียวกัน นั่นคือเซลล์ 13 และ 18 ยังไม่เชื่อมถึงกัน ดังนั้นเราจะทำลายผนังระหว่างมันดังแสดงในรูปที่ 8.22 โดยเซตที่มี 13 และเซตที่มี 18 เป็นสมาชิกได้รับการนำมารวมกันด้วยการทำงาน union และทำให้ทุกอย่างที่เชื่อมต่อกับเซลล์ 18 ก็จะเชื่อมต่อกับทุกอย่างที่เชื่อมต่ออยู่กับเซลล์ 13 หลังเสร็จสิ้นการทำงานของอัลกอริทึมทุก ๆ เซลล์ก็จะเชื่อมถึงกันดังรูปที่ 8.23
{0, 1} {2} {3} {4, 6, 7, 8, 9, 13, 14} {5} {10, 11, 15} {12} {16, 17, 18, 22} {19} {20} {21} {23} {24}
รูปที่ 8.21 สภาพ maze ระหว่างการทำงานของอัลกอริทึมที่มีผนังของบางเซลล์ถูกทำลาย มีการควบรวมบางเซต
{0, 1} {2} {3} {5} {10, 11, 15} {12} {4, 6, 7, 8, 9, 13, 14, 16, 17, 18, 22} {19} {20} {21} {23} {24}
รูปที่ 8.22 สภาพ maze เมื่อเลือกเซลล์ 13 และ 18 จากรูปที่ 8.21 ผนังระหว่างเซลล์ถูกทำลาย
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24}
รูปที่ 8.23 จำนวนผนังที่ถูกทำลายคือ 24 ด้านแต่เซลล์ทั้งหมดก็เชื่อถึงกันได้
ค่าใช้จ่ายในการทำงานของ union/find จะเป็นตัวกำหนด running time ของอัลกอริทึม จำนวนการทำงานของ find จะแปรผันตามจำนวนเซลล์เนื่องจากผนังที่จะถูกทำลายนั้นมีจำนวนเท่ากับจำนวนเซลล์ลบหนึ่ง อย่างไรก็ตาม หากพิจารณาให้ดีจะเห็นว่าในขณะเริ่มต้นนั้นมีจำนวนผนังเป็น 2 เท่าของจำนวนเซลล์ ดังนั้นถ้า N เป็นจำนวนเซลล์และเราต้องทำงาน find 2 ครั้งต่อผนังหนึ่ง เราจึงประมาณได้ว่าตลอดการทำงานของอัลกอริทึมจะต้องทำงาน find โดยประมาณระหว่าง $2N$ ถึง $4N$ ครั้ง ดังนั้น running time ของอัลกอริทึมจึงมีค่าเป็น $O(N\ log*\ N)$
dsa/dsapp.txt · Last modified: 2021/09/10 15:51 by wasu
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
