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

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

ปัญหาวิถียาวสุด (อังกฤษ: Longest path problem) เป็นหนึ่งในปัญหาทางคณิตศาสตร์ในเรื่องทฤษฎีกราฟ ซึ่งมีไว้สำหรับค้นหาวิถีเชิงเดียว (Simple path) ที่มีระยะทางมากที่สุดนับจากปมเริ่มต้นไปยังปมปลายทางบนกราฟถ่วงน้ำหนัก (Weighted graph) ลักษณะของปัญหาวิถียาวสุดจะคล้ายคลึงกันกับปัญหาวิถีสั้นสุด (Shortest path problem) ซึ่งเป็นการหาวิถีเชิงเดียวบนกราฟที่มีระยะทางสั้นที่สุดแทน เราสามารถหาวิถีสั้นสุดบนกราฟใดๆได้ในเวลาที่เป็นฟังก์ชันพหุนาม (Polynomial time) นั่นหมายถึงปัญหาวิถีสั้นสุดที่ลักษณะของปัญหาเป็นแบบปัญหาการตัดสินใจนั้นจัดอยู่ในกลุ่มความซับซ้อนแบบพี แต่ในทางกลับกัน ปัญหาวิถียาวสุดนั้นกลับยังไม่มีขั้นตอนวิธีใดที่ทำงานได้อย่างถูกต้องในเวลาที่เป็นฟังก์ชันพหุนาม กล่าวคือเป็นปัญหาที่อยู่ในกลุ่มเอ็นพี และได้รับการพิสูจน์แล้วว่าปัญหาวิถียาวสุดนั้นเกิดจากการลดรูปมาจากปัญหาวิถีฮัลมินตัน (Hamiltonian path problem) ซึ่งอยู่ในกลุ่มเอ็นพีบริบูรณ์[1] ทำให้ปัญหานี้อยู่ในกลุ่มเอ็นพีบริบูรณ์เช่นเดียวกัน

รายละเอียด[แก้]

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

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

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

รวมเป็นเวลาในการทำงานทั้งหมด O(|G.V| + |G.E|)

สำหรับกราฟอื่นๆ[แก้]

  • ขั้นตอนวิธีสำหรับ Interval Graphs[4]
  • ขั้นตอนวิธีสำหรับ Ptolemaic Graphs[5]
  • ขั้นตอนวิธีสำหรับ Small Graph Classes[6]
  • ขั้นตอนวิธีสำหรับ Cocomparability Graphs[7]

ขั้นตอนวิธีอื่นๆที่เกี่ยวข้อง[แก้]

ปัญหาที่เกี่ยวข้อง[แก้]

อ้างอิง[แก้]

  1. A proof that longest path is NP-complete
  2. Dynamic programming (PDF)
  3. Topological sorting
  4. Ioannidou, Kyriaki, Longest path problem on Interval Graphs (PDF)
  5. Takahara, Yoshihiro, Longest path problem on Ptolemaic Graphs
  6. Uehara, Ryuhei, Longest path problem on Small Graph Classes
  7. Longest path problem on Cocomparability Graphs

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