ขั้นตอนวิธีของโกสรชุ
บทความนี้อาจต้องการตรวจสอบต้นฉบับ ในด้านไวยากรณ์ รูปแบบการเขียน การเรียบเรียง คุณภาพ หรือการสะกด คุณสามารถช่วยพัฒนาบทความได้ |
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ขั้นตอนวิธีของโกสรชุ (อังกฤษ: Kosaraju's_algorithm) หรือ ขั้นตอนวิธีของโกสรชุ-ชารีร์ (อังกฤษ: Kosaraju-Sharir algorithm) เป็นขั้นตอนวิธีสำหรับใช้หา ส่วนประกอบที่เชื่อมกันแบบเข้ม ของกราฟระบุทิศทาง (directed graph) ขั้นตอนวิธีนี้ใช้ประโยชน์จากหลักความจริงที่ว่า ทรานสโพสของกราฟ (กราฟเดียวกันที่เส้นเชื่อมทุกเส้นกลับทิศทางจากของเดิม) จะมีส่วนประกอบที่เชื่อมกันแบบเข้ม อันเดียวกับกราฟนั้นๆ
ประวัติ แก้
ในปี พ.ศ. 2521 โกสรชุ (Sambasiva Rao Kosaraju) ศาสตราจารย์สาขาวิทยาการคอมพิวเตอร์แห่งมหาวิทยาลัยจอนส์ฮอปกินส์ ชาวอินเดีย ได้เขียนเอกสารวิจัย เรื่องขั้นตอนวิธีการคำนวณหาส่วนประกอบที่เชื่อมกันแบบเข้มของกราฟระบุทิศทางอย่างมีประสิทธิภาพ ขั้นตอนวิธีนี้ภายหลังได้ถูกเรียกว่า ขั้นตอนวิธีของโกสรชุ-ชารีร์ แต่เอกสารวิจัยดังกล่าวไม่ได้ถูกตีพิมพ์ ต่อมาขั้นตอนวิธีนี้ถูกเผยแพร่โดยอัลเฟร็ด อาโฮ (Alfred Aho) จอห์น ฮอปครอฟ (John Hopcroft) และเจฟเฟรย์ อัลแมน (Jeffrey Ullman)
ขั้นตอนวิธี แก้
อัลกอรึทึมของโกสรชุ-ชารีร์ นั้นมีหลักการดังนี้
- ให้ G เป็นกราฟระบุทิศทาง (directed graph) และ S แทนกองซ้อน (stack) ที่ว่างเปล่า
- While S ยังไม่ได้เก็บจุดยอดทุกจุด
- เลือกจุดยอด v ที่ไม่อยู่ใน S แล้วทำ Depth-first search โดยเริ่มต้นที่ v จากนั้นทุกครั้งที่ Depth-first search เข้าไปถึงปม u จนเสร็จ ก็ให้ push u เข้าไปใน S
- กลับทิศของทุกเส้นเชื่อมเพื่อจะได้ transpose ของกราฟ
- While S ไม่ว่าง
- Pop จุดยอด v ออกมาจากกองซ้อน S แล้วทำ Depth-first search โดยเริ่มต้นที่ v จะพบว่าเซตของจุดยอดที่เข้าถึงได้จาก v จะเป็นส่วนประกอบที่เชื่อมกันแบบเข้มที่มี v อยู่ภายใน ดังนั้นก็จำจุดยอดเหล่านี้ไว้ และลบจุดยอดเหล่านี้ออกจากกราฟ G และกองซ้อน S
- หากใช้ Breadth-first search (BFS) แทน Depth-first search ก็ได้ผลอย่างเดียวกัน
ประสิทธิภาพการทำงาน แก้
หากกราฟถูกเก็บข้อมูลในรูปแบบ adjacency list เมื่อใช้อัลกอรึทึมของโกสรชุ-ชารีร์ จะเกิดการเดินทางเข้าไปในกราฟ 2 ครั้ง และการ reverse กราฟอีก 1 ครั้ง แต่เนื่องจากเราใช้ adjacency list เก็บข้อมูล เราจะสามารถสร้างกราฟ reverse ได้ขณะที่เดินทางเข้าไปในกราฟครั้งแรก ทำให้แท้จริงแล้วการเวลาการทำงานจะคำนวณจากการเดินทางเข้าไปในกราฟ 2 ครั้งเท่านั้น จึงพบว่าประสิทธิภาพของขั้นตอนวิธีนี้เท่ากับ Θ(V+E) (เส้นตรง) เมื่อ V แทนจำนวนจุดยอด และ E แทนจำนวนเส้นเชื่อม ซึ่งถือว่าประสิทธิภาพเป็น asymptotically optimal เพราะเวลาการทำงานนั้นตรงกับขอบเขตล่าง (lower bound) เพราะทุกๆ ขั้นตอนวิธีจะต้องตรวจสอบทุกจุดยอดกับเส้นเชื่อม ดังนั้นตามหลักการแล้วขั้นตอนวิธีนี้เป็นขั้นตอนวิธีที่ง่ายและมีประสิทธิภาพ แต่ในทางปฏิบัติจะมีประสิทธิภาพต่ำกว่าขั้นตอนวิธีของ Tarjan หรือขั้นตอนวิธีของ Gabow ที่สามารถหาส่วนประกอบที่เชื่อมกันแบบเข้มได้โดยเดินทางเข้าไปในกราฟเพียงแค่รอบเดียว
ถ้ากราฟถูกเก็บข้อมูลในรูปแบบ adjacency matrix ขั้นตอนวิธีจะใช้เวลาทำงาน O(V2)
การพิสูจน์ขั้นตอนวิธีของโกสรชุ แก้
พิสูจน์ว่าขั้นตอนวิธีของโกสรชุนั้นใช้ได้จริง โดยพิสูจน์ว่าจุดยอด s และ t อยู่ในต้นไม้ค้นหาเชิงลึก (Depth-first search tree) ต้นเดียวกันในกราฟ G ก็ต่อเมื่อ s และ t นั้นอยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน
- กรณีที่ 1 s และ t อยู่ในต้นไม้ค้นหาเชิงลึกคนละต้น
แสดงว่าเส้นเชื่อมใดๆ ระหว่างปมในต้นไม้ที่มี s กับปมในต้นไม้ที่มี t จะเป็นเส้นเชื่อมที่เชื่อมระหว่างต้นไม้ 2 ต้น เนื่องจากเส้นเชื่อมระหว่างต้นไม้สองต้นจะเดินทางไปได้ในทิศทางเดียวเท่านั้น จึงสรุปได้ว่า s และ t ไม่อยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน
- กรณีที่ 2 s และ t อยู่ในต้นไม้ค้นหาเชิงลึกต้นเดียวกัน
กำหนดให้ r แทนรากของต้นไม้, G’ แทนทรานสโพสต์ของกราฟ G
- มีทางเดิน (path) จาก s ไป r ในกราฟ G’ (เนื่องจากมีทางเดินจาก r ไป s ใน G)
- r มีเลข postorder สูงกว่า s เมื่อทำการค้นหาเชิงลึกใน G’ (มิเช่นนั้น s จะต้องเป็นรากของต้นไม้)
- r ต้องเป็นปมบรรพบุรุษของ s ในกราฟ G’ (เนื่องจาก 1 และ 2)
- จะต้องมีทางเดินจาก r ไป s ใน G’ (เนื่องจาก 3)
- มีทางเดินจาก r ไป s และจาก s ไป r ในกราฟ G (เนื่องจาก 1 และ 4)
- s และ r นั้นอยู่ใน ส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน (เนื่องจาก 5)
- ใช้เหตุผลเดียวกันในการพิสูจน์จุดยอด r และ t
- จะได้ว่าถ้า s กับ r อยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน และ r กับ t อยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน แล้ว s กับ r ก็จะอยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกันด้วย
อ้างอิง แก้
- Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd edition. The MIT Press, 2009. ISBN 0-262-03384-8.