Impressum/Datenschutz
Hohe Performanz
Obwohl das Paket in Mathematica-Code progammiert ist, liefert es dennoch eine sehr gute Performance, da alle Funktionen compiliert wurden und nur solche Mathematica-Features Verwendung finden, die von sich aus bereits performant sind.

So wurde auf Operationen wie das Zufügen von Listenelementen weitgehend verzichtet und bevorzugt Felder konstanter Länge und Indexverzeigerungen verwendet.

Für alle Verfahren wurde der Zusammenhang zwischen Problemgröße und Rechenzeit untersucht und dargestellt. Damit kann im Voraus abgeschätzt werden, welche Rechenzeiten zu erwarten sind und welche Problemgröße mit den Verfahren noch bearbeitet werden kann.

Einige verfügbaren Implementierungen und typische Rechenzeiten in Sekunden der komfortablen Schnittstelle für vollständige Graphen mit 50 und 200 Knoten (40.000 Kanten) sind in der folgenden Tabelle zusammengestellt. Die Zeiten enthalten auch alle automatischen Konsistenzprüfungen und wurden auf einem Pentium 4/1,6 GHz unter Windows 2000 mit Mathematica 5.0 ermittelt.

Algorithmus    50  200
Minimum Spanning Tree    0.453  5.437
Shortest Path    0.532  6.312
Traveling Salesman    0.875  17.203
Chinese Postman    0.640  5.141
Maximum Flow    0.953  28.329
Minimum Cost Flow    0.719  30.734
Bipartite Matching    0.312  4.204
General Matching    0.312  4.500

Die unten stehende Tabelle zeigt die Rechenzeiten in Abhängigeit der Knotenzahl des Dijkstra-Algorithmus zur Suche kürzester Wege in einem Graphen mit nicht-negativen Kanten.

Knoten Rechenzeit [s]
30 0.250
60 0.688
90 1.375
120 2.359
150 3.593
180 5.094
210 6.937
240 9.078
270 11.328
300 13.640
Impressum/Datenschutz • Seite geprüft am 27. Sep. 2005