การค้นหาเส้นทางหรือการกำหนดเส้นทางคือ การใช้โปรแกรมคอมพิวเตอร์ในการค้นหาเส้นทางที่สั้นที่สุดระหว่างสองจุด นับเป็นรูปแบบที่ใช้งานได้จริงมากกว่าการแก้ปัญหาเขาวงกตสาขาการวิจัยนี้อาศัยอัลกอริทึมของไดจ์กสตรา (Dijkstra) เป็นหลัก ในการค้นหาเส้นทางที่สั้นที่สุดบน กราฟ ถ่วงน้ำหนัก

การค้นหาเส้นทางมีความเกี่ยวข้องอย่างใกล้ชิดกับปัญหาเส้นทางที่สั้นที่สุดในทฤษฎีกราฟซึ่งเป็นการศึกษาถึงวิธีการระบุเส้นทางที่ตรงตามเกณฑ์บางอย่างได้ดีที่สุด (สั้นที่สุด ราคาถูกที่สุด เร็วที่สุด ฯลฯ) ระหว่างสองจุดในเครือข่ายขนาดใหญ่

โดยหลักการแล้ว วิธีการค้นหาเส้นทางจะค้นหากราฟโดยเริ่มจากจุดยอด หนึ่ง และสำรวจจุดยอด ที่อยู่ติดกัน จนกว่าจะถึงจุดยอดปลายทาง โดยทั่วไปแล้วมีจุดประสงค์เพื่อค้นหาเส้นทางที่ถูกที่สุด แม้ว่าวิธีการค้นหากราฟ เช่นการค้นหาแบบกว้าง (breadth-first search)จะสามารถหาเส้นทางได้หากมีเวลาเพียงพอ แต่วิธีการอื่นๆ ที่ "สำรวจ" กราฟ มักจะไปถึงปลายทางได้เร็วกว่า เปรียบเทียบได้กับคนคนหนึ่งที่กำลังเดินข้ามห้อง แทนที่จะตรวจสอบเส้นทางที่เป็นไปได้ทั้งหมดล่วงหน้า คนคนนั้นมักจะเดินไปในทิศทางของปลายทางและจะเบี่ยงเบนจากเส้นทางก็ต่อเมื่อหลีกเลี่ยงสิ่งกีดขวางเท่านั้น และจะเบี่ยงเบนให้น้อยที่สุดเท่าที่จะเป็นไปได้

ปัญหาหลักสองประการของการค้นหาเส้นทางคือ (1) การหาเส้นทางระหว่างสองโหนดในกราฟและ (2) ปัญหาเส้นทางที่สั้นที่สุด — การหาเส้นทางที่สั้นที่สุดที่เหมาะสมที่สุดอัลกอริทึมพื้นฐาน เช่น การค้นหา แบบกว้างและแบบลึกจะแก้ปัญหาแรกโดยการสำรวจ ความเป็นไปได้ทั้งหมด โดยเริ่มจากโหนดที่กำหนด พวกมันจะวน ซ้ำไปตามเส้นทางที่เป็นไปได้ทั้งหมดจนกว่าจะถึงโหนดปลายทาง อัลกอริทึมเหล่านี้ทำงานใน${\displaystyle O(|V|+|E|)}$หรือใช้เวลาเชิงเส้น โดยที่ V คือจำนวนจุดยอด และ E คือจำนวนขอบระหว่างจุดยอด

ปัญหาที่ซับซ้อนกว่าคือการหาเส้นทางที่เหมาะสมที่สุด วิธีการที่ครอบคลุมทุกด้านในกรณีนี้เรียกว่าอัลกอริทึมเบลล์แมน-ฟอร์ดซึ่งให้ความซับซ้อนของเวลาเท่ากับ${\displaystyle O(|V||E|)}$หรือใช้เวลาแบบกำลังสอง อย่างไรก็ตาม ไม่จำเป็นต้องตรวจสอบเส้นทางที่เป็นไปได้ทั้งหมดเพื่อหาเส้นทางที่ดีที่สุด อัลกอริทึมเช่นA*และอัลกอริทึมของ Dijkstraจะกำจัดเส้นทางที่เป็นไปไม่ได้อย่างมีกลยุทธ์ ไม่ว่าจะผ่านทางฮิวริสติกส์หรือการเขียนโปรแกรมแบบไดนามิก การกำจัดเส้นทาง ที่เป็นไปไม่ได้ทำให้อัลกอริทึมเหล่านี้สามารถลดความซับซ้อนของเวลาลงได้ต่ำถึง${\displaystyle O(|E|\log(|V|))}$[ ^{1 ]​}

อัลกอริทึมข้างต้นเป็นอัลกอริทึมทั่วไปที่ดีที่สุดซึ่งทำงานบนกราฟโดยไม่ต้องประมวลผลล่วงหน้า อย่างไรก็ตาม ในระบบกำหนดเส้นทางการเดินทางในทางปฏิบัติ อัลกอริทึมที่สามารถประมวลผลกราฟล่วงหน้าเพื่อให้ได้ประสิทธิภาพที่ดีกว่าสามารถให้ความซับซ้อนของเวลาที่ดีกว่าได้^{[ 2 ]}อัลกอริทึมหนึ่งดังกล่าวคือ ลำดับชั้น การหดตัว

การค้นหาเส้นทางมีประวัติความเป็นมาของการรวมอยู่ในวิดีโอเกมที่มีวัตถุเคลื่อนที่หรือ NPC คริส ครอว์ฟอร์ดในปี 1982 อธิบายว่าเขา "ใช้เวลามากมาย" ในการพยายามแก้ปัญหาการค้นหาเส้นทางในTankticsซึ่งรถถังคอมพิวเตอร์ติดอยู่ในทะเลสาบรูปตัวยูบนบก "หลังจากความพยายามที่สูญเปล่ามากมาย ฉันก็ค้นพบวิธีแก้ปัญหาที่ดีกว่า: ลบทะเลสาบรูปตัวยูออกจากแผนที่" เขากล่าว^{[ 6 ]}

การค้นหาเส้นทางแบบลำดับชั้น

แนวคิดการค้นหาเส้นทางแบบลำดับชั้นมีมาก่อนการนำไปใช้ในอุตสาหกรรมวิดีโอเกมและมีรากฐานมาจากการวิจัยปัญญาประดิษฐ์แบบคลาสสิก คำอธิบายอย่างเป็นทางการที่เก่าแก่ที่สุดปรากฏในงานของ Sacerdoti เกี่ยวกับ ABSTRIPS (Abstraction-Based STRIPS ) ในปี 1974 ^{[ 7 ]}ซึ่งสำรวจกลยุทธ์การค้นหาแบบลำดับชั้นในการวางแผนตามตรรกะ การวิจัยในภายหลัง เช่น Hierarchical A* โดย Holte et al. ได้พัฒนาทฤษฎีลำดับชั้นของนามธรรมในปัญหาการค้นหาเพิ่มเติม^{[ 8 ]}

ในบริบทของวิดีโอเกม ความจำเป็นในการวางแผนอย่างมีประสิทธิภาพบนแผนที่ขนาดใหญ่ที่มีเวลา CPU จำกัด นำไปสู่การนำอัลกอริทึมการค้นหาเส้นทางแบบลำดับชั้นมาใช้ในทางปฏิบัติ ความก้าวหน้าที่โดดเด่นคือการแนะนำHierarchical Path-Finding A* (HPA*) โดย Botea et al. ในปี 2547 ^{[ 9 ]} HPA* แบ่งแผนที่ออกเป็นกลุ่มและคำนวณเส้นทางท้องถิ่นที่เหมาะสมที่สุดระหว่างจุดทางเข้าของกลุ่มที่อยู่ติดกันล่วงหน้า ในระหว่างการทำงาน จะวางแผนเส้นทางนามธรรมผ่านกราฟกลุ่ม จากนั้นปรับปรุงเส้นทางนั้นภายในแต่ละกลุ่ม ซึ่งช่วยลดพื้นที่การค้นหาลงอย่างมากและช่วยให้สามารถวางแผนได้ใกล้เคียงกับค่าที่เหมาะสมที่สุดด้วยประสิทธิภาพที่เร็วกว่ามาก

Partial-Refinement A* (PRA*) ซึ่งพัฒนาโดย Sturtevant และ Buro ใช้แนวทางที่คล้ายกัน แต่เน้นการวางแผนและการดำเนินการแบบสลับกัน แทนที่จะปรับปรุงเส้นทางทั้งหมดในทันที PRA* จะปรับปรุงเพียงไม่กี่ขั้นตอนแรก และดำเนินการปรับปรุงส่วนที่เหลือต่อไปตามความจำเป็นในระหว่างการปฏิบัติงาน ซึ่งมีประโยชน์อย่างยิ่งในสภาพแวดล้อมแบบไดนามิก

เทคนิคที่คล้ายกันนี้ ได้แก่ตาข่ายนำทาง (navmesh) ซึ่งใช้สำหรับการวางแผนทางเรขาคณิตในเกม และการวางแผนการขนส่ง แบบหลายรูปแบบ เช่น ในรูปแบบต่างๆ ของปัญหาพนักงานขายเดินทางที่เกี่ยวข้องกับการขนส่งหลายประเภท

ตัววางแผนแบบลำดับชั้นจะทำการค้นหาเส้นทางในสองขั้นตอน: ขั้นแรก ระหว่างคลัสเตอร์ในระดับสูง จากนั้น ภายในคลัสเตอร์แต่ละคลัสเตอร์ในระดับต่ำ^{[ 10 ]}โครงสร้างนี้ช่วยให้การค้นหาแบบโลคอลที่มีคำแนะนำด้วยโหนด ที่น้อยลง ส่งผลให้มีประสิทธิภาพสูง ข้อเสียหลักคือความซับซ้อนในการใช้งานในการรักษาเลเยอร์นามธรรมและการปรับปรุง

ตัวอย่าง

แผนที่ขนาด 3000×2000 โหนดประกอบด้วยไทล์ 6 ล้านไทล์ การวางแผนเส้นทางโดยตรงในระดับนี้ แม้จะใช้อัลกอริธึม ที่ปรับให้เหมาะสมแล้ว ก็ยังต้องใช้การคำนวณอย่างมากเนื่องจากจำนวนโหนดกราฟและเส้นทางที่เป็นไปได้มีจำนวนมหาศาล วิธีการแบบลำดับชั้นจะแบ่งแผนที่ออกเป็นกลุ่มโหนดขนาด 300×200 โหนด ทำให้เกิดตารางขนาด 10×10 (รวม 100 กลุ่ม) กราฟนามธรรมระดับสูงจะมีเพียง 100 โหนดเท่านั้น การวางแผนเส้นทางระหว่างกลุ่มเหล่านี้ใช้การคำนวณน้อย เมื่อพบเส้นทางนามธรรมแล้ว แต่ละกลุ่มบนเส้นทางจะถูกประมวลผลโดยใช้ตัววางแผน A* ทั่วไป เพื่อค้นหาเส้นทางระดับต่ำที่แน่นอนภายในกลุ่มนั้น กระบวนการสองขั้นตอนนี้ช่วยเพิ่มประสิทธิภาพอย่างมากในขณะที่ยังคงรักษาคุณภาพของเส้นทางให้ใกล้เคียงกับค่าที่เหมาะสมที่สุด

• อัลกอริทึมของไดจ์กสตรา
• อัลกอริทึมการค้นหา A*ซึ่งเป็นกรณีพิเศษของอัลกอริทึมของ Dijkstra
• D*คือกลุ่มของ อัลกอริธึม การค้นหาแบบฮิวริสติกแบบเพิ่มทีละขั้นสำหรับปัญหาที่ข้อจำกัดเปลี่ยนแปลงไปตามเวลา หรือไม่เป็นที่ทราบอย่างสมบูรณ์เมื่อตัวแทนวางแผนเส้นทางครั้งแรก
• อัลกอริทึม การวางแผนเส้นทางแบบทุกมุมคือกลุ่มของอัลกอริทึมสำหรับการวางแผนเส้นทางที่ไม่จำกัดเฉพาะการเคลื่อนที่ตามขอบในกราฟการค้นหา ออกแบบมาเพื่อให้สามารถรับมุมใดก็ได้ และด้วยเหตุนี้จึงสามารถค้นหาเส้นทางที่สั้นกว่าและตรงกว่าได้

การค้นหาเส้นทางแบบหลายเอเจนต์คือการค้นหาเส้นทางสำหรับเอเจนต์หลายตัวจากตำแหน่งปัจจุบันไปยังตำแหน่งเป้าหมายโดยไม่ชนกัน ในขณะเดียวกันก็ปรับฟังก์ชันต้นทุนให้เหมาะสมที่สุด เช่น ผลรวมของความยาวเส้นทางของเอเจนต์ทั้งหมด ถือเป็นการขยายผลของการค้นหาเส้นทาง อัลกอริทึมการค้นหาเส้นทางแบบหลายเอเจนต์จำนวนมากได้รับการขยายมาจาก A* หรืออิงจากการลดรูปไปสู่ปัญหาอื่น ๆ ที่ได้รับการศึกษามาเป็นอย่างดี เช่น การเขียนโปรแกรมเชิงเส้นจำนวนเต็ม^{[ 11 ]}อย่างไรก็ตาม อัลกอริทึมดังกล่าวมักจะไม่สมบูรณ์ กล่าวคือ ยังไม่ได้รับการพิสูจน์ว่าสามารถสร้างโซลูชันได้ภายในเวลาพหุนาม แนวทางแบบขนานบางอย่าง เช่นCollaborative Diffusionนั้นอิงจาก อัลกอริทึม แบบขนานที่ง่ายต่อการใช้งาน ซึ่งกระจายการค้นหาเส้นทางแบบหลายเอเจนต์ไปยังโครงสร้างตารางการคำนวณ เช่น เซลล์ที่คล้ายกับออโตมาตาเซลลูลาร์อัลกอริทึมประเภทอื่นเสียสละความเหมาะสมที่สุดเพื่อประสิทธิภาพโดยการใช้รูปแบบการนำทางที่รู้จัก (เช่น การไหลของจราจร) หรือโทโพโลยีของพื้นที่ปัญหา^{[ 12 ]}

• การวางแผนเส้นทางในทุกมุม– อัลกอริทึมเพื่อค้นหาเส้นทางที่สั้นที่สุดในปริภูมิยูคลิด 
• การวางแผนการเคลื่อนที่– ปัญหาเชิงคำนวณ 

• https://melikpehlivanov.github.io/AlgorithmVisualizer
• https://sourceforge.net/projects/argorha
• StraightEdgeโปรเจ็กต์โอเพนซอร์สที่เขียนด้วยภาษา Java สำหรับการค้นหาเส้นทาง 2 มิติ (โดยใช้ A * ) และระบบแสงสว่าง รวมถึงแอปเพล็ตสาธิต
• python-pathfinding โปรเจก ต์โอเพนซอร์สที่เขียนด้วยภาษา Python สำหรับการค้นหาเส้นทาง 2 มิติ (โดยใช้อัลกอริธึมของ Dijkstra) และการให้แสงสว่าง
• Daedalus Libเป็นโอเพนซอร์ส Daedalus Lib จัดการการสร้างแบบจำลองสภาพแวดล้อม 2 มิติแบบสามเหลี่ยมและการค้นหาเส้นทางแบบไดนามิกอย่างสมบูรณ์โดยใช้อัลกอริธึม A* และ funnel
• การแสดงภาพอัลกอริทึมการค้นหาเส้นทางบนแผนที่จริงบนYouTube