Implementierung eines Suchalgorithmus

Question

Ich bin ein Anfänger, der versucht, den A * Suchalgorithmus für die Praxis zu implementieren, und ich frage mich, was der beste Weg ist, darüber zu gehen. Ich habe eine Graphenstruktur (Adjazenzmatrix) erstellt und mein Plan war, das A * auf einen Anfangs- und Zielknoten anzuwenden. Ich erschaffe auch die Heuristik und verbessere sie, während ich weitergehe. Die Frage ist, kann das überhaupt funktionieren? Ich habe mir andere Implementierungen angeschaut und sie haben es mit verschiedenen Datenstrukturen gemacht.

Answer 1

Das hängt davon ab, wie Sie die Adjazenzmatrix implementiert haben.

Ein kritischer Punkt von A * ist das Finden der Nachbarn eines Knotens. Wenn Sie die Matrix als einfaches dichtes Bitfeld implementieren, bei dem Sie eine 1 für benachbarte Knoten und eine 0 für nicht benachbarte Knoten haben, ist diese Suche ziemlich ineffizient, da Sie jeden Knoten überprüfen müssen. Obwohl dies ineffizient ist, hindert Sie das nicht daran, A * zu implementieren.

Wenn Sie eine kompliziertere Implementierung der Adjazenzmatrix haben, z. als spärliche Matrix, mit der Sie die Nachbarn direkt abfragen können, ist dies besser für A * geeignet.