Algorithmen werden immer im worst-case verglichen, das heisst in Deinem Fall bei 5 Knoten 20 Vergleiche (quelle als letzte in Liste, Ziel als letzes in der Liste der Quelle).
Zudem vergleicht man die Algorithmen mit sehr großen Zahlen, also z.b. 100 Wegpunkte, also 10.000 Wege. Du musst also jedesmal erst 100 Vergleiche für Quelle und dann 99 Vergleiche für das Ziel durchführen (hier nimmt man dann aber auch die 100, weil der eine fällt nicht ins Gewicht).
D.h. Bei Deinem Baum sinds 10.000 Vergleiche. Bei einer Unsortierten Liste wären es, wie Du richtig sagst ebenfalls 10.000 Vergleiche. Du sparst also mit Deinem Baum gegenüber einer unsortierten Liste einen Vergleich, egal wieviele Wegpunkte es sind. Dieser eine wird allerdings ignoriert, sodass beide Verfahren O(n) oder O(m^2) haben (n Wege, m Knoten).
Bei einer Sortierten Liste musst Du aber MAXIMAL x Vergleiche bei 2^x Einträgen durchführen (hab leider jetzt keinen vernünftigen TR da, um lb(10.000) auszurechnen, aber es sind aufgerundet 14). Hier spricht man dann von O(lb(n)) oder O(lb(m^2)) oder 2lb(m).

Würdest Du nun Deinen Baum auch sortieren und mit Binärsuche zugreifen, kämst Du in jeder Ebene auch auf lb(m) (jeweils Quelle und Ziel). Damit wärst Du immernoch nicht besser, als 2lb(m) oder lb(n).

Zu Deiner Vergleichstheorie:
Zunächst mal werden Vergleiche nicht so durchgeführt, wie Du annimmst, sondern durch Subtraktion, wobei dann die Statusbits ausgewertet werden. Ein >= ist also immer genauso schnell wie ein > oder ein =. Auf Prozessorebene kriegt man sozusagen alle drei Ergebnisse gleichzeitig. Divisionen gibts hier auch keine, weil /2 und *2 mit Bitverschiebungen geregelt werden und diese sind mit die schnellsten Assemblerbefehle.
Natürlich ist der Einzelne Schleifendurchlauf bei einer Binärsuche aufwändiger, aber wenn ich dafür einen Bruchteil (der bei größeren zahlen immer kleiner wird) an Schleifendurchläufen brauche rechnet sich das.

Zum Thema Mehraufwand: Die TStringList gibts schon incl. Sortieren und Binärsuche, einen Schlüüsel ermitteln sind einfache Stringverkettungen und den Eintrag kriegste mit oList.Objects[oList.IndexOf(Schlüssel)]. Eine eigene klasse (nein zwei) schreiben ist doch deutlich aufwändiger.


Du siehst also, Du kannst maximal gleichziehen, wenn Du Deinen Baum auch sortierst.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Im Prinzip ist eine Sortierte Liste mit Binärsuche auch ein Baum (sogar ein Binärbaum), allerdings etwas anders im Speicher gehalten.
Ich könnte die Liste

genauso auch so aufschreiben:

Dein 'Baun' hingegen ist im Prinzip eine verschachtelte Liste, da Du ja in jeder Ebene sequentiell die Elemente durchgehst. Du siehst also, nicht nur die Datenstruktur ist wichtig, sondern auch das Zugriffsverfahren.

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Genau das ist noch mein Problem, diesen Ansatz bei dir zu verstehen. Ich brauche bei einer Liste mit 5 Hauptknoten und 4 Subknoten nicht 20 Vergleiche, sondern nur 9 [5+4].

Da ich denke, dass du es durch meine nicht so guten Erklärungen noch nicht so ganz verstanden hast, versuch ich es nochmal.

Ich habe 4 Klassen:

Class 1:

Das ist die Klasse eines Knotenpunktes bzw. Node

Class 2:

Das ist die Klasse, in der der Weg von einer Node zur anderen gespeichert wird.

Class 3

Diese Klasse speichert alle Wege von einem bestimmten [FStartNode] Node zu jedem anderen

Class 4

Diese Klasse speichert alle TLevel_PathNodeTargets

Nun geh ich bei der suche so vor:


Wichtig ist, dass ich bei Zeile 10 bis 15 die Ziele NOCH NICHT BEACHTE. DIE SIND MIR DA NOCH WURSCHT. Ich überspringe sie also

Im Endefekt könnt ich meinem 'Baum' auch so darstellen

_________________
Aktuelles Projekt: Gael - Development Blog
Website: LightBlackSoft.com

OK. Jetzt hab ichs . Du hast also nicht O(n), sondern O(2m) (wieder n=Wege, m=Knoten).
Das wären dann aber bei 100 Knoten immernoch 200 Vergleiche (ja eigentlich 199, aber der eine fällt wie gesagt bei großen Zahlen nicht auf), im Gegensatz zu meinen 14 (worstcase), bzw. 100 im Gegensatz zu meinen 7 (average), bzw. 2 zu 1 (bestcase).

Bei fünf Knoten ist der Unterschied marginal (9 Du, 6 ich), aber bei steigender Knotenzahl steigt Deine Vergleichszahl im Verhältnis 2m, meine im Verhältnis 2lb(m) (eigentlich lb(n), aber lb(n)=lb(m^2)=2lb(m)). Anders ausgedrückt: Bei doppelter Knotenzahl musst Du doppelt soviele Vergleiche durchführen, ich 2 mehr.

Würdest Du anstelle der linearen Suche (Forschleife) auch ein BinarySearch einsetzen (das Du dann auch selber coden müsstest), würde Deine Methode auch mit 2lb(m) steigen (lb(m) Quelle+lb(m) Ziel).

_________________
Manchmal sehen Dinge, die wie Dinge aussehen wollen, mehr wie Dinge aus, als Dinge.
<Esmerelda Wetterwax>
Es kann vorkommen, dass die Nachkommen trotz Abkommen mit ihrem Einkommen nicht auskommen und umkommen.

Ok, jetzt sind wir eindlich einer Meinung. puh .

Jetzt versteh ich auch, wie ich meine noch optimieren kann - und eine BinarySearch ist nicht so schwer zu implementieren. Doch das verschieb ich mal auf etwas später, da 200 vergleiche doch noch machbar seien sollten [größere Levels hab ich noch nicht]. Ich hab jetzt sowieso erstmal meine PathFinding-Routine optimiert. Hatte bisher ein Level mit 80 Nodes und einem Fahrstuhl [also ein Engpass]. Nachdem nach über 11Std noch nicht mal alle Wege von Node 1 berechnet waren, hab ich mir gedacht, dass geht auch schneller. Jetzt braucht er für alle 80 Nodes nur eine Minute. Hatte ein wichtiges Feature vergessen einzubauen bzw. ich hab sie nicht ausreichend eingebaut - die Visited-Liste wurde an einer stelle nicht genutzt. Naja, jetzt gehts erstmal richtig schön flott. [würd sogar real-time funktionieren, da er für einen Node zum anderen weniger als 0.05 sekunden braucht. Es ist zwar nicht wirklich der optimalste Weg, aber fast - und die Bots sollen ja wenigstens etwas menschlich wirken.

Aber jetzt steh ich erstmal vor einem anderen Problem, wobei ihr mir damit wohl eher weniger helfen könnt. Muss den Bots jetzt noch ein paar sachen beibringen, damit sie den Fahrstuhl auch richtig benutzen. Das tun sie zwar bereits, aber es gibt noch Bugs.

Ich danke dir, Sidorion, für deine Gedult

_________________
Aktuelles Projekt: Gael - Development Blog
Website: LightBlackSoft.com