อัลกอริทึม Pathfinding สำหรับแผนที่ต่อเนื่อง (เช่นรูปหลายเหลี่ยม)

Question

ฉันพยายามตรวจสอบอัลกอริทึมที่แตกต่างกันสำหรับเส้นทางสั้น ๆ ระหว่างจุดสองจุดในระนาบที่มีสิ่งกีดขวางหลายเหลี่ยม อัลกอริทึมส่วนใหญ่ที่ฉันพบใช้แผนที่แยก (Grid Map, กราฟการมองเห็น, Voronoi Roadmap ฯลฯ ) หนังสือบางเล่ม (เช่น“ องค์ประกอบของหุ่นยนต์” โดย Ben-Ari หรือ“ Introduction to Autonomous Robots” โดย Nikolaus Correll) กล่าวถึงแผนที่ต่อเนื่อง (เช่นข้อมูลรูปหลายเหลี่ยมดิบ) แต่ไม่ได้อธิบายอัลกอริทึมที่เกี่ยวข้อง พวกเขาอ้างข้อได้เปรียบด้านความจำหรือประสิทธิภาพสำหรับอุปสรรคเพียงเล็กน้อยและเรียบง่ายซึ่งอาจเป็นเรื่องที่น่าสนใจมากสำหรับฉัน

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

มีแหล่งข้อมูลสำหรับอัลกอริทึมเส้นทางสั้น ๆ โดยใช้แผนที่ต่อเนื่องหรือคำหลักที่มีประโยชน์ในการค้นหาหรือไม่?

---

เช่นเดียวกับที่แนะนำฉันพยายามระบุคำศัพท์ที่ฉันใช้:

แผนที่ต่อเนื่อง (ดูภาพประกอบ ) อ้างถึงการจัดเก็บค่าจำนวนจริง (ต่อเนื่อง) ของรูปทรงเรขาคณิต อุปสรรค / สามเหลี่ยม I. จะถูกจัดเก็บเป็น: A = (3,2), B = (7,5), C = (7,2)

แผนที่แยก (ดูภาพประกอบ ) หมายถึงการแบ่งส่วนย่อยออกเป็นชิ้น ๆ (การแยกความแตกต่างเช่นในแผนที่ตาราง) อุปสรรค / สามเหลี่ยม I. จะถูกจัดเก็บเป็นดัชนีเซลล์: (3,2), (4,2), (5,2), (6,2), (5,3), (6,3), ( 6,4) การค้นหาเส้นทางในแผนที่แยกมักทำได้โดยอัลกอริทึมที่ใช้กราฟเช่น Dijkstra หรือ A *

การคำนวณทางเรขาคณิตเป็นเพียงคำที่คลุมเครือที่ฉันใช้สำหรับการดำเนินการของเรขาคณิตเชิงคำนวณที่ฉันคาดหวังในอัลกอริทึมการค้นหาเส้นทางสำหรับแผนที่ต่อเนื่อง (เช่นการแปลระยะตั้งฉากการตรวจจับจุดตัด)

Answer 1

สำหรับ "แผนที่ต่อเนื่อง" อย่างที่คุณเรียกมันเพียงแค่ใช้ Dijkstra กับจุดยอดทั้งหมดของคุณ ข้อแตกต่างเพียงอย่างเดียวคือคุณต้องตรวจสอบการตัดเมื่อคำนวณระยะห่างระหว่างโหนด

Answer 2

อีกประการหนึ่งที่ใช้บ่อยขึ้นในระยะสำหรับปัญหาของฉันดูเหมือนจะเป็นแบบยุคลิดเส้นทางที่สั้นที่สุด (s) ความแตกต่างระหว่างอัลกอริทึมสำหรับแผนที่ต่อเนื่องและแผนที่แยกดูเหมือนจะค่อนข้างคลุมเครือสำหรับฉัน

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

สำหรับข้อมูลเพิ่มเติมโปรดดู:

• "Euclidean Shortest Paths ที่แน่นอนหรืออัลกอริทึมโดยประมาณ" โดย F. Li และ R. Klette
• แอนิเมชั่นที่ดี แต่เป็นรถที่น่ารักโดย Ivan Chen
• ใบสมัครโดย Anton Kovsharov

อาจมีคนโต้แย้งว่าแผนที่เส้นทางที่สั้นที่สุดที่สร้างขึ้นเป็นเพียงการแยกความแตกต่างของพื้นที่การกำหนดค่าแบบต่อเนื่อง อย่างไรก็ตามฉันเดาว่าแผนที่เส้นทางที่สั้นที่สุดเป็นเพียงผลลัพธ์ที่สามารถรับได้หากใช้อัลกอริทึมกับพื้นที่กำหนดค่าทั้งหมด หากต้องการเพียงเส้นทางที่สั้นที่สุดระหว่างสองจุดอัลกอริทึมอาจหยุดทำงานหลังจากถึงจุดเป้าหมาย ฉันยังไม่แน่ใจเกี่ยวกับการจัดประเภทของอัลกอริทึมเหล่านี้ แต่สิ่งนี้ควรตอบคำถามของฉัน