As for finding K looping paths, Dre

As for finding K looping paths, Dreyfus algorithm [12] ran in OðKjV j log jV jÞ time given a shortest tree is available. Fox [13] gave an algorithm to run in OðjV j2 þ KjV j log jV jÞ time. Using a concept of path deletion, Martins [14] developed an algorithm with the worst time to be O(K3|V|). Later, this time was improved to be O(K2|A|) by Azevedo et al. [15] who used an efficient implementation. Martins path deletion was generalized by Villeneuve and Desaulniers [16] who developed the solution for the shortest path problem with forbidden paths. The algorithm of Azevedo et al. [15] formed the basis of Yang and Chen [17] who developed a polynomial time algorithm for finding K shortest looping paths in a traffic–light network. Eppstein [18] used an implicit representation of paths to run in O(|A| + |V|log|V| + K|V|) time. On the basis of Eppsteins algorithm, Jime´nez and Marzal [19] proposed a modified version that improved computational performance in practice. For a traffic–light network, Yang and Chen [20] developed a polynomial time algorithm to find K shortest ‘‘unique-arc walks,’’ which means that the path may include repeated nodes but will exclude repeated arcs. Other recent developments related to K shortest paths can be found in [21,22].

ผลลัพธ์ (ไทย) 1:

สำหรับค้นหามีการวนรอบเส้นทาง อัลกอริทึม Dreyfus [12] K วิ่งในล็อกเจ OðKjV jV jÞ เวลาให้สั้นที่สุดต้นไม้ได้ จิ้งจอก [13] ให้อัลกอริทึมการทำงานใน OðjV þ j2 j ทั้งฉบับ KjV บันทึกเวลา jÞ jV ใช้แนวคิดของการลบเส้นทาง Martins [14] พัฒนาอัลกอริทึมการ มีเวลาเลวร้ายที่สุดเป็น O (K3|V|) ขณะนี้ถูกปรับปรุงเป็น O (K2| ภายหลังA|) โดย Azevedo et al. [15] ซึ่งใช้การนำไปใช้อย่างมีประสิทธิภาพ การลบเส้นทาง Martins ถูกตั้งค่าทั่วไปทาง Villeneuve Desaulniers [16] ผู้พัฒนาโซลูชั่นสำหรับปัญหาเส้นทางสั้นที่สุดเส้นทางต้องห้าม อัลกอริทึมของ Azevedo et al. [15] รูปแบบพื้นฐานของยางและเฉิน [17] ซึ่งพัฒนาอัลกอริทึมเวลาโพลิโนเมียหา K มีการวนรอบเส้นทางในเครือข่าย – ไฟสั้นที่สุด Eppstein [18] ใช้แสดงเส้นทางการนัยใช้ O (|A| + |V|log|V| + K|V|) เวลา โดยใช้อัลกอริทึม Eppsteins, Jime´nez และ Marzal [19] เสนอปรับเปลี่ยนที่ปรับปรุงประสิทธิภาพการทำงานคำนวณในทางปฏิบัติ สำหรับเครือข่าย – ไฟ ยางและเฉิน [20] พัฒนาเป็นเวลาโพลิโนเมียอัลกอริทึมในการค้นหา K สั้น ''เฉพาะส่วนโค้งเดิน ซึ่งหมายความ ว่า เส้นทางรวมถึงโหนซ้ำ แต่จะแยกส่วนที่ซ้ำ พัฒนาอื่น ๆ ล่าสุดเกี่ยวข้องกับ K ที่สั้นที่สุดเส้นทางที่สามารถพบได้ใน [21,22]

ผลลัพธ์ (ไทย) 2:

ในฐานะที่เป็นสำหรับการค้นหาเส้นทาง K วนลูป, อัลกอริทึมเดรย์ฟั [12] วิ่งในOðKjV J บันทึกเวลา JV JTH ให้ต้นไม้ที่สั้นที่สุดสามารถใช้ได้ ฟ็อกซ์ [13] ให้ขั้นตอนวิธีการที่จะทำงานในOðjV j2 þ KJV J บันทึกเวลา JV JTH โดยใช้แนวคิดของการลบเส้นทาง, มาร์ติน [14] การพัฒนาอัลกอริทึมที่มีเวลาที่เลวร้ายที่สุดที่จะเป็น O (K3 | V |) ต่อมาคราวนี้ได้รับการปรับปรุงให้เป็น O (K2 | |) โดย Azevedo และคณะ [15] ที่ใช้ในการดำเนินงานที่มีประสิทธิภาพ เส้นทางการลบมาร์ตินได้รับการทั่วไปโดยเนิฟและ Desaulniers [16] ที่พัฒนาทางออกสำหรับปัญหาเส้นทางที่สั้นที่สุดที่มีเส้นทางที่ต้องห้าม อัลกอริทึมของ Azevedo และคณะ [15] เป็นพื้นฐานของยางและเฉิน [17] ที่พัฒนาอัลกอริทึมเวลาพหุนามสำหรับการค้นหา K เส้นทางวนรอบที่สั้นที่สุดในเครือข่ายไฟจราจร Eppstein [18] ใช้แทนโดยนัยของเส้นทางที่จะวิ่งใน O (| | + | V | เข้าสู่ระบบ | V | + K | V |) เวลา บนพื้นฐานของอัลกอริทึม Eppsteins, Jime'nez และ Marzal [19] เสนอแก้ไขฉบับที่ปรับปรุงประสิทธิภาพการประมวลผลในทางปฏิบัติ สำหรับเครือข่ายไฟจราจร, ยางและเฉิน [20] การพัฒนาอัลกอริทึมเวลาพหุนามที่จะหา K ที่สั้นที่สุด '' เดินไม่ซ้ำกันโค้ง '' ซึ่งหมายความว่าเส้นทางที่อาจรวมถึงโหนดซ้ำแล้วซ้ำอีก แต่จะไม่รวมโค้งซ้ำแล้วซ้ำอีก ความคืบหน้าล่​​าสุดอื่น ๆ ที่เกี่ยวข้องกับเส้นทางที่สั้นที่สุด K สามารถพบได้ใน [21,22]

ผลลัพธ์ (ไทย) 3:

สำหรับการหา K ปิดเส้นทาง เดรย์ฟัสขั้นตอนวิธี [ 12 ] วิ่งในโอð KJV J J Þบันทึกจำนวนเวลาสั้นที่สุด ต้นไม้ที่สามารถใช้ได้ สุนัขจิ้งจอก [ 13 ] ให้วิธีการทำงานใน O ð JV j2 þ KJV J J Þบันทึกจำนวนเวลา ใช้แนวคิดของการลบเส้นทางมาร์ติน [ 14 ] พัฒนาอัลกอริทึมกับเวลาที่เลวร้ายที่สุดเป็น O ( K3 | V | ) ต่อมา เวลานี้กำลังปรับปรุงอยู่ o ( K2 | เป็น | ) โดย ซเวโด้ et al .[ 15 ] ใครใช้เพื่อการปฏิบัติงานที่มีประสิทธิภาพ ทางลบคือ ทั่วไป โดย มาร์ติน วิลล์เนิฟ และ desaulniers [ 16 ] ผู้ที่พัฒนาโซลูชั่นสำหรับปัญหาวิถีสั้นสุดต้องห้ามเส้นทาง ขั้นตอนวิธีของ ซเวโด้ et al . [ 15 ] รูปแบบพื้นฐานของหยางเฉิน [ 17 ] การพัฒนาที่พหุนามเวลา ขั้นตอนการหาเส้นทางที่สั้นที่สุดใน k วนลูปและจราจรเครือข่ายeppstein [ 18 ] ใช้แสดงนัยของเส้นทางวิ่งใน O ( | เป็น | | V | เข้าสู่ระบบ | V | K | V | ) เวลา บนพื้นฐานของ eppsteins ขั้นตอนวิธีใหม่และ jime เนซ marzal [ 19 ] เสนอแก้ไขรุ่นที่ปรับปรุงการคำนวณสมรรถนะในการปฏิบัติงาน สำหรับการจราจร–แสงเครือข่าย หยางเฉิน [ 20 ] พัฒนาโดยใช้เวลาสั้นที่สุด วิธีหา K ' 'unique-arc เดิน' ' ซึ่งแปลว่าเส้นทางที่อาจรวมถึง แต่ไม่ต้องย้ำซ้ำจุดโค้ง ความคืบหน้าล่าสุดที่เกี่ยวข้องอื่น ๆของเส้นทางสั้นที่สุดสามารถพบได้ใน [ 21,22 ]