search

jensharder91 / -Lab-Efficient-Algorithms

0 stars 0 forks source link

Blatt 05 Aufgabe 6 #35

Closed jensharder91 closed 6 years ago

P4nd4b43r commented 6 years ago

Angefangen

P4nd4b43r commented 6 years ago

Hier auch wieder Beispiele klappen... Idee hier ist ein Rekursiver Aufruf, bis das Polygon ein Dreieck oder Viereck ist. Es wird immer die kürzeste Innenkante zum Teilen gewählt.

P4nd4b43r commented 6 years ago

Für die Aufgabe Triangula scheitert der rekursive Ansatz beispielsweise auf folgender Instanz: 8 149.48 138.783 97.391 144.947 30.573 149.288 11.442 141.705 9.95 16.931 13.316 11.007 79.608 4.092 148.428 9.189

Die richtige Antwort sollte lauten "595.599" während der rekursive Ansatz "618.852" liefert. Eine tieferliegende Intuition warum das ganze nicht funktioniert, kann ich aber nicht geben.

P4nd4b43r commented 6 years ago

Dynamische Programmierung klappt