Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
บทความนี้อาจต้องการตรวจสอบต้นฉบับ ในด้านไวยากรณ์ รูปแบบการเขียน การเรียบเรียง คุณภาพ หรือการสะกด คุณสามารถช่วยพัฒนาบทความได้ |
ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีการหาปมบรรพบุรุษร่วมใกล้สุดของคู่ปมของทาร์จาน (อังกฤษ: Tarjan's off-line least common ancestors algorithm; อันที่จริงแล้ว least ควรจะเป็น lowest) คือขั้นตอนวิธีในการคำนวณหา (lowest common ancestors) สำหรับทุก ๆ คู่ของปมในต้นไม้ () โดยมีพื้นฐานในการคำนวณหาจากโครงสร้างข้อมูลที่เรียกว่าโครงสร้างข้อมูลเซตไม่มีส่วนร่วม ขั้นตอนวิธีนี้ได้ถูกตั้งชื่อตาม ผู้ซึ่งค้นพบกลวิธีนี้ในปี 1979
ปมบรรพบุรุษร่วมใกล้สุดของระหว่างคู่ปม d และ e ในต้นไม้ T คือ ปม g ซึ่งเป็นปมบรรพบุรุษของทั้งปม d และปม e ที่ไกลจากปมรากมากที่สุด
ขั้นตอนวิธีของทาร์จาน ไม่เหมือนกับขั้นตอนวิธีการหาปมบรรพบุรุษร่วมใกล้สุดของคู่ปมอื่น ๆ เนื่องจากเป็นขั้นตอนวิธีออฟไลน์ ซึ่งคือขั้นตอนวิธีที่จะต้องป้อนข้อมูลนำเข้าทั้งหมดก่อนเริ่มการแก้ปัญหาตามขั้นตอนวิธี นอกจากนี้ขั้นตอนวิธีของทาร์จาน ยังเป็นขั้นตอนวิธีที่ใช้โครงสร้างข้อมูลที่เรียกว่า การยูเนียนและการค้นหา ทำให้ระยะเวลาที่ใช้สำหรับขั้นตอนวิธีนี้ไม่เป็นค่าคงตัว ในกรณีที่มีจำนวนคู่ของปมเท่ากับจำนวนของปมทั้งหมด ทำให้แตกต่างจากขั้นตอนวิธีอื่น ๆ ที่ไม่ได้ใช้โครงสร้างข้อมูลการยูเนียนและการค้นหา ต่อมาในปี 1983 และ ได้ทำการปรับปรุงประสิทธิภาพของขั้นตอนวิธีให้ใช้ระยะเวลาเร็วขึ้นเป็นแบบ O(n)
รหัสเทียม
รหัสเทียม ด้านล่างอธิบายถึง ปมบรรพบุรุษร่วมใกล้สุดของแต่ละคู่ปมในต้นไม้ P โดยมี r เป็นปมราก ซึ่งลูกของปม n จะอยู่ในเซต n.children ทั้งนี้เนื่องจากขั้นตอนวิธีการนี้เป็นแบบออฟไลน์ ดังนั้น เซตของ P จะต้องถูกกำหนดเป็นพิเศษล่วงหน้า ขั้นตอนวิธีนี้ใช้กับ () 3 แบบ คือ
- MakeSet(u) : สร้างเซตใหม่ที่มี u เป็นสมาชิกเพียงตัวเดียว
- Find(u) : หาหมายเลขเซตที่ u เป็นสมาชิกอยู่
- Union(u,v) : ยูเนียนเซต u กับ เซต v
- โดยมี TarjanOLCA(r) เป็นการเรียกฟังก์ชันโดยเริ่มที่ปมราก r
function TarjanOLCA(u) MakeSet(u); u.ancestor := u; for each v in u.children do TarjanOLCA(v); Union(u,v); Find(u).ancestor := u; u.colour := black; for each v such that {u,v} in P do if v.colour == black print "Tarjan's Least Common Ancestor of " + u + " and " + v + " is " + Find(v).ancestor + "."; ขณะเริ่มต้นแต่ละปมจะถูกกำหนดให้มีสีขาว และจะถูกกำหนดเป็นสีดำก็ต่อเมื่อปมนั้นและลูกทั้งหมดของปมนั้นถูกผ่านแล้ว ปมบรรพบุรุษร่วมใกล้สุดของคู่ปม {u,v} จะสามารถหาได้จาก Find(v).ancestor ในทันทีได้ก็ต่อเมื่อ หลังจากที่ปม u ถูกเปลี่ยนเป็นสีดำเรียบร้อยแล้ว โดยมีเงื่อนไขว่า ปม v จะต้องเป็นสีดำแล้ว ไม่เช่นนั้นจะสามารถหาได้จาก Find(u).ancestor ในทันทีหลังจากที่ ปม v ถูกเปลี่ยนเป็นสีดำ
รหัสเทียมด้านล่างต่อไปนี้ เป็นรหัสเทียมอ้างอิงถึงการดำเนินการทั้ง 3 แบบที่ได้รับการปรับปรุงให้เหมาะสมสำหรับป่าไม้ของกลุ่มเซตไม่มีตัวร่วม อันได้แก่ MakeSet, Find และ Union
function MakeSet(x) x.parent := x x.rank := 0
function Union(x, y) xRoot := Find(x) yRoot := Find(y) if xRoot.rank > yRoot.rank yRoot.parent := xRoot else if xRoot.rank < yRoot.rank xRoot.parent := yRoot else if xRoot != yRoot yRoot.parent := xRoot xRoot.rank := xRoot.rank + 1
function Find(x) if x.parent == x return x else x.parent := Find(x.parent) return x.parent
อ้างอิง
- Gabow, H. N.; (1983), "A linear-time algorithm for a special case of disjoint set union", Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 246–251, doi:10.1145/800061.808753
- (1979), "Applications of path compression on balanced trees", 26 (4): 690–715, doi:10.1145/322154.32216
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 khunsamarthchwyphthnabthkhwamid inwithyakarkhxmphiwetxr khntxnwithikarhapmbrrphburusrwmiklsudkhxngkhupmkhxngtharcan xngkvs Tarjan s off line least common ancestors algorithm xnthicringaelw least khwrcaepn lowest khuxkhntxnwithiinkarkhanwnha lowest common ancestors sahrbthuk khukhxngpmintnim odymiphunthaninkarkhanwnhacakokhrngsrangkhxmulthieriykwaokhrngsrangkhxmulestimmiswnrwm khntxnwithiniidthuktngchuxtam phusungkhnphbklwithiniinpi 1979 pmbrrphburusrwmiklsudkhxngrahwangkhupm d aela e intnim T khux pm g sungepnpmbrrphburuskhxngthngpm d aelapm e thiiklcakpmrakmakthisud khntxnwithikhxngtharcan imehmuxnkbkhntxnwithikarhapmbrrphburusrwmiklsudkhxngkhupmxun enuxngcakepnkhntxnwithixxfiln sungkhuxkhntxnwithithicatxngpxnkhxmulnaekhathnghmdkxnerimkaraekpyhatamkhntxnwithi nxkcaknikhntxnwithikhxngtharcan yngepnkhntxnwithithiichokhrngsrangkhxmulthieriykwa karyueniynaelakarkhnha thaihrayaewlathiichsahrbkhntxnwithiniimepnkhakhngtw inkrnithimicanwnkhukhxngpmethakbcanwnkhxngpmthnghmd thaihaetktangcakkhntxnwithixun thiimidichokhrngsrangkhxmulkaryueniynaelakarkhnha txmainpi 1983 aela idthakarprbprungprasiththiphaphkhxngkhntxnwithiihichrayaewlaerwkhunepnaebb O n rhsethiymrhsethiym danlangxthibaythung pmbrrphburusrwmiklsudkhxngaetlakhupmintnim P odymi r epnpmrak sunglukkhxngpm n caxyuinest n children thngnienuxngcakkhntxnwithikarniepnaebbxxfiln dngnn estkhxng P catxngthukkahndepnphiesslwnghna khntxnwithiniichkb 3 aebb khux MakeSet u srangestihmthimi u epnsmachikephiyngtwediyw Find u hahmayelkhestthi u epnsmachikxyu Union u v yueniynest u kb est v odymi TarjanOLCA r epnkareriykfngkchnodyerimthipmrak rfunction TarjanOLCA u MakeSet u u ancestor u for each v in u children do TarjanOLCA v Union u v Find u ancestor u u colour black for each v such that u v in P do if v colour black print Tarjan s Least Common Ancestor of u and v is Find v ancestor khnaerimtnaetlapmcathukkahndihmisikhaw aelacathukkahndepnsidaktxemuxpmnnaelalukthnghmdkhxngpmnnthukphanaelw pmbrrphburusrwmiklsudkhxngkhupm u v casamarthhaidcak Find v ancestor inthnthiidktxemux hlngcakthipm u thukepliynepnsidaeriybrxyaelw odymienguxnikhwa pm v catxngepnsidaaelw imechnnncasamarthhaidcak Find u ancestor inthnthihlngcakthi pm v thukepliynepnsida rhsethiymdanlangtxipni epnrhsethiymxangxingthungkardaeninkarthng 3 aebbthiidrbkarprbprungihehmaasmsahrbpaimkhxngklumestimmitwrwm xnidaek MakeSet Find aela Union function MakeSet x x parent x x rank 0 function Union x y xRoot Find x yRoot Find y if xRoot rank gt yRoot rank yRoot parent xRoot else if xRoot rank lt yRoot rank xRoot parent yRoot else if xRoot yRoot yRoot parent xRoot xRoot rank xRoot rank 1 function Find x if x parent x return x else x parent Find x parent return x parentxangxingGabow H N 1983 A linear time algorithm for a special case of disjoint set union Proceedings of the 15th ACM Symposium on Theory of Computing STOC pp 246 251 doi 10 1145 800061 808753 1979 Applications of path compression on balanced trees 26 4 690 715 doi 10 1145 322154 32216