Komplexe, zubuchbare Leistungen abstrahieren

[Robotiker]

Zitat von nahpets:

Hallo Valle,
So, und jetzt kommt der Teil, für den ihr mich alle für vollkommen bekloppt halten dürft

Eigentlich nicht, es erinnert mich nur etwas an den Nachbau einer Graphdatenbank mit relationalen Mitteln. Auch weil weiter oben eine Darstellung des Problems als Matrix und "Beziehungsgeflecht" erwähnt wurde.

[nahpets]

Hallo Robotiker,

Zitat von Robotiker:

Zitat von nahpets:

Hallo Valle,
So, und jetzt kommt der Teil, für den ihr mich alle für vollkommen bekloppt halten dürft

Eigentlich nicht, es erinnert mich nur etwas an den Nachbau einer Graphdatenbank mit relationalen Mitteln. Auch weil du weiter oben eine Darstellung des Problems als Matrix erwähnst, das wäre dann quasi die Adjazenzmatrixdarstellung der Graphdatenbank.

Doch, ich bin bekloppt (und fühl mich wohl dabei ). Das Wort Adjazenzmatrixdarstellung habe ich ja noch nie gehört. Die Suchmaschine meiner Wahl liefert mir dazu einige Ergebnisse, überwiegend von Seiten, deren Webadressen durchaus wissenschaftlich klingen. Was soll's. Angeklickt, gelesen, nix verstanden. (Ja, schon gut, sollte mir das mal etwas entspannter an einem oder zweidreivier schönen Abenden reinziehen.)
Wenn ich mir die Bilder auf dieser Seite anschaue http://www.imn.htwk-leipzig.de/~medo...ge1/k31t4.html, ja, so stelle ich mir das, was hier abgebildet werden soll, vor. Nicht im Detail so, aber vom Grundsatz schon. Aber damit werden wir hier dann wohl ein bisserl OT.

Das, was auf der Seite oben steht, erläutert eigentlich auch den Vorschlag von Valle, dass das Plugin "gewinnt", dass den niedrigsten Wert zurückgibt, dies entspräche dann der kürzesten Kante. Passt das so inetwa?

Auf der Seite steht auch

Zitat:

Die Implementation des Algorithmus von Kruskal kann aus Programmen zusammengesetzt werden, die wir bereits untersucht haben. Erstens müssen wir die Kanten entsprechend der wachsenden Reihenfolge ihres Gewichts nacheinander betrachten.

Das heißt doch eigentlich, dass Valles Idee diesem entspricht und das Plugin mit dem niedrigsten Rückgabewert das höchste Gewicht hat.

Wäre von selbst nie auf die Idee gekommen, dass man die Lösung der hier anstehenden Aufgabe auch wissenschaftlich betrachten könnte, weil ich befürchte, sie dann nicht mehr zu verstehen und lösen zu können

[Namenloser]

[OT]

Zitat von nahpets:

Hallo Robotiker,

Zitat von Robotiker:

Zitat von nahpets:

Hallo Valle,
So, und jetzt kommt der Teil, für den ihr mich alle für vollkommen bekloppt halten dürft

Eigentlich nicht, es erinnert mich nur etwas an den Nachbau einer Graphdatenbank mit relationalen Mitteln. Auch weil du weiter oben eine Darstellung des Problems als Matrix erwähnst, das wäre dann quasi die Adjazenzmatrixdarstellung der Graphdatenbank.

Doch, ich bin bekloppt (und fühl mich wohl dabei ). Das Wort Adjazenzmatrixdarstellung habe ich ja noch nie gehört. Die Suchmaschine meiner Wahl liefert mir dazu einige Ergebnisse, überwiegend von Seiten, deren Webadressen durchaus wissenschaftlich klingen. Was soll's. Angeklickt, gelesen, nix verstanden. (Ja, schon gut, sollte mir das mal etwas entspannter an einem oder zweidreivier schönen Abenden reinziehen.)

Eine Adjazenzmatrix ist eigentlich was total einfaches. Sagen wir du hast einen Graphen mit den Knoten A,B,C und D. Zwischen zwei Knoten kann es höchstens eine Kante (Verbindung) geben.

Ein möglicher (ungerichteter) Graph wäre z.B. folgender:

Code:

A --- B
 \    |
  \   |
   \  |
    \ |
C --- D

Das kannst du aber auch so darstellen:

Code:

    A B C D
  +--------
A | 0 1 0 1
B | 1 0 0 1
C | 0 0 0 1
D | 1 1 1 0

Eine 1 in der Tabelle bedeutet einfach, es gibt eine Kante zwischen den Knoten, und eine 0 bedeutet, es gibt keine Kante.

Wenn die Kanten gewichtet sind, dann sind zusätzlich zu 0en und 1en halt noch weiterere Werte möglich. Die Zahl gibt dann an, „wie stark“ die Knoten verbunden sind.

[/OT]

[nahpets]

[OT]
Hallo NamenLozer,

das ist mir jetzt noch zu hoch.

Fahren wir mal Eisenbahn.

In Deinem Beispiel seien A, B, C, D irgendwelche Orte mit Bahnhof, ich kann damit also feststellen, von welchem Ort ich zu welchem Ort fahren kann. Also von A komme ich nach B und nach D.

Wenn wir jetzt hergehen und für A, B, C, D weitere Matrizen aufstellen, z. B. für A, E, F, G:

Code:

    A E F G
  +--------
A | 0 0 0 1
E | 0 0 1 0
F | 0 1 0 1
G | 1 0 1 0

Desgleichen noch für B, C, D und weitere Orte, so kann ich mich hier quasi von Matrix zu Matrix hangeln, um letztlich einen Weg von z. B. D nach G zu finden, der hier also über A führt, wo ich aber umsteigen muss.

Wenn ich jetzt die beiden Matrizen zusammenfasse (heißt das so?) käme dann das dabei raus?

Code:

    A B C D E F G
  +--------------
A | 0 1 0 1 0 0 0
B | 1 0 0 1 0 0 0
C | 0 0 0 1 0 0 0
D | 1 1 1 0 0 0 1
E | 0 0 0 0 0 0 0
F | 0 0 0 0 0 0 0
G | 0 0 0 1 0 0 0

Also schaue ich in A stehend wohin ich kann. Das sind B und D. Nun schaue ich für B nach, wohin ich kann, das sind A und D. das passt mir nicht. Jetzt schaue ich für D nach, wohin ich kann, das sind A, B, C und G. Und schon habe ich meine Route

(Da meldet sich im Hintergrund eine Stimme, die mich dran erinnert: Da war mal was mit Matrizenmultiplikation! - gehört das hierhin?)

Ok, ist eigentlich nix anderes, als das, was Valle hier benötigt, um die Bedingungen für Leistungen und die entsprechenden Abhängigkeiten von Buchungszeitraum ... feststellen zu können.

Eigentlich ganz einfach kompliziert oder lieber kompliziert einfach?
Oder die simple Programmiererregel: Zerlege ein Problem solange in kleinere Schritte, bist Du es umsetzen kannst.

Und das scheint mir hier beim Ferienhausbuchungsprojekt das Wesentliche zu sein, danach ist das dann "nur noch" Fleißarbeit.

@Robotiker

Zitat von Robotiker:

Oh, 'tschuldigung, ich wollte nicht mit Fachbegriffen um mich werfen. Ich dachte es wäre unter Programmieren allgemein bekannt, dass man einen Graphen nicht nur mit Kreisen und Pfeilen (Knoten und Kanten) darstellen kann, sondern auch als Tabelle mit einer Zeile und Spalte pro Knoten. Das ist die Adjazenzmatrix.

Da brauchst Du Dich nicht zu entschuldigen, es gibt im großen Netz genug Möglichkeiten zu suchen und (fast) alles an Antworten zu finden. Hat mich jetzt ja auch nur 'ne Minute gekostet. Mit Fachbegriffen stand ich schon immer auf Kriegsfuß, eigentlich habe ich von der Theorie keine Ahnung, baue aber trotzdem (verblüffenderweise) Lösungen zu Problemen, bei denen andere sagen, das geht doch garnicht. Allerdings nur im kaufmännischen Bereich, technische Erfahrungen fehlen mir vollkommen.

Das was mit neo4j gemacht werden kann ist also u. a. die optische Darstellung der Datenbankinhalte a la UML. (?) Das Bild möchte ich für das hier diskutierte Problem gerne mal sehen, um sehen zu können, ob meine Vorstellungen mit der Realität in Einklang zu bringen sind [/OT]

[Robotiker]

Zitat von nahpets:

Das was mit neo4j gemacht werden kann ist also u. a. die optische Darstellung der Datenbankinhalte a la UML.

Nein, das ist kein Grafiktool. Das ist eine Datenbank, aber ohne Tabellen, sondern mit Knoten und Kanten, an denen Eigenschaften hängen.

Man könnte mit den Kanten Beziehungen, wie "ist Zubuchoption von", "enthält", "schliesst aus", "muss kleiner sein als", usw. darstellen. Man muss das nicht in Tabellen modellieren.

Im Prinzip läuft das auf eine ähnliche Lösung hinaus, wie in dem Beitrag von Furtbichler oben, aber mit einer anderen Art von NoSQL-Datenbank und eventuell unter dem Verzicht auf explizit geschriebenen Plugins, die könnte man z.B. mit Graph Rewriting aus der Datenbank ableiten, z.B. so
http://en.wikipedia.org/wiki/GrGen

[nahpets]

@Robotiker

Zitat von Robotiker:

Zitat von nahpets:

Das was mit neo4j gemacht werden kann ist also u. a. die optische Darstellung der Datenbankinhalte a la UML.

Nein, das ist kein Grafiktool. Das ist eine Datenbank, aber ohne Tabellen, sondern mit Knoten und Kanten, an denen Eigenschaften hängen.

So hatte ich das auch nicht aufgefasst, sondern nur eher beim Ergebnis der Darstellung. Gut, da habe ich (noch) keine Ahnung. Muss ich mir mal intensiv anschauen.

Zitat von Robotiker:

Man könnte mit den Kanten Beziehungen, wie "ist Zubuchoption von", "enthält", "schliesst aus", "muss kleiner sein als", usw. darstellen. Man muss das nicht in Tabellen modellieren.

Im Prinzip läuft das auf eine ähnliche Lösung hinaus, wie in dem Beitrag von Furtbichler oben, aber mit einer anderen Art von NoSQL-Datenbank und eventuell unter dem Verzicht auf explizit geschriebenen Plugins, die könnte man z.B. mit Graph Rewriting aus der Datenbank ableiten, z.B. so
http://en.wikipedia.org/wiki/GrGen

Also eigentlich ein vollkommen anderer Weg, um das hier diskutierte Problem lösen zu können.

Bisheriges Fazit aus diesem Thread: Es gibt viele Wege nach Rom und Valle bekommt jetzt das Problem zu entscheiden, welcher Weg der für ihn der Beste ist.

[Robotiker]

Zitat von nahpets:

Bisheriges Fazit aus diesem Thread: Es gibt viele Wege nach Rom und Valle bekommt jetzt das Problem zu entscheiden, welcher Weg der für ihn der Beste ist.

Das wird bei einem solchen Thema zwangsläufig der Fall sein. Und wir haben sicher noch nicht alle Möglichkeiten ausgelotet.

Manchmal ist es aber so, wie oben bei der Graph- und Matrixdarstellung, dass man es mit zwei Seiten einer Medaille zu tun hat. Dann kann es hilfreich sein, auch mal auf die andere Seite zu schauen, sei es auch nur um das Problem besser zu verstehen.

Wenn man z.B. sehr viele n:m Beziehungen einführt (wie "enthält", "schliesst aus" usw.) und die auch noch rekursiv durchsuchen muss, dann sollte man schon mal an eine Speicherung als Graph denken, da kriegt man das dann quasi mit Automatikgetriebe.

[Namenloser]

[OT]

Zitat von nahpets:

Wenn wir jetzt hergehen und für A, B, C, D weitere Matrizen aufstellen, z. B. für A, E, F, G:

Code:

    A E F G
  +--------
A | 0 0 0 1
E | 0 0 1 0
F | 0 1 0 1
G | 1 0 1 0

Desgleichen noch für B, C, D und weitere Orte, so kann ich mich hier quasi von Matrix zu Matrix hangeln, um letztlich einen Weg von z. B. D nach G zu finden, der hier also über A führt, wo ich aber umsteigen muss.

Wenn ich jetzt die beiden Matrizen zusammenfasse (heißt das so?) käme dann das dabei raus?

Code:

    A B C D E F G
  +--------------
A | 0 1 0 1 0 0 0
B | 1 0 0 1 0 0 0
C | 0 0 0 1 0 0 0
D | 1 1 1 0 0 0 1
E | 0 0 0 0 0 0 0
F | 0 0 0 0 0 0 0
G | 0 0 0 1 0 0 0

Also schaue ich in A stehend wohin ich kann. Das sind B und D. Nun schaue ich für B nach, wohin ich kann, das sind A und D. das passt mir nicht. Jetzt schaue ich für D nach, wohin ich kann, das sind A, B, C und G. Und schon habe ich meine Route

(Da meldet sich im Hintergrund eine Stimme, die mich dran erinnert: Da war mal was mit Matrizenmultiplikation! - gehört das hierhin?)[/OT]

Ja, wenn du die Adjazenzmatrix mit sich selbst multiplizierst, dann bekommst du für jeden Knoten die Knoten, die du mit genau 2 Schritten erreichst. Wenn du dann noch mal die Matrix dranmultiplizierst kriegst du die Knoten, die du mit 3 Schritten erreichst usw...

Allerdings macht deine zusammengefasste Matrix irgendwie keinen Sinn. Da steht jetzt z.B. dass du von D nach G gehen kannst, dabei gibt es gar keine Verbindung zwischen D und G. Auf der anderen Seite müsstest du von A nach G kommen, aber da steht bei dir eine 0. Und alle anderen Verbindungen von deiner AEFG-Matrix fehlen irgendwie auch...

Ich kenn es außerdem eigentlich auch nur so, dass es eine Adjazenzmatrix gibt, in der alle Knoten-Kombinationen drin sind, und nicht mehrere Ajazenzmatrizen für Teilgraphen, die erst noch kombiniert werden müssen.

Aber ich verweise jetzt einfach mal auf diese Vorlesungsfolien (oder hier das etwas ausführlichere Skript, ab Seite 101 geht’s los), damit wir nicht noch weiter ins Off-Topic abdriften.

[/OT]

[nahpets]

@NamenLozer
[OT]
Deine Antwort zeigt mir, dass ich da wohl so einiges (ziemlich alles) nicht verstanden habe, aber dafür gibt es neuen Lesestoff, um das zu ändern Und damit genug OT.
[/OT]

[generic]

was nahpets meint lässt sich auch einfacher Ausdrücken.
Bitmap-Index