Neuberechnung eines Graphen
-
@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 !!!
