ขั้นตอนวิธีของโกสรชุ

จากวิกิพีเดีย สารานุกรมเสรี

ขั้นตอนวิธีของโกสรชุ (อังกฤษ: 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

  1. มีทางเดิน (path) จาก s ไป r ในกราฟ G’ (เนื่องจากมีทางเดินจาก r ไป s ใน G)
  2. r มีเลข postorder สูงกว่า s เมื่อทำการค้นหาเชิงลึกใน G’ (มิเช่นนั้น s จะต้องเป็นรากของต้นไม้)
  3. r ต้องเป็นปมบรรพบุรุษของ s ในกราฟ G’ (เนื่องจาก 1 และ 2)
  4. จะต้องมีทางเดินจาก r ไป s ใน G’ (เนื่องจาก 3)
  5. มีทางเดินจาก r ไป s และจาก s ไป r ในกราฟ G (เนื่องจาก 1 และ 4)
  6. s และ r นั้นอยู่ใน ส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน (เนื่องจาก 5)
  7. ใช้เหตุผลเดียวกันในการพิสูจน์จุดยอด r และ t
  8. จะได้ว่าถ้า s กับ r อยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน และ r กับ t อยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน แล้ว s กับ r ก็จะอยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกันด้วย

อ้างอิง[แก้]

แหล่งข้อมูลอื่น[แก้]