Neuberechnung eines Graphen
-
Hallo zusammen, nochmals, folgendes Problem: Ich habe einen zusammenhängenden Graphen mit Knoten und Kanten. Jeder Knoten ist mit einer Zahl markiert. Jetzt möchte ich in mehreren Schritten, die Markierungen für alle Knoten neu berechnen, vielleicht 100 mal. Der neue Wert eines Knoten k ist die Summe der Markierungen, der Knoten, die mit k durch Kanten verbunden sind. Das kann man ohne grössere Probleme in eine Computerprogramm fassen. Nur wenn die Menge der Knoten und Kanten sehr gross ist, gibt es Probleme. Wisst Ihr dafür einen Link für einen effizienten Algorithmus ? Ungerichtete Kanten !
-
@biter wo ist denn das Problem auch bei größeren Mengen von Punkten & Kanten? Du musst dir nur von den Werten eine Kopie machen bzw für jeden Knoten den neuen Wert beim Berechnen erst anderswo speichern. Klingt nicht danach, dass der Aufwand schnell steigen würde bei größeren Graphen.
-
Wenn die Knoten und Kanten nicht mehr in den RAM-Speicher passen, wäre ein effizienter Algorithmus hilfreich. Einer mit nicht zu grossem Speicherbedarf. Auch die Anzahl der Kanten wächst sehr schnell. Wenn ein mittlerer Verzweigungsgrad von 50 oder so vorhanden ist. Dass man die Menge der Knoten in Gruppen zusammenfasst einen kleineren Graph erhält, als vage Idee. Bei einer Weiterberechnung in einem Schritt liegt nicht das Problem, wie Du gesagt hast nur eine Kopie vom Graph.
-
Kannst du vlt mal Source Code posten? Ich kann mir ungefähr vorstellen, was du vorhast, aber nur ungefähr.
Spontan würde ich sagen, dass sehr große Datenmengen kein Problem sein sollten, daher würde ich mutmaßen, dass deine Implementierung nicht optimal ist. Auch daher: Vlt besser mal Code posten.
-
Das würde jetzt zuweit führen, Source-Code habe ich jetzt noch nicht, stell Dir nur einen Graph bildlich vor mit Knoten und Kanten, wobei in jedem Knoten eine Zahl drinsteht. Und dann für jeden Knoten den Wert neuberechnen, das nenne ich einen Schritt. Die Brute-Force Implementierung wäre nicht optimal.
-
@biter sagte in Neuberechnung eines Graphen:
Die Brute-Force Implementierung wäre nicht optimal.
Ach!
-
Weil sie nicht in den Speicher passt !
-
Wahrscheinlich existiert für das Problem keine Lösung !
-
@biter sagte in Neuberechnung eines Graphen:
Weil sie nicht in den Speicher passt !
Wahrscheinlich existiert für das Problem keine Lösung !Wie groß ist denn dein Graph?! Nur mal so von der Größenordnung her.
-
@biter wenn du nur theoretisch überlegst, gib am besten dein Problem auch entsprechend formalisiert an. Dann kann man Speicherplatz und Rechenzeit abhängig der Kanten und Knotenanzahl angeben.
Für gängige Datenstrukturen für Graphen kannst du mal hier gucken: https://en.wikipedia.org/wiki/Adjacency_matrix
und hier: https://en.wikipedia.org/wiki/Adjacency_list je nach dem, was für deinen Graph besser geeignet ist.
-
Muss mich noch korrigieren, es sind doch gerichtete Kanten, und der neue Wert für den Knoten k, wird aus der Summe der Werte von den Knoten g gebildet, für die es eine gerichtete Kante von g nach k gibt. Die Datenstruktur von meinem ( noch nicht fertigen ) Programm ist ein Array der Länge N auf der M < N Zahlen und sonst Nullen angeordnet sind. Und die Anzahl der Knoten, werden von der Anzahl der Möglichkeiten wie man die Zahl N additiv in M Teile zerlegen kann, und alle Zahlen < M bestimmt. Für N = 30 ist es schon über 10^9. Es kommt deshalb nur N = 20 in Betracht. Die Anzahl der Kanten ist ungefähr 10 mal soviel.
-
zum Beispiel N = 6, M = 4: Array der Länge 6: wobei die Reihenfolge immer gleich bleibt.
l
Anzahl der Möglichkeiten ( Länge 4 ) anzuordnen zB ( 0 1 0 2 3 4 ) +
Anzahl der Möglichkeiten ( Länge 3 ) anzuordnen zb ( 0 0 1 0 2 3 ) +
Anzahl der Möglichkeiten ( Länge 2 ) +
Anzahl der Möglichkeiten ( Länge 1) = Anzahl der Knoten.
-
@biter Wenn du z.B. mit eine Adjazensmatrix arbeitest, braucht du für V Knoten, eine Matrix der Größe V². Theoretisch reicht dir pro Knoten 1bit. Das machen bei 10^9 Knoten 125 MB. (Wenn es immer ganzy Byte sind bist du da allerdings schon bei 1 GB). Problematisch wird höchstens der Knotenwert, denn mit 10^9 64 bit Zahlen, bist du halt bei 64 GB, die haben die meisten Workstations nicht. Dann müsste man jeweils die Werte, auf denen man aktuell nicht arbeitet, auf Platte schreiben.
-
@Schlangenmensch sagte in Neuberechnung eines Graphen:
@biter Wenn du z.B. mit eine Adjazensmatrix arbeitest, braucht du für V Knoten, eine Matrix der Größe V². Theoretisch reicht dir pro Knoten 1bit. Das machen bei 10^9 Knoten 125 MB. (Wenn es immer ganzy Byte sind bist du da allerdings schon bei 1 GB).
Ähm. Bei V=10^9 kommt für V²/8 deutlich mehr als 125 MB raus.
Problematisch wird höchstens der Knotenwert, denn mit 10^9 64 bit Zahlen, bist du halt bei 64 GB, die haben die meisten Workstations nicht. Dann müsste man jeweils die Werte, auf denen man aktuell nicht arbeitet, auf Platte schreiben.
Äh. 10^9 ist genau eine Milliarde, d.h. 10^9 * 8 Byte (64 Bit) sind genau 8 GB (knapp unter 8 GiB). Ich denke da hast du dich mit Bit vs. Byte vertan.
-
Die Anzahl der Knoten bei N = 30 müsste 8 * 10^18 sein, nicht zu machen. Dann anstelle von long, decimal 16 Byte. Meine Idee ist das es viele Knoten mit gleichem Wert gibt. Da müsste irgendwas zu machen sein, aber was ?
-
@biter
Also ich denke mit 10^17 Knoten bist du sowieso am A.
Angenommen du brauchst um einen Knoten zu verarbeiten einen Tankzyklus, dann brauchst du bei 3 GHz schon etwa ein Jahr. Für einen Durchlauf, alles im RAM, RAM Zugriffszeiten ignoriert, mehrere Verbindungen pro Knoten ignoriert.IMO kann das nur gehen wenn du das ganze mathematisch lösen kannst. Also du fängst an mit einer Formel für den Wert jedes Kontens am Anfang. Aus dieser bastelst du eine Formel für den Wert jedes Knotens nach der 1. Iteration usw.
Wenn das geht, dann besteht eine Chance.Ansonsten sehe ich eher schwarz.
-
@hustbaer sagte in Neuberechnung eines Graphen:
@Schlangenmensch sagte in Neuberechnung eines Graphen:
@biter Wenn du z.B. mit eine Adjazensmatrix arbeitest, braucht du für V Knoten, eine Matrix der Größe V². Theoretisch reicht dir pro Knoten 1bit. Das machen bei 10^9 Knoten 125 MB. (Wenn es immer ganzy Byte sind bist du da allerdings schon bei 1 GB).
Ähm. Bei V=10^9 kommt für V²/8 deutlich mehr als 125 MB raus.
ähm, ja... da ist mir irgendwo ein Quadrat verloren gegangen.... ich nehme alles zurück und behaupte das Gegenteil. Allerdings bei ca 100 Kanten pro Knoten, wäre die Matrix aber ziemlich sparse, daher vlt eine andere Datenstruktur besser geeignet.
Problematisch wird höchstens der Knotenwert, denn mit 10^9 64 bit Zahlen, bist du halt bei 64 GB, die haben die meisten Workstations nicht. Dann müsste man jeweils die Werte, auf denen man aktuell nicht arbeitet, auf Platte schreiben.
Äh. 10^9 ist genau eine Milliarde, d.h. 10^9 * 8 Byte (64 Bit) sind genau 8 GB (knapp unter 8 GiB). Ich denke da hast du dich mit Bit vs. Byte vertan.
Joa... da ist mir grade nicht ganz ersichtlich was ich da in meinen Taschenrechner getippt habe, die 64 kommen genau hin, wenn's in Gigabit wäre... wird wohl doch Zeit für die Weihnachtspause, oder zumindest noch einen Kaffee.
-
N = 30 geht deswegen nicht N = 20, M = 10 ist das ungefähr das höchste, die Anzahl der Knoten 10 Millionen
-
Da fällt mir ein, dass es gar keine Adjazens-Matrix braucht, wenn man pro Knoten nur 15 Folgeknoten hat. V=10^9 geht natürlich trotzdem nicht V=10^6 geht 10^6 * 15 * 4 Byte für die Übergangstabelle.
-
Entschuldigung, dass ich das nicht gleich gesagt habe. Mir geht es um effiziente Algorithmen mit weit weniger Speicherplatz. Endliche Automaten kann ,man minimieren. Es kommt wahrscheinlich auch auf die Besonderheiten der Kanten-Berechnungen an, das geht hier aber zu weit. Womöglich kann man die Menge der Knoten zu Gruppen zusammenfassen und so einen kleineren Graph erhalten. Oder es ist noch kein Algorithmus bekannt, dann muss ich es selber studieren. Ein schönes Weihnachtsfest bei bester Gesundheit, Euch allen !!!
