(1) Die Entfernung hat doch eine Aussagekraft, nur das etwa eine euklidische Distanz selbstverständlich nur eine Approximation ist. Dieser Umstand ist jedoch kein Problem, da die Natur einer jeden Heuristik ja nichts anderes als eine approximative Funktion ist.
Und selbstverständliche sind solche "Schätzfunktionen" nie optimal, sonst wären sie (a) keine Schätzfunktion und (b)
deutlich teurer in ihrer Laufzeit.
(2) Das wird dir nicht helfen. Wird eine Heuristik monoton, so kann sie in die Kostenfunktion integriert werden und damit entspricht eine A*-Suche exakt dem Dijkstra Algorithmus.
(3) Das geht selbstverständlich auch nicht, denn Wände überhaupt als Kosten zu betrachten, ergibt ja nur unter der Prämisse Sinn, dass es durchlässige und undurchlässige Wände geben kann, also zwischen zwei Feldern eine Wand oder eben keine.
Aus diesem Zustand folgt dann direkt, dass die Heuristik sämtliche Wände der Umgebung korrekt betrachten muss, d.h. den Suchraum viel stärker "erkunden"
muss.
Denn würde die Heuristik einfach von
keinen Wänden ausgehen, wäre sie nicht besser als die bisherige Heuristik. Berücksichtigt sie aber Wände, muss sie
genau wissen wie viele und wie stark sie die Kosten beeinflussen, denn ansonsten könnte sie die Kosten überschätzen und wäre damit keine zulässige Heuristik mehr.
Das ist dann der klassische Fall, dass man per Optimierung der Heuristik die Situation verschlimmert, weil man meint die Heuristik müsste so gut wie möglich an die optimale Lösung herankommen, dabei aber mehr Laufzeit opfert, als man unterm Strich gewinnt.
(4) Nein, das UV-Mapping kommt ja aus der Texturierung von Objekten, etwa Polygonen. Es geht hierbei also um die Oberfläche. Natürlich wäre die grundlegende Vorgehensweise prinzipbedingt anpassbar, aber die Problematik entsteht ja durch die UV-Map an sich: bei einer Kugel etwa kann man z.B. an den Polen alle benachbarten Punkte (minimale Distanz zueinander) direkt besuchen, würde in einem Graphen also diese Knoten alle untereinander verbinden. In einer UV-Map ist das nicht möglich, hier könnten in 2D prinzipbedingt maximal 8 Nachbarn existieren, in 3D kannst du aber mehr mögliche Pfade haben.
Deshalb als Graph modellieren, nicht per UV-Map.
ascer schrieb:
Ich glaube dir ermangelt es einfach ganz grundlegend an Grundwissen bzgl. Algorithmik.
Das war übrigens mitnichten angreifend, abwertend oder überhaupt irgendwie negativ gemeint, sondern einfach nur eine Feststellung, die sich mir aufdrängte.
Es wirkt so, als wärst du intuitiv unzufrieden mit approximativen Verfahren. Vielfach gibt es aber in der Algorithmik, also der Informatik, nichts besseres. Die Zeitkomplexität von A* ist im
worst-case ja schon V^2, also polynomiell, also ziemlich fix im Vergleich zu anderen Lösungen.
Die Problematik von A* ist nebenbei gesagt i.d.R. auch nicht die Laufzeit, sondern die Speicherkomplexität, da ja alle bekannten Knoten in der closed und open List gehalten werden müssen.
