ปัญหาวิถียาวสุด

ปัญหาวิถียาวสุด (อังกฤษ: 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) ในปัจจุบันยังไม่มีใครค้นพบขั้นตอนวิธีที่ใช้เวลาที่เป็นฟังก์ชั่นพหุนามได้ แต่ว่าสำหรับการแก้ปัญหาวิถียาวสุดที่ง่ายนั้น กราฟที่รับมาจะเป็นกราฟอวัฏจักรระบุทิศทาง ดังที่จะแสดงต่อไปนี้

สำหรับกราฟอวัฏจักรระบุทิศทาง

ไฟล์:Longestdag.png

วิถียาวสุดบนกราฟอวัฏจักรระบุทิศทางแบบถ่วงน้ำหนัก จากปม A ไปยังปม G แทนด้วยลูกศรสีแดง

กราฟอวัฏจักรระบุทิศทาง (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);
    }

ขั้นตอนวิธีดังกล่าวก็จะมีเวลาในการทำงานเท่ากับ

1. เวลาในการสร้างกราฟใหม่ เป็น O(|G.E|)
2. เวลาในการแก้ปัญหาวิถีสั้นสุด (ขึ้นกับขั้นตอนวิธีที่ใช้) เช่น ขั้นตอนวิธีของไดค์สตรา จะใช้เวลาในการทำงานเป็น 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
    }

ประสิทธิภาพในการทำงานขอขั้นตอนวิธีนี้เกิดจาก

1. เวลาในการเรียงลำดับแบบทอพอลอยี เป็น O(|G.V| + |G.E|)
2. เวลาในการตรวจสอบและเปลี่ยนค่าในอาเรย์ distance เป็น O(|G.E|)
3. เวลาในการหาค่ามากสุดในอาเรย์ 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)

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

• 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