A*-Implementation

[KEBA]

Hallo zusammen,

Ich bin gerade dabei eine Lib zu schreiben, die etliche Algorithmen und einige Tools implementieren soll: pyreia. Das ganze steckt noch sehr in den Kinderschuhen, soll heißen: Ich weiß selbst, dass da noch einiges recht schlecht ist.

Ich habe einige Basis-Node-Klassen, die die wichtigsten Eigenschaften eines Nodes implementieren. Node.children ist z. B. ein Dictionary bestehend aus Kindern (keys) und den Kosten ein Kind zu erreichen (values).

Daher hatte ich um den A*-Algorithmus zu implementieren gedacht, dass ich eine Klasse names ANode erstelle, die von Node erbt und dann entsprechende Attribute hat (f, g, h etc). Der Algorithmus lief auch wunderbar, allerdings ist mir aufgefallen, dass ich dann einen konzeptionellen Fehler habe. Was mache ich denn z.B. wenn ich einen weiteren Algorithmus implementiere? Diese erbt dann wieder von Node und alles funktioniert gut. Und wenn ich nun einen Baum habe, auf dem ich mehrere Algorithmen laufen lassen will?

Also dachte ich mir, dass ich A* eben funktional (FP) implementiere. Dazu hab ich heapq etwas angepasst um eine cmp_func übergeben zu können. Dann braucht man an sich keine Klassen mehr dafür.

Zur eigentlichen Frage: Meine derzeitige A*-Implementation ist nicht sonderlich schön. Sie funktioniert zwar, aber ich finde mind. zwei Dinge extrem hässlich:

1. Hier möchte ich den Wert eines Heap-Elements verringen. Weder heapq noch meine Implementation unterstützen aber "decreaseKey". Daher muss ich wohl _siftup manuell ausführen. Das stört mich an sich nicht, aber ich muss das entsprechende Element erst mittels "index" suchen, was recht viel Zeit kosten dürfte. Kann ich das Verringern des Wertes besser implementieren? Habe ich das Konzept der Heaps als Vorrangwarteschlange da irgendwie falsch verstanden?

2. So eine Map ist zwar nicht unbedingt langsam, aber dennoch hässlich. Zwei Dicts zu nutzen ist mehr als hässlich, das geht mit OOP natürlich viel einfacher, aber - wie oben gesagt - von Nodes zu erben ist auch keine gute Idee. Kann ich das da irgendwie schöner machen?

Hoffe ich habe meine Probleme ausführlich und klar genug beschrieben;

Grüße, Keba.

[BlackJack]

@KEBA: Zu den Node-Typen: Du musst den A*-Node ja nicht von `Node` erben lassen es reicht ja wenn ein `ANode` eine Referenz auf einen zugehörigen `Node` kennt, oder Du verpasst den `ANode`\s eine `from_node()`-Methode um aus einem normalen `Node` einen `ANode` zu erstellen. Dann erstellst Du für den Algorithmus einen Graphen aus `ANode`\s aus dem Graphen mit `Node`\s. So kann man dass dann auch mit mehreren Algorithmen machen.

[KEBA]

Hallo,

Du musst den A*-Node ja nicht von `Node` erben lassen es reicht ja wenn ein `ANode` eine Referenz auf einen zugehörigen `Node` kennt,

Stimmt, daran hab ich (zumindest so) nicht gedacht, so werd ich das wohl machen. Danke dafür!

oder Du verpasst den `ANode`\s eine `from_node()`-Methode um aus einem normalen `Node` einen `ANode` zu erstellen.

Hab so das Gefühl, das könnte ineffizient werden und Probleme mit mehreren Algorithmen machen. Die andere Idee gefällt mir besser.

Problem #1 ist allerdings immer noch nicht gelöst...

Grüße, Keba.

//edit: Naja, ich verstehe das ehrlich gesagt so nicht wirklich. Dann muss ich ja für jeden Node einen ANode erstellen; geht zwar recht schnell (über Node.tree krieg ich alle Nodes aus einem Graphen), aber das ist mMn noch unschöner als die dict-Variante, da ich dann auch Nodes bearbeite, die mich gar nicht interesieren.

Implementiere ich dann eine "from_node"-Funktion, die ich nur dann aufrufe, wenns nötig ist, muss ich irgenwie überprüfen, ob es schon ein ANode zu dem Node gibt, lande also wieder bei Dicts. Generelll komm ich immer nur (über Node.children bzw. Anode.node.children) an Node-Instanzen, nie an ANode-Instanzen.

Hab da so das Gefühl ich versteh dich etwas falsch...

[BlackJack]

@KEBA: Ich denke Du hast mich schon richtig verstanden. "Könnte ineffizient werden" würde ich mal hinten anstellen bis sich herausstellt, dass es *wirklich* ineffizient ist. Es ist IMHO erst einmal das einfachste und verständlichste wenn man verschiedene Algorithmen mit jeweils eigenen Daten und Methoden "über" die Knoten "legen" will.

[KEBA]

Hm, nein ich verstehe dich nicht. Soll ich wirklich ein Dict anlegen, welches mir Nodes zu ANodes zuordnet? Das ist doch nicht schöner als die jetzige FP-Implementierung?

Von dem eigentlichem Problem (#1) mal abgesehen...

Grüße, Keba.

[BlackJack]

@KEBA: Nein kein Dictionary was die Nodes zuordnet. Wenn ich einen Graphen mit `Node`\s habe, dann würde ich daraus einen Graphen mit `ANode`\s aufbauen und darauf dann den A* laufen lassen.

[KEBA]

Ah, das hört sich schon sinnvoller an, werd ich mal so implementieren, danke

Grüße, Keba.