Kürzester Pfad zwischen zwei Punkten im Koordinatensystem

Question

Ich habe zwei Punkte A und B. Ich möchte den kürzesten Weg von A nach B finden, aber es gibt N (bis zu 200) Rechtecke und der Pfad kann keines dieser Rechtecke schneiden . Pfad und Rechtecke können sich nur an den Ecken der Rechtecke und an den Seiten des Rechtecks ​​schneiden. Wie lang ist der kürzeste Weg? Rechtecke können sich nicht schneiden. Sie können Punkt oder Seite teilen. Wenn also zwei von ihnen eine Seite teilen, können Sie zwischen ihnen wechseln.

Answer 1

Normalerweise ist der beste Algorithmus für diese Art von Problemen A* mit einer einfachen Heuristik wie Manhattan Distance. Aber zuerst solltest du die illegalen Punkte finden. Illegale Punkte sind diejenigen, die Sie nicht in dieses Problem eingeben können. Die Punkte innerhalb eines Rechtecks ​​sind illegal (Punkte, die sich an den Seiten der Rechtecke befinden, sind legal, da Sie sie passieren können). Nachdem Sie diese Punkte gefunden haben, implementieren Sie einfach einen A * -Algorithmus, um den kürzesten Pfad zwischen A und B zu finden.

Beachten Sie, dass, da es kein Kantengewicht in diesem Problem gibt, Sie einfach ein BFS ausführen können, um den kürzesten Pfad zu finden, aber es wird nicht so schnell wie A * sein.

Wenn Ihr Suchbereich sehr groß ist und Sie mit A * nicht genügend Speicherplatz haben, sollten Sie die Verwendung von IDA* in Erwägung ziehen, die zwar weniger Arbeitsspeicher beansprucht, aber Knoten mehr als einmal untersucht.