Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
บทความนี้อาจต้องการตรวจสอบต้นฉบับ ในด้านไวยากรณ์ รูปแบบการเขียน การเรียบเรียง คุณภาพ หรือการสะกด คุณสามารถช่วยพัฒนาบทความได้ |
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ขั้นตอนวิธีของโกสรชุ (อังกฤษ: 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) เพราะทุกๆ ขั้นตอนวิธีจะต้องตรวจสอบทุกจุดยอดกับเส้นเชื่อม ดังนั้นตามหลักการแล้วขั้นตอนวิธีนี้เป็นขั้นตอนวิธีที่ง่ายและมีประสิทธิภาพ แต่ในทางปฏิบัติจะมีประสิทธิภาพต่ำกว่า หรือ ที่สามารถหาส่วนประกอบที่เชื่อมกันแบบเข้มได้โดยเดินทางเข้าไปในกราฟเพียงแค่รอบเดียว
ถ้ากราฟถูกเก็บข้อมูลในรูปแบบ 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. .
แหล่งข้อมูลอื่น
- A description and proof of Kosaraju's Algorithm
- Good Math, Bad Math: Computing Strongly Connected Components 2012-02-05 ที่ เวย์แบ็กแมชชีน
- Java implementation at AlgoWiki.net 2010-11-16 ที่ เวย์แบ็กแมชชีน
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
bthkhwamnixactxngkartrwcsxbtnchbb indaniwyakrn rupaebbkarekhiyn kareriyberiyng khunphaph hruxkarsakd khunsamarthchwyphthnabthkhwamidlingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisud khntxnwithikhxngoksrchu xngkvs Kosaraju s algorithm hrux khntxnwithikhxngoksrchu charir xngkvs Kosaraju Sharir algorithm epnkhntxnwithisahrbichha swnprakxbthiechuxmknaebbekhm khxngkrafrabuthisthang directed graph khntxnwithiniichpraoychncakhlkkhwamcringthiwa thransophskhxngkraf krafediywknthiesnechuxmthukesnklbthisthangcakkhxngedim camiswnprakxbthiechuxmknaebbekhm xnediywkbkrafnnprawtiinpi ph s 2521 oksrchu Sambasiva Rao Kosaraju sastracarysakhawithyakarkhxmphiwetxraehngmhawithyalycxnshxpkins chawxinediy idekhiynexksarwicy eruxngkhntxnwithikarkhanwnhaswnprakxbthiechuxmknaebbekhmkhxngkrafrabuthisthangxyangmiprasiththiphaph khntxnwithiniphayhlngidthukeriykwa khntxnwithikhxngoksrchu charir aetexksarwicydngklawimidthuktiphimph txmakhntxnwithinithukephyaephrodyxlefrd xaoh Alfred Aho cxhn hxpkhrxf John Hopcroft aelaecfefry xlaemn Jeffrey Ullman khntxnwithixlkxruthumkhxngoksrchu charir nnmihlkkardngni ih G epnkrafrabuthisthang directed graph aela S aethnkxngsxn stack thiwangepla While S yngimidekbcudyxdthukcud eluxkcudyxd v thiimxyuin S aelwtha Depth first search odyerimtnthi v caknnthukkhrngthi Depth first search ekhaipthungpm u cnesrc kih push u ekhaipin S klbthiskhxngthukesnechuxmephuxcaid transpose khxngkraf While S imwang Pop cudyxd v xxkmacakkxngsxn S aelwtha Depth first search odyerimtnthi v caphbwaestkhxngcudyxdthiekhathungidcak v caepnswnprakxbthiechuxmknaebbekhmthimi v xyuphayin dngnnkcacudyxdehlaniiw aelalbcudyxdehlanixxkcakkraf G aelakxngsxn Shakich Breadth first search BFS aethn Depth first search kidphlxyangediywknprasiththiphaphkarthanganhakkrafthukekbkhxmulinrupaebb adjacency list emuxichxlkxruthumkhxngoksrchu charir caekidkaredinthangekhaipinkraf 2 khrng aelakar reverse krafxik 1 khrng aetenuxngcakeraich adjacency list ekbkhxmul eracasamarthsrangkraf reverse idkhnathiedinthangekhaipinkrafkhrngaerk thaihaethcringaelwkarewlakarthangancakhanwncakkaredinthangekhaipinkraf 2 khrngethann cungphbwaprasiththiphaphkhxngkhntxnwithiniethakb 8 V E esntrng emux V aethncanwncudyxd aela E aethncanwnesnechuxm sungthuxwaprasiththiphaphepn asymptotically optimal ephraaewlakarthangannntrngkbkhxbekhtlang lower bound ephraathuk khntxnwithicatxngtrwcsxbthukcudyxdkbesnechuxm dngnntamhlkkaraelwkhntxnwithiniepnkhntxnwithithingayaelamiprasiththiphaph aetinthangptibticamiprasiththiphaphtakwa hrux thisamarthhaswnprakxbthiechuxmknaebbekhmidodyedinthangekhaipinkrafephiyngaekhrxbediyw thakrafthukekbkhxmulinrupaebb adjacency matrix khntxnwithicaichewlathangan O V2 karphisucnkhntxnwithikhxngoksrchuphisucnwakhntxnwithikhxngoksrchunnichidcring odyphisucnwacudyxd s aela t xyuintnimkhnhaechingluk Depth first search tree tnediywkninkraf G ktxemux s aela t nnxyuinswnprakxbthiechuxmknaebbekhmediywkn krnithi 1 s aela t xyuintnimkhnhaechinglukkhnlatn aesdngwaesnechuxmid rahwangpmintnimthimi s kbpmintnimthimi t caepnesnechuxmthiechuxmrahwangtnim 2 tn enuxngcakesnechuxmrahwangtnimsxngtncaedinthangipidinthisthangediywethann cungsrupidwa s aela t imxyuinswnprakxbthiechuxmknaebbekhmediywkn krnithi 2 s aela t xyuintnimkhnhaechingluktnediywkn kahndih r aethnrakkhxngtnim G aethnthransophstkhxngkraf G mithangedin path cak s ip r inkraf G enuxngcakmithangedincak r ip s in G r mielkh postorder sungkwa s emuxthakarkhnhaechinglukin G miechnnn s catxngepnrakkhxngtnim r txngepnpmbrrphburuskhxng s inkraf G enuxngcak 1 aela 2 catxngmithangedincak r ip s in G enuxngcak 3 mithangedincak r ip s aelacak s ip r inkraf G enuxngcak 1 aela 4 s aela r nnxyuin swnprakxbthiechuxmknaebbekhmediywkn enuxngcak 5 ichehtuphlediywkninkarphisucncudyxd r aela t caidwatha s kb r xyuinswnprakxbthiechuxmknaebbekhmediywkn aela r kb t xyuinswnprakxbthiechuxmknaebbekhmediywkn aelw s kb r kcaxyuinswnprakxbthiechuxmknaebbekhmediywkndwyxangxingAlfred 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 aehlngkhxmulxunA description and proof of Kosaraju s Algorithm Good Math Bad Math Computing Strongly Connected Components 2012 02 05 thi ewyaebkaemchchin Java implementation at AlgoWiki net 2010 11 16 thi ewyaebkaemchchin