Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
บทความนี้ต้องการการจัดหน้า หรือ ให้ คุณสามารถปรับปรุงแก้ไขบทความนี้ได้ และนำป้ายออก พิจารณาใช้เพื่อชี้ชัดข้อบกพร่อง |
ปัญหาวิถียาวสุด (อังกฤษ: Longest path problem) เป็นหนึ่งในปัญหาทางคณิตศาสตร์ในเรื่องทฤษฎีกราฟ ซึ่งมีไว้สำหรับค้นหาวิถีเชิงเดียว (Simple path) ที่มีระยะทางมากที่สุดนับจากปมเริ่มต้นไปยังปมปลายทางบนกราฟถ่วงน้ำหนัก (Weighted graph) ลักษณะของปัญหาวิถียาวสุดจะคล้ายคลึงกันกับปัญหาวิถีสั้นสุด (Shortest path problem) ซึ่งเป็นการหาวิถีเชิงเดียวบนกราฟที่มีระยะทางสั้นที่สุดแทน เราสามารถหาวิถีสั้นสุดบนกราฟใดๆได้ในเวลาที่เป็นฟังก์ชันพหุนาม (Polynomial time) นั่นหมายถึงปัญหาวิถีสั้นสุดที่ลักษณะของปัญหาเป็นแบบปัญหาการตัดสินใจนั้นจัดอยู่ในกลุ่มความซับซ้อนแบบพี แต่ในทางกลับกัน ปัญหาวิถียาวสุดนั้นกลับยังไม่มีขั้นตอนวิธีใดที่ทำงานได้อย่างถูกต้องในเวลาที่เป็นฟังก์ชันพหุนาม กล่าวคือเป็นปัญหาที่อยู่ในกลุ่มเอ็นพี และได้รับการพิสูจน์แล้วว่าปัญหาวิถียาวสุดนั้นเกิดจากการลดรูปมาจาก (Hamiltonian path problem) ซึ่งอยู่ในกลุ่มเอ็นพีบริบูรณ์ ทำให้ปัญหานี้อยู่ในกลุ่มเอ็นพีบริบูรณ์เช่นเดียวกัน
รายละเอียด
วิถีเชิงเดียวจากปม A ไปยังปม B ของกราฟใดๆหมายถึง เซตของวิถีทุกรูปแบบที่เริ่มต้นจากจุด A และไปสิ้นสุดยังจุด B โดยไม่มีการผ่านปมซ้ำ ในกรณีที่กราฟนั้นเป็นกราฟถ่วงน้ำหนัก กล่าวคือมีตัวเลขกำกับประจำทุกๆเส้นเชื่อมก็จะได้ว่า วิถีเชิงเดียวยาวสุดจากปม A ไปยังปม B ก็คือเซตของวิถีทุกรูปแบบที่มีน้ำหนักรวมของเส้นเชื่อมทุกเส้นบนวิถีมากที่สุด ดังนั้น ปัญหาวิถียาวสุดจึงเป็นปัญหาประเภท Optimization Problem คือแก้ปัญหาโดยการหาผลลัพธ์ที่ดีที่สุดที่เป็นไปได้นั่นเอง อย่างไรก็ตามปัญหาวิถียาวสุดสามารถปรับให้เปนปัญหาการตัดสินใจได้โดยการกำหนดตัวเลข k ขึ้นมาตัวหนึ่งแล้วถามปัญหาว่า ในกราฟนี้มีวิถียาวสุดที่ยาวไม่น้อยกว่า k หรือไม่ จากการพิสูจน์ว่าปัญหาวิถียาวสุดเป็นปัญหาในกลุ่มเอ็นพีบริบูรณ์ดังนั้นจึงหมายความว่าปัญหานี้สามารถหาคำตอบโดยใช้ (Non-deterministic function) หรือสามารถตรวจคำตอบใช่ได้ในเวลาที่เป็นฟังก์ชันพหุนามนั่นเอง โดยการตรวจคำตอบใช่นั้นทำได้โดยการส่งหลักฐาน (Certificate) C เข้าไปในฟังก์ชันโดย C เป็นวิถีหนึ่งในกราฟซึ่งมีวิถียาวสุดยาวกว่าหรือเท่ากับ k ก็จะทำให้ฟังก์ชันตรวจคำตอบทำงานได้ในเวลาที่เป็นฟังก์ชันพหุนาม
ขั้นตอนวิธี
- ข้อมูลนำเข้า กราฟ G, ปมเริ่มต้น a "เป็นสมาชิกของ" G.V, ปมปลายทาง b "เป็นสมาชิกของ" G.V
- ข้อมูลส่งออก ระยะทางของวิถีที่ยาวที่สุดจากปม a ไปยังปม b บนกราฟ G
- สำหรับกราฟที่สามาถนำมาใช้เป็นข้อมูลนำเข้า นั้นสามารถเป็นกราฟใดๆก็ได้ โดยหากเป็นกราฟถ่วงน้ำหนักทั่วไป (General Weighted Graph) ในปัจจุบันยังไม่มีใครค้นพบขั้นตอนวิธีที่ใช้เวลาที่เป็นฟังก์ชันพหุนามได้ แต่ว่าสำหรับการแก้ปัญหาวิถียาวสุดที่ง่ายนั้น กราฟที่รับมาจะเป็นกราฟอวัฏจักรระบุทิศทาง ดังที่จะแสดงต่อไปนี้
สำหรับกราฟอวัฏจักรระบุทิศทาง
กราฟอวัฏจักรระบุทิศทาง (Directed acyclic graph หรืออักษรย่อว่า DAG) เป็นกราฟระบุทิศทาง ที่ไม่มีวัฏจักรแบบระบุทิศทางใดๆในกราฟ ขั้นตอนวิธีสำหรับแก้ปัญหาวิถียาวสุดบนกราฟอวัฏจักรระบุทิศทาง อาจใช้การปรับเปลี่ยนมาจากปัญหาวิถีสั้นสุด โดยสร้างกราฟใหม่ขึ้นมา (G’) โดยให้กราฟใหม่นี้มีปมและเส้นเชื่อมเหมือนกราฟเดิมทุกประการ แต่น้ำหนักของเส้นเชื่อมให้เปลี่ยนเป็นค่าติดลบของค่าเดิม แล้วนำกราฟใหม่นี้มาแก้ปัญหาแบบวิถีสั้นสุด ก็จะได้ว่าวิถีสั้นสุดของกราฟใหม่ ก็จะกลายเป็นวิถียาวสุดของกราฟเดิมนั่นเอง
int LogestPathDAG(Graph G, Vertex Start, Vertex End){ construct Graph G’ : G’.V = G.V : G’.E = G.E : G’.w = -G.w return shortestPathDAG(G’, Start, End); } ขั้นตอนวิธีดังกล่าวก็จะมีเวลาในการทำงานเท่ากับ
- เวลาในการสร้างกราฟใหม่ เป็น O(|G.E|)
- เวลาในการแก้ปัญหาวิถีสั้นสุด (ขึ้นกับขั้นตอนวิธีที่ใช้) เช่น ขั้นตอนวิธีของไดค์สตรา จะใช้เวลาในการทำงานเป็น O(|G.E| log(|G.V|))
จึงได้เวลาในการทำงานรวม (กรณีใช้ขั้นตอนวิธีของไดค์สตรา) เป็น O(|G.E| log(|G.V|))
- อย่างไรก็ตาม การแก้ปัญหาวิถียาวสุดบนกราฟอวัฎจักรระบุทิศทางนั้น มีอัลกอรีทึมที่สามารถทำงานได้เร็วกว่าขั้นตอนวิธีข้างต้น นั่นคือใช้กำหนดการพลวัต (Dynamic programming) ซึ่งมีขั้นตอนดังนี้
int LongestPathDAG(Graph G, Vertex Start, Vertex End){ topologicalSorting(G); int distance[|G.V|] arrage by sorted G; for each vertex u in topOrder of G.V for each edge e in G.E point from u to v if (distance(v) < distance(u) + weight(e)) distance(v) = distance(u) + weight(e); return max value element in distance } ประสิทธิภาพในการทำงานขอขั้นตอนวิธีนี้เกิดจาก
- เวลาในการเรียงลำดับแบบทอพอลอยี เป็น O(|G.V| + |G.E|)
- เวลาในการตรวจสอบและเปลี่ยนค่าในอาเรย์ distance เป็น O(|G.E|)
- เวลาในการหาค่ามากสุดในอาเรย์ distance เป็น O(|G.V|)
รวมเป็นเวลาในการทำงานทั้งหมด O(|G.V| + |G.E|)
สำหรับกราฟอื่นๆ
- ขั้นตอนวิธีสำหรับ Interval Graphs
- ขั้นตอนวิธีสำหรับ Ptolemaic Graphs
- ขั้นตอนวิธีสำหรับ Small Graph Classes
- ขั้นตอนวิธีสำหรับ Cocomparability Graphs
ขั้นตอนวิธีอื่นๆที่เกี่ยวข้อง
- (Topological sorting)
- ขั้นตอนวิธีของไดค์สตรา (Dijkstra algorithm)
ปัญหาที่เกี่ยวข้อง
- ปัญหาวิถีสั้นสุด (Shortest path problem)
- (Hamiltonian path problem)
- (Travelling salesman problem)
อ้างอิง
- , คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2007-06-11, สืบค้นเมื่อ 2011-09-29
- Dynamic programming (PDF)
- , คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-08-19, สืบค้นเมื่อ 2011-09-29
- Ioannidou, Kyriaki, Longest path problem on Interval Graphs (PDF)
- Takahara, Yoshihiro, Longest path problem on Ptolemaic Graphs
- Uehara, Ryuhei, Longest path problem on Small Graph Classes
- Longest path problem on Cocomparability Graphs
แหล่งข้อมูลอื่น
- NP-Completeness
- Source of the algorithm
- "Find the Longest Path", by Daniel J. Barrett
- Efficient Algorithms for the Longest Path Problem by Ryuhei UEHARA (JAIST), Yushi UNO (Osaka Prefecture University)[]
- On the relation between the travelling-salesman and the longest path problems by William W. Hardgrave and George L. Nemhauser
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
bthkhwamnitxngkarkarcdhna cdhmwdhmu islingkphayin hruxekbkwadenuxha ihmikhunphaphdikhun khunsamarthprbprungaekikhbthkhwamniid aelanapayxxk phicarnaichpaykhxkhwamxunephuxchichdkhxbkphrxng pyhawithiyawsud xngkvs Longest path problem epnhnunginpyhathangkhnitsastrineruxngthvsdikraf sungmiiwsahrbkhnhawithiechingediyw Simple path thimirayathangmakthisudnbcakpmerimtnipyngpmplaythangbnkrafthwngnahnk Weighted graph lksnakhxngpyhawithiyawsudcakhlaykhlungknkbpyhawithisnsud Shortest path problem sungepnkarhawithiechingediywbnkrafthimirayathangsnthisudaethn erasamarthhawithisnsudbnkrafididinewlathiepnfngkchnphhunam Polynomial time nnhmaythungpyhawithisnsudthilksnakhxngpyhaepnaebbpyhakartdsinicnncdxyuinklumkhwamsbsxnaebbphi aetinthangklbkn pyhawithiyawsudnnklbyngimmikhntxnwithiidthithanganidxyangthuktxnginewlathiepnfngkchnphhunam klawkhuxepnpyhathixyuinklumexnphi aelaidrbkarphisucnaelwwapyhawithiyawsudnnekidcakkarldrupmacak Hamiltonian path problem sungxyuinklumexnphibriburn thaihpyhanixyuinklumexnphibriburnechnediywknraylaexiydwithiechingediywcakpm A ipyngpm B khxngkrafidhmaythung estkhxngwithithukrupaebbthierimtncakcud A aelaipsinsudyngcud B odyimmikarphanpmsa inkrnithikrafnnepnkrafthwngnahnk klawkhuxmitwelkhkakbpracathukesnechuxmkcaidwa withiechingediywyawsudcakpm A ipyngpm B kkhuxestkhxngwithithukrupaebbthiminahnkrwmkhxngesnechuxmthukesnbnwithimakthisud dngnn pyhawithiyawsudcungepnpyhapraephth Optimization Problem khuxaekpyhaodykarhaphllphththidithisudthiepnipidnnexng xyangirktampyhawithiyawsudsamarthprbihepnpyhakartdsinicidodykarkahndtwelkh k khunmatwhnungaelwthampyhawa inkrafnimiwithiyawsudthiyawimnxykwa k hruxim cakkarphisucnwapyhawithiyawsudepnpyhainklumexnphibriburndngnncunghmaykhwamwapyhanisamarthhakhatxbodyich Non deterministic function hruxsamarthtrwckhatxbichidinewlathiepnfngkchnphhunamnnexng odykartrwckhatxbichnnthaidodykarsnghlkthan Certificate C ekhaipinfngkchnody C epnwithihnunginkrafsungmiwithiyawsudyawkwahruxethakb k kcathaihfngkchntrwckhatxbthanganidinewlathiepnfngkchnphhunamkhntxnwithikhxmulnaekha kraf G pmerimtn a epnsmachikkhxng G V pmplaythang b epnsmachikkhxng G V khxmulsngxxk rayathangkhxngwithithiyawthisudcakpm a ipyngpm b bnkraf G sahrbkrafthisamathnamaichepnkhxmulnaekha nnsamarthepnkrafidkid odyhakepnkrafthwngnahnkthwip General Weighted Graph inpccubnyngimmiikhrkhnphbkhntxnwithithiichewlathiepnfngkchnphhunamid aetwasahrbkaraekpyhawithiyawsudthingaynn krafthirbmacaepnkrafxwtckrrabuthisthang dngthicaaesdngtxipnisahrbkrafxwtckrrabuthisthang withiyawsudbnkrafxwtckrrabuthisthangaebbthwngnahnk cakpm A ipyngpm G aethndwyluksrsiaedng krafxwtckrrabuthisthang Directed acyclic graph hruxxksryxwa DAG epnkrafrabuthisthang thiimmiwtckraebbrabuthisthangidinkraf khntxnwithisahrbaekpyhawithiyawsudbnkrafxwtckrrabuthisthang xacichkarprbepliynmacakpyhawithisnsud odysrangkrafihmkhunma G odyihkrafihmnimipmaelaesnechuxmehmuxnkrafedimthukprakar aetnahnkkhxngesnechuxmihepliynepnkhatidlbkhxngkhaedim aelwnakrafihmnimaaekpyhaaebbwithisnsud kcaidwawithisnsudkhxngkrafihm kcaklayepnwithiyawsudkhxngkrafedimnnexng int LogestPathDAG Graph G Vertex Start Vertex End construct Graph G G V G V G E G E G w G w return shortestPathDAG G Start End khntxnwithidngklawkcamiewlainkarthanganethakb ewlainkarsrangkrafihm epn O G E ewlainkaraekpyhawithisnsud khunkbkhntxnwithithiich echn khntxnwithikhxngidkhstra caichewlainkarthanganepn O G E log G V cungidewlainkarthanganrwm krniichkhntxnwithikhxngidkhstra epn O G E log G V xyangirktam karaekpyhawithiyawsudbnkrafxwdckrrabuthisthangnn mixlkxrithumthisamarththanganiderwkwakhntxnwithikhangtn nnkhuxichkahndkarphlwt Dynamic programming sungmikhntxndngniint LongestPathDAG Graph G Vertex Start Vertex End topologicalSorting G int distance G V arrage by sorted G for each vertex u in topOrder of G V for each edge e in G E point from u to v if distance v lt distance u weight e distance v distance u weight e return max value element in distance prasiththiphaphinkarthangankhxkhntxnwithiniekidcak ewlainkareriyngladbaebbthxphxlxyi epn O G V G E ewlainkartrwcsxbaelaepliynkhainxaery distance epn O G E ewlainkarhakhamaksudinxaery distance epn O G V rwmepnewlainkarthanganthnghmd O G V G E sahrbkrafxun khntxnwithisahrb Interval Graphs khntxnwithisahrb Ptolemaic Graphs khntxnwithisahrb Small Graph Classes khntxnwithisahrb Cocomparability Graphskhntxnwithixunthiekiywkhxng Topological sorting khntxnwithikhxngidkhstra Dijkstra algorithm pyhathiekiywkhxngpyhawithisnsud Shortest path problem Hamiltonian path problem Travelling salesman problem xangxing khlngkhxmulekaekbcakaehlngedimemux 2007 06 11 subkhnemux 2011 09 29 Dynamic programming PDF khlngkhxmulekaekbcakaehlngedimemux 2011 08 19 subkhnemux 2011 09 29 Ioannidou Kyriaki Longest path problem on Interval Graphs PDF Takahara Yoshihiro Longest path problem on Ptolemaic Graphs Uehara Ryuhei Longest path problem on Small Graph Classes Longest path problem on Cocomparability GraphsaehlngkhxmulxunNP Completeness Source of the algorithm Find the Longest Path by Daniel J Barrett Efficient Algorithms for the Longest Path Problem by Ryuhei UEHARA JAIST Yushi UNO Osaka Prefecture University lingkesiy On the relation between the travelling salesman and the longest path problems by William W Hardgrave and George L Nemhauser