ฉันกำลังพยายามหากลไกการค้นหาเส้นทางที่เร็วขึ้นในเกมที่ฉันกำลังสร้างกราฟโหนดที่เชื่อมต่ออยู่ โหนดแบ่งออกเป็นสองประเภท ได้แก่ "เครือข่าย" และ "เราเตอร์"
ในภาพนี้ วงกลมสีน้ำเงินแสดงถึงเราเตอร์และเครือข่ายสี่เหลี่ยมสีเทา
แต่ละเครือข่ายจะเก็บรายการเราเตอร์ที่เชื่อมต่ออยู่ และในทางกลับกัน เราเตอร์ไม่สามารถเชื่อมต่อกับเราเตอร์อื่นได้โดยตรง และเครือข่ายไม่สามารถเชื่อมต่อกับเครือข่ายอื่นได้โดยตรง
รายการเครือข่ายที่เราเตอร์เชื่อมต่ออยู่
เราเตอร์ก็ทำเช่นเดียวกัน
ฉันจำเป็นต้องมีอัลกอริทึมที่จะแมปเส้นทาง ซึ่งวัดจากจำนวนเครือข่ายที่ข้าม สำหรับแต่ละเครือข่ายต้นทางและปลายทางที่เป็นไปได้ ยกเว้นเส้นทางที่ต้นทางและปลายทางเป็นเครือข่ายเดียวกัน ฉันมีอันหนึ่งในตอนนี้ แต่มันช้าจนใช้งานไม่ได้ โดยใช้เวลาประมาณสองวินาทีในการกำหนดเส้นทาง ซึ่งจะกลายเป็นที่สังเกตได้อย่างไม่น่าเชื่อสำหรับผู้เล่นที่เชื่อมต่อทั้งหมด
อัลกอริธึมปัจจุบันเป็นการค้นหาแบบเดรัจฉานในเชิงลึกก่อน (มันถูกรวมเข้าด้วยกันในเวลาประมาณหนึ่งชั่วโมงเพื่อให้การแคชพาธทำงาน) ซึ่งจะส่งคืนอาร์เรย์ของเครือข่ายตามลำดับที่พวกมันถูกสำรวจ ซึ่งอธิบายว่าทำไมมันจึงช้ามาก มีอัลกอริธึมใดบ้างที่มีประสิทธิภาพมากขึ้น?
โปรดทราบว่าในขณะที่กราฟตัวอย่างเหล่านี้มีเครือข่ายสี่เครือข่าย แต่กราฟในทางปฏิบัติมีเครือข่าย 55 เครือข่ายและมีเราเตอร์ประมาณ 20 ตัวที่ใช้งานอยู่ เส้นทางที่เป็นไปไม่ได้ก็สามารถเกิดขึ้นได้เช่นกัน และเมื่อใดก็ตามภูมิประเทศกราฟเครือข่าย/เราเตอร์สามารถเปลี่ยนแปลงได้ โดยกำหนดให้แคชเส้นทางต้องถูกสร้างขึ้นใหม่
วิธีการ/อัลกอริทึมใดน่าจะให้ผลลัพธ์ที่ดีที่สุดสำหรับกราฟประเภทนี้
