Algorithmus für maximalen Pfad gesucht |
| 28.06.2008, 12:20 | Auf diesen Beitrag antworten » |
| aRo | Algorithmus für maximalen Pfad gesucht Hallo! Vielleicht hat ja jemand mal Lust darüber nachzugrübeln. Also gesucht ist ein Alogrithmus der in einem Baum mit positiv gewichteten Kanten die zwei Knoten sucht, die den maximalen Abstand voneinander haben und sich diesen Abstand auch merkt. Die Laufzeit soll O(|V|) sein (V ist die Menge der Knoten). Der Algorithmus ist zu beschreiben und begründen, muss also nicht unbedingt wirklich in einer Programmiersprache geschrieben werden. Mein bisheriger Ansatz: Wobei ich nicht ganz sicher bin, ob das O(|V|) ist? Was ist eig. der Unterschied zu O(V)? Also, man muss für jeden Knoten seine 2 größten Kinder suchen. Kinder, die nicht eines der zwei größten sind, können mit eventuellem Unterbaum fallen gelassen werden (z.B. aus einer Liste gelöscht werden). Die Werte der zwei größten Kinder und die Namen der Kinder müssen im Vater gespeichert werden. Als Größe eines Knotens bezeichne ich die die maximal 2 Zahlen, die in ihm stehen + die verbindene Kante zum Papa. Blätter haben also den Wert 0, mit ihnen fängt man an und aus ihnen baut man am Anfang eine Liste, aus der gestrichen wird. Am Ende stehen die beiden gesuchten Knoten in der Wurzel und die SUmme der beiden Werte der Wurzel ist der gesuchte Abstand. Ist das verständlich? Was sagt ihr dazu? |
|
|
|
| 04.07.2008, 17:20 | Auf diesen Beitrag antworten » |
| Crotaphytus | Klingt von der Idee her eigentlich schon ganz gut. Zwei Denkanregungen: 1. Du musst die Blätter erst mal kennen. 2. Gesucht ist nicht der Wert des größten Abstands, sondern die Knoten, die diesen besitzen. O(|V|) steht da einfach nur, weil V wie du gesagt hast eine Menge ist. O(V) ist jetzt nicht so wirklich definiert... Stells dir einfach als O(n) mit n = |V| vor. 
|
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
