Algorithmus zur Wegfindung



  • Also, ich hab mal ne Frage bezüglich eines (mir nicht bekannten) Algorithmus an euch.

    Folgendes Problem:
    Wer sich etwas mit organischer Chemie auskennt, weiß, wie schwierig es ist, die Nomenklatur der IUPAC richtig anzuwenden und die längste C-Kette herauszufinden. Deswegen wollte ich mir ein Programm schreiben, was mir dies vereinfacht und noch weitere Funktionen hat.
    Nun stellt sich das Problem, die längste C-Kette zu finden. Dazu habe ich folgenden Ansatz:
    - finde alle CH3-Gruppen (Mögliche Ausgansgspunkte der längsten Kette)
    - suche zwischen allen einen Weg
    - der längste Weg ist die Hauptkette
    Dies ist ein vergleichbares Problem mit der Routenplanung - beim Schritt des Wegsuchens ist der kürzeste Weg erforderlich.
    Die Struktur meines Moleküls sieht intern so aus: Es gibt Boxen, in denen die Atome sind und Verbindungen, in denen zwei Pointer auf je eine Box sind.
    Nun bräuchte ich einen Algorithmus, der den kürzesten Weg zwischen zwei gegebenen Pointern auf je eine Box sucht.

    Ich hoffe, dass es für alle (auch die sich nicht mit Chemie auskennen!) mein Problem verständlich ist und mir einer helfen kann.

    Danke.



  • Wikipedia schrieb:

    Mit Ameisenalgorithmen lassen sich vor allem kombinatorische Optimierungsprobleme lösen, z.B. für Projektplanungsprobleme oder das Quadratische Zuordnungsproblem, doch auch andere Aufgaben können damit angegangen werden. Wichtig ist, daß zwar Annäherungen an ein mögliches Optimum gefunden werden, allerdings nicht zwingend ein optimaler Wert.

    Ich hab jetzt nochmal recherchiert. Was haltet ihr vom "Ameisenalgorithmus". Ich finde, dass hört sich eigentlich gut an. Das einzige Problem ist: ich kann keine Annäherung an das Optimum gebrauchen, ich benötige das Optimum.



  • Servus,

    google mal nach "Warshall-Algorithmus, Floyd-Algorithmus, Algorithmus von Prim und Dijkstra-Algorithmus"... ist bestimmt was für Dich dabei 😉

    Gruss Winn





  • Danke schonmal, ich werde mich damit beschäftigen. Den Dijkstra hatte ich schon mal gesehen, aber nicht weiter beachtet. Aber ich denke, da ist was für mich dabei.



  • Also, ich denke, Warshall-Floyd, Prim und Djikstra sind hier nicht zu gebrauchen. Man sucht hier schließlich einfach den Durchmesser eines Baums und der lässt sich in linearer Laufzeit wie folgt bestimmen:

    Vertices sind im nachfolgenden Algorithmus CH2- oder CH3-Gruppen.

    starte an einem beliebigen Vertex v
    v.marked = true
    längsterWeg = 0
    endKnoten = v
    
    for each Adjazenzvertex a von v
        if length(a) > längsterWeg then
            längsterWeg = length(a)
            endKnoten = Endknoten des Weges von a
    
    v.marked = false
    return length(endKnoten)
    
    Funktion length(v):
    längsterWeg = 0
    v.marked = true
    
    for each Adjazenzvertex a von v
        if not a.marked then
            if length(a) > längsterWeg then
                längsterWeg = length(a)
    
    v.marked = false
    return längsterWeg + 1
    

    Sorry für diese komische Art von Pseudocode, der stammt direkt aus einem Info-Übungszettel.

    Das ergibt nun die Länge aber man kann (implementierungstechnisch sowieso besser) 'length' ein 'pair' zurückgeben lassen, das die Länge und den Endvertex enthält, dadurch erhält man die Anfangsgruppe der längsten C-Kette.



  • Danke schon mal für die Antwort. Aber ich habe noch einige Fragen zu deinem Posting.

    Konrad Rudolph schrieb:

    Vertices sind im nachfolgenden Algorithmus CH2- oder CH3-Gruppen.

    Das Problem hierbei ist, dass meine Datenstruktur wie folgt aufgebaut ist (Pseudocode):

    • Bindung

    • Atom* a

    • Atom* b

    • Anzahl (Einfachbdg., Zweifachbdg., Dreifachbdg.)

    • Atom

    • Element elem

    • Element

    Ich suche daraus jeweils die Atome, die selbst in vier Bindungen eingetragen sind, von denen wiederum jeweils 3 H und 1 C als Partner sind. D. h. wiederum, ich müsste mich theoretisch durch das Molekül "durchhangeln".

    starte an einem beliebigen Vertex v
    v.marked = true
    längsterWeg = 0
    endKnoten = v
    
    for each [b]Adjazenzvertex[/b] a von v
        if length(a) > längsterWeg then
            längsterWeg = length(a)
            endKnoten = Endknoten des Weges von a
    
    v.marked = false
    return length(endKnoten)
    

    Was sind Adjazenzvertices?

    Funktion length(v):
    längsterWeg = 0
    v.marked = true
    
    for each Adjazenzvertex a von v
        if not a.marked then
            if [b]length[/b](a) > längsterWeg then
                längsterWeg = [b]length[/b](a)
    
    v.marked = false
    return längsterWeg + 1
    

    Ist es Absicht, dass diese Funktion rekursiv ist?

    Das ergibt nun die Länge aber man kann (implementierungstechnisch sowieso besser) 'length' ein 'pair' zurückgeben lassen, das die Länge und den Endvertex enthält, dadurch erhält man die Anfangsgruppe der längsten C-Kette.

    Könntest du das noch mal erklären? Das verstehe ich nicht so ganz.

    Sorry dass ich so viel frage, ich bin absoluter Neuling auf diesem Gebiet!



  • Lars Hupel schrieb:

    Das Problem hierbei ist, dass meine Datenstruktur wie folgt aufgebaut ist (Pseudocode):

    Sorry, aber dieser Pseudocode sagt mir irgendwie überhaupt nichts. Wäre es vielleicht möglich (wenn relevant!), diesen als richtigen Code zu posten?

    Ich suche daraus jeweils die Atome, die selbst in vier Bindungen eingetragen sind, von denen wiederum jeweils 3 H und 1 C als Partner sind. D. h. wiederum, ich müsste mich theoretisch durch das Molekül "durchhangeln".

    Na ja, das sollte ja kein Problem darstellen.

    Was sind Adjazenzvertices?

    Alle Vertices, auf die es von v aus eine Kante gibt.

    Ist es Absicht, dass diese Funktion rekursiv ist?

    Ja, natürlich.

    Das ergibt nun die Länge aber man kann (implementierungstechnisch sowieso besser) 'length' ein 'pair' zurückgeben lassen, das die Länge und den Endvertex enthält, dadurch erhält man die Anfangsgruppe der längsten C-Kette.

    Könntest du das noch mal erklären? Das verstehe ich nicht so ganz.

    Ich meine, dass Du length so implementieren solltest, dass es ein 'std::pair<vertex*, int>' zurückgibt, so dass man gleichzeitig die Länge und den Vertex zurückgeben kann, an dem der längste Weg startet.



  • Also, hier ist der Code ("Box" steht hierbei für "Atom"):

    class Element;
    class Box;
    class Bindung;
    
    class Element
    {
      public:
        String Bezeichnung;
        int wertigkeit;
        int radius;
        TColor Farbe;
    
        Element()
        {
        };
    
        Element(String bez,int wert,int r,TColor farb)
        {
          Bezeichnung = bez;
          wertigkeit = wert;
          radius = r;
          Farbe = farb;
        };
    
        bool operator==(const char* vgl) const
        {
          return (String(vgl)==this->Bezeichnung);
        };
    
        bool operator!=(const char* vgl) const
        {
          return (String(vgl)!=this->Bezeichnung);
        };
    
        String operator + (const String& summand) const
        {
          return (Bezeichnung + summand);
        };
    };
    
    class Bindung
    {
      public:
        Box* a;
        Box* b;
        int anzahl;
        Bindung(Box* ptr1,Box* ptr2,int n)
        {
          anzahl = n;
          a = ptr1;
          b = ptr2;
        };
        Bindung()
        {
        };
    };
    
    class Box
    {
      public:
        Element elem;
        int freieBindungen;
        int xm;
        int ym;
        bool isIn(int x,int y)
        {
          return (x > (xm - elem.radius) && x < (xm + elem.radius) && y > (ym - elem.radius) && y < (ym + elem.radius));
        };
        Box()
        {
        };
        Box(const int x,const int y,const Element& __elem)
        {
          xm = x;
          ym = y;
          elem = __elem;
          freieBindungen = __elem.wertigkeit;
        };
        Box(const int x,const int y,const int frei,const Element& __elem)
        {
          xm = x;
          ym = y;
          elem = __elem;
          freieBindungen = frei;
        };
    };
    

    Anmerkung: Dies ist ein C++Builder-Quelltext und nebenbei auch nicht der Beste! Bitte meinen Code in chemischer und semantischer Hinsicht kritisieren, der wird noch verbessert (bin für jeden Hinweis dankbar!). Habe aber versucht, ihn verständlich und chemisch korrekt zu gestalten!


Log in to reply