Wegfindung - A * mit geringsten Umdrehungen

Question

Ist es möglich, A * so zu ändern, dass der kürzeste Weg mit der geringsten Anzahl von Umdrehungen zurückgegeben wird?

Eine Komplikation: Knoten können nicht mehr nur durch ihren Standort unterschieden werden, da ihr Elternknoten für die Bestimmung zukünftiger Abbiegungen relevant ist, daher müssen sie auch eine Richtung haben.

Aber das Hauptproblem, das ich habe, ist, wie man die Anzahl der Umdrehungen in die Teilpfadkosten (g) einarbeitet. Wenn ich g mit der Anzahl der genommenen Umdrehungen (t) multipliziere, passieren seltsame Dinge wie: Ein längerer Pfad mit N Kurven nahe dem Ende wird bevorzugt über einen kürzeren Pfad mit N Kurven nahe dem Anfang.

Eine andere, weniger optimale Lösung, die ich in Betracht ziehe, ist: Nach der Berechnung des kürzesten Pfads könnte ich eine zweite A * Iteration (mit einer anderen Pfadkostenformel) ausführen, diesmal begrenzt im x/y-Bereich des kürzesten Pfades und gib den Pfad mit den wenigsten Windungen zurück. Irgendwelche anderen Ideen?

Answer 1

Der aktuelle "Status" der Suche wird eigentlich durch zwei Dinge dargestellt: Der Knoten, in dem Sie sich befinden, und die Richtung, in die Sie blicken. Sie möchten jeden dieser Zustände in verschiedene Knoten aufteilen.

Also, für jeden Knoten im Ausgangsdiagramm, teilen Sie es in E separate Knoten, wobei E ist die Anzahl der eingehenden Kanten. Jeder dieser neuen Knoten repräsentiert den alten Knoten, jedoch in verschiedene Richtungen zeigend. Die Ausgangskanten dieser neuen Knoten sind alle dieselben wie die alten Ausgangskanten, jedoch mit einem anderen Gewicht. Wenn das alte Gewicht w war, dann ...

• Wenn die Kante nicht eine Wende darstellen, machen das neue Gewicht w auch
• Wenn die Kante nicht eine Wende darstellen, machen das neue Gewicht w + ε, wobei ε eine Nummer deutlich kleiner als das kleinste Gewicht ist.

Dann tun Sie einfach eine normale A * Suche. Da keine der Gewichtungen abgenommen hat, ist Ihre Heuristik immer noch admissible, so dass Sie immer noch dieselbe Heuristik verwenden können.

Answer 2

Wenn Sie wirklich die Anzahl der Umdrehungen minimieren möchten (im Gegensatz zu einem guten Kompromiss zwischen Umdrehungen und Pfadlänge), transformieren Sie Ihren Problembereich, indem Sie für jedes Knotenpaar, das durch eine unversperrte Gerade verbunden ist, eine Kante hinzufügen ; Dies sind die Paare, zwischen denen Sie ohne eine Wendung reisen können. Es gibt O (n) solche Kanten pro Knoten, so dass der neue Graph in Bezug auf Kanten O (n) ist. Das macht A * -Lösungen so viel wie O (n) in Bezug auf die Zeit.

Manhattan Entfernung könnte eine gute Heuristik für A * sein.