ich habe eine Menge von n Elementen A={A1 , ... , An} gegeben und soll einen Algorithmus entwerfen, um die längste Sequenz [Ai1 , ... , Aik] zu finden, sodass Aij in Relation zu Aij+1 steht. Die Relation ist transitiv, ansonsten ist sie zur Lösung der Aufgabe nicht relevant. Einen Algorithmus, um zu testen, ob zwei Elemente in Relation stehen, habe ich aber bereits. Weiterhin wird nicht vorausgesetzt, dass die Sequenz [i1 , ... , ik] streng monoton wachsend ist, d.h. also, dass die gesuchte Sequenz nicht nur durch "Wegstreichen" einiger Elemente aus A entstehen kann. Es ist also auch durchaus sowas wie [A2 , A4 , A1 , ...] erlaubt.
Nun besteht mein Problem darin, einen möglichst effizienten Algorithmus zu finden. Eine naive Methode, die aus ständigen paarweisen Vergleichen besteht, würde sicherlich schnell hochgradig polynomiell werden. Und selbst O(n²) scheint mir für diese Aufgabe zu langsam, da das Testen auf Relation auch noch gewisse Zeit benötigt. Hat jemand vielleicht eine Idee für mich? Hat es vielleicht etwas mit den letzten Vorlesungen zu tun (Kürzeste Wege, Dijkstra, Bellman-Ford, Prioritätswarteschlangen, Union-FInd-Datenstruktur)? Über einen kleinen Tipp würde ich mich sehr freuen.
