Algorithmus zur Wegfindung

picocat

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.

picocat

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.

Winn

Servus,

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

Gruss Winn

Apollon

Oder konsultiere Wikipedia.

http://de.wikipedia.org/wiki/Graphentheorie
http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra

picocat

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.

Konrad Rudolph

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.

picocat

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!

Konrad Rudolph

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.

picocat

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!