AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein C# Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)
Thema durchsuchen
Ansicht
Themen-Optionen

Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

Ein Thema von Matze · begonnen am 3. Jun 2014 · letzter Beitrag vom 4. Jun 2014
Antwort Antwort
Seite 1 von 2  1 2      
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#1

Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 3. Jun 2014, 19:09
Hallo zusammen,

ich habe einen Fahrplan, durch den definiert ist, wo welche Teile in einer Produktion bearbeitet werden dürfen. Dafür werden Quell- und Zielstationen sowie eine Bedingung (nur Gutteile, nur Schlechtteile, ...) festgelegt.

Das sieht z.B. so aus (schematisch dargestellt):
Code:
class FahrplanEintrag
{
    int QuellStation; // -1 = Keine Vorgeschichte, d.h. ZielStation = Start-Station
    int ZielStation;
    int Bedingung;
}

List<FahrplanEintrag> Fahrplan = new List<FahrplanEintrag>()
{
    new FahrplanEintrag()
    {
        QuellStation = -1,
        ZielStation = 1,
        Bedingung = 0, // alle Teile
    },
    new FahrplanEintrag()
    {
        QuellStation = 1,
        ZielStation = 2,
        Bedingung = 1, // nur Gutteile
    },
    new FahrplanEintrag()
    {
        QuellStation = 1,
        ZielStation = 1,
        Bedingung = 2, // nur Schlechtteile (erneute Bearbeitung in Station 1 zulässig)
    },
    new FahrplanEintrag()
    {
        QuellStation = 2,
        ZielStation = 3,
        Bedingung = 1, // nur Gutteile
    },
    // ...
}
Das bedeutet für obiges Beispiel:

In der ZielStation 1 darf jedes Teil bearbeitet werden, das zuvor an keiner Station bearbeitet wurde oder in Station 1 war und schlecht bearbeitet wurde. Es beginnt also mit Station 1.
In Station 2 dürfen alle Teile bearbeitet werden, die zuvor in Station 1 waren und dort gut bearbeitet wurden. Waren die Teile in Station 2 gut, dürfen sie in Station 3 bearbeitet weerden.

Es kann mehrere Start-Stationen geben und mehrere Zielstationen.

Ein Teil dürfte auch z.B. wie folgt durchlaufen:
Code:
1 -> 2 -> 3 -> 4 -> 5 -> 6
      |               |
      |-> 7 ----------|
Das Teil darf also von Station 2 in Station 3 oder in Station 7 kommen.
Von 3 darf es nur in 4 und dann in 5 und dann in 6.
Geht das Teil von 2 nach 7, darf es von 7 nur in 6 weiterbearbeitet werden.

Es kann auch Fälle geben, in denen ein Teil, das in 6 schlecht wurde, wieder zurück nach 2 muss o.ä.

Es gibt also beliebige Verzweigungen und Zusammenführungen.

Anhand der obigen Definitionsliste (List<...>), in der die Einträge beliebig angeordnet sind, möchte ich nun alle möglichen Wege eines Teils bekommen.
Entweder mit einem Baum oder irgendwie anders. So, dass ich das auch visualisieren könnte.

Wie kann ich das denn machen?

Eine Start-Station ist für mich eine, in der die Quell-Station = -1 ist. D.h. damit muss ich vermutlich irgendwie beginnen (wie gesagt, es kann auch mehrere Start-Stationen geben).

Ich dachte evtl. an eine Struktur in der Art, aber vielleicht geht es auch schöner:
Code:
class EinzelneStation
{
    int AktuelleStation; // "Knoten" mit der Station, in der sich das Teil geared befindet
    List<EinzelneStation> NaechsteStationen; // Liste von "Knoten", zu denen das aktuelle Teil als nächstes darf
    List<int> RuecksprungStation; // im Falle, dass das Teil wieder zurück an vorige Stationen darf, steht hier die Nr., damit es keine "Endlosschleife" gibt
    int BedingungFuerBearbeitungsfreigabe;
}

List<EinzelStation> AlleMoeglichenWege
Evtl. mit Rekursion beginnend bei den Start-Staionen (Abbruchbedingungen sind: Rücksprung zu einer vorigen Station bzw. End-Station erreicht).

Ergebnis soll (wie auch immer) etwas in der Art sein, das mir alle möglichen Wege aufzeigt:
Code:
1 (Rücksprung: 1, Bedingung: Wenn Schlechtteil in 1)
2 (Bedingung: nur Gutteil)
3 (Bedingung: nur Gutteil)

ODER

1 (Rücksprung: 1, Bedingung: Wenn Schlechtteil in 1)
2 (Bedingung: nur Gutteil)
4 (Bedingung: nur Schlechtteil)

ODER

...
Konntet ihr's halbwegs nachvollziehen?

Ich möchte aus der Fahrplandefinition ermitteln, welche möglichen Wege ein Teil nehmen kann (mit den entsprechenden Bedingungen).

Grüße
Matze

Geändert von Matze ( 3. Jun 2014 um 19:11 Uhr)
  Mit Zitat antworten Zitat
Perlsau
(Gast)

n/a Beiträge
 
#2

AW: Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 3. Jun 2014, 19:24
Ob man das mit einer gewöhnlichen Baumstruktur (TTreeView) überhaupt darstellen kann? Sieht eher nach Ablaufplan aus ...
  Mit Zitat antworten Zitat
jobo

Registriert seit: 29. Nov 2010
3.072 Beiträge
 
Delphi 2010 Enterprise
 
#3

AW: Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 3. Jun 2014, 19:47
Da hat Perlsau glaub ich Recht.
Du hast ja schon einen Baum gezeichnet, der keiner ist.

Wozu dient das? Optische "Validierung" der Pläne?
Es gibt eine dll, graphwiz oder so, die ist glaub ich frei verfügbar und kann sowas wahrscheinlich malen. Ich hab die mal vor langer Zeit ausprobiert. Bin mir nicht sicher, aber die verarbeitet auch unterschiedliche Eingabeformate.
Gruß, Jo
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#4

AW: Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 3. Jun 2014, 19:49
Stopp!
Mir geht's NICHT um die Visualisierung. Vielleicht habe ich mich falsch ausgedrückt.
Ich möchte das nur in einer internen Struktur haben, die ich ausgeben KÖNNTE, aber mir geht's hauptsächlich darum, dass die Software intern "weiß", welche möglichen Wege es gibt ohne Visualisierung.
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#5

AW: Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 3. Jun 2014, 22:42
Stopp!
Mir geht's NICHT um die Visualisierung. Vielleicht habe ich mich falsch ausgedrückt.
Ich möchte das nur in einer internen Struktur haben, die ich ausgeben KÖNNTE, aber mir geht's hauptsächlich darum, dass die Software intern "weiß", welche möglichen Wege es gibt ohne Visualisierung.
Aber die interne Struktur hast du doch bereits mit deiner „schematischen Darstellung“. Du hast eine Liste von Knoten und eine Liste von Kanten, dadurch ist der Graph vollständig definiert.

Was willst du durch die Darstellung dem Nutzer denn erleichtern? Welche Fehlerquellen sollen z.B. aufgedeckt werden? Davon würde ich dann abhängig machen, wie die Darstellung aussehen soll. Und davon ist wiederum abhängig, welche interne Darstellungsform am besten geeignet ist.

Wie bereits gesagt wurde, gibt es exponenziell viele Pfade, mit Kreisen sogar unendlich viele. Da bringt es wohl wenig, einfach alle theoretisch möglichen Pfade bruteforce-mäßig auszugeben.

Die Glaskugel sagt, dass eine Wegematrix vielleicht das sein könnte, was du suchst. Die gibt an, welche Knoten von einem bestimmten Knoten aus direkt oder indirekt (über beliebig viele Sprünge) erreichbar sind.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#6

AW: Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 4. Jun 2014, 00:27
Letztendlich ist halt wirklich die Frage, was du damit machen willst.

Wenn die Anzahl der Stationen klein ist oder die Eigenschaften der Verknüpfung günstig, dann macht es vielleicht wirklich Sinn, alle Pfade auszugeben. Bei mehr als ein paar dutzend Pfaden würde ich das aber bezweifeln.

Du könntest anstelle einzelnen Pfade auch einen Prefixbaum ausgeben, das würde die Sache dann deutlich übersichtlicher machen, in extremen Fällen würde es nicht helfen.

Es folgt: Werbung für theoretischere Informatik in der Industrie

Wenn du ein schönen Model suchst, um Abläufe mit komplexe Abhängigkeiten zu untersuchen, sind vielleicht Petri-Netze was für dich.
Je nach Ziel könntest du dich mit temporaler Logik auseinandersetzen, was Fragen erlaubt, die wie folgt aussehen: Kann es ein Werkstück geben, das Station 1 erreicht, nachdem es Station 2 in schlechter Qualität verlassen hat.
Bei kleineren Problem könnte man auch mit naiv implementierte Model-Checkern Spaß haben; für größere Probleme schadet etwas Rechenpower und eine clevere Implementierung nicht.

Geändert von BUG ( 4. Jun 2014 um 00:32 Uhr)
  Mit Zitat antworten Zitat
jobo

Registriert seit: 29. Nov 2010
3.072 Beiträge
 
Delphi 2010 Enterprise
 
#7

AW: Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 4. Jun 2014, 07:54
Stopp!
..aber mir geht's hauptsächlich darum, dass die Software intern "weiß", welche möglichen Wege es gibt ohne Visualisierung.
Äh, das weiß sie doch schon! Oder ist Deine Fahrplandarstellung nicht Bestandteil des Programmes?
Eine Liste von Start und Zielstationen, damit kann man sehr einfach feststellen, wo es von einem gegebenen Standpunkt hin gehen kann.

Ein Weg dagegen dürfte erstmal sehr uninteressant sein, da es einer Software selbst egal ist, wie der Weg sein könnte (erst Recht unter dynamischen Bedingungen)
Wenn es nicht um Visualisierung geht und auch nicht um Validierung: (mögliche) Wege werden doch erst spannend, wenn es um Optimierungen geht, Umwege, Teilebestandsprüfung, Vorbestellung usw.
Gruß, Jo
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#8

AW: Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 4. Jun 2014, 08:05
Kann es sein, dass es hier einen logischen Fehler gibt?
Code:
class FahrplanEintrag
{
    int QuellStation; // -1 = Keine Vorgeschichte, d.h. ZielStation = Start-Station
    int ZielStation;
    int Bedingung;
}

List<FahrplanEintrag> Fahrplan = new List<FahrplanEintrag>()
{
    new FahrplanEintrag() // Station 1 ???
    {
        QuellStation = -1,
        ZielStation = 1, // schon ein Ring !!!
        Bedingung = 0, // alle Teile
    },
    new FahrplanEintrag() // Station 2 ???
    {
        QuellStation = 1,
        ZielStation = 2, // wieder auf sich selber !!!
        Bedingung = 1, // nur Gutteile
    },
    new FahrplanEintrag() // Station 3 ???
    {
        QuellStation = 1,
        ZielStation = 1,
        Bedingung = 2, // nur Schlechtteile (erneute Bearbeitung in Station 1 zulässig)
    },
    new FahrplanEintrag() // Station 4 ???
    {
        QuellStation = 2,
        ZielStation = 3,
        Bedingung = 1, // nur Gutteile
    },
    // ...
}
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#9

AW: Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 3. Jun 2014, 19:35
Es kann auch Fälle geben, in denen ein Teil, das in 6 schlecht wurde, wieder zurück nach 2 muss o.ä.
Wenn du Kreise drin hast, gibt natürlich ein Problem, wenn du alle Pfade ausgeben möchtest

Im Prinzip ist dein Plan ein nicht deterministischer Zustandsautomat, wobei das Tupel (Quell-Station, Teil-Art) der Zustand ist. Die Fahrplan-Einträge fügen dann eine (Gutteil/Schlechtteil) oder zwei Transitionen (alle Teile) hinzu.
Dieser Automat erkennt dann alle möglichen Wege für ein Teil.
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#10

AW: Baumstruktur aus Daten erzeugen: Eine Herausforderung! ;-)

  Alt 3. Jun 2014, 19:40
Danke für die Antworten.

Wenn du Kreise drin hast, gibt natürlich ein Problem, wenn du alle Pfade ausgeben möchtest
Hehe jupp. Daher genügt mir hier die Angabe "Rücksprung nach Station x möglich", sodass keine "Kreise"/"Endlosschleifen" entstehen.

Im Prinzip ist dein Plan ein nicht deterministischer Zustandsautomat, wobei das Tupel (Quell-Station, Teil-Art) der Zustand ist.
Stimmt, laut Wikipedia ist es das, was hier vorliegt.
Hättest du mir dafür ein konkretes Programmierbeispiel für meinen Anwendungsfall?

@Perlsau: Ich brauche keinen TreeView dafür. Ich möchte eine Struktur haben, mit der ich das z.B. als Text o.ä. ausgeben kann. Jupp, so eine Art Ablaufplan wäre das, rein grafisch betrachtet. Mir geht's jedoch erstmal darum, dass ich in der Software die möglichen Wege kenne ohne das zu Visualisieren.

Geändert von Matze ( 3. Jun 2014 um 19:44 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 21:03 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz