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

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

ขั้นตอนวิธีดังกล่าวก็จะมีเวลาในการทำงานเท่ากับ
# เวลาในการสร้างกราฟใหม่ เป็น **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)

## อ้างอิง

## แหล่งข้อมูลอื่น
* 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

หมวดหมู่:ทฤษฎีเครือข่าย
หมวดหมู่:ทฤษฎีกราฟ