Situering
Gegeven een verzameling punten in het Euclidische vlak. Een bitonische tour is een gesloten veelhoek die elk punt uit de verzameling bevat, zodanig dat om het even welke vertikale lijn de veelhoek hoogstens tweemaal doorsnijdt.
Een bitonische tour kan ook gedefinieerd worden als een tour die start in het meest linkse punt en naar het meest rechtse punt gaat, door enkel verder te gaan naar rechts gelegen punten, en dan terugkeert naar het meest linkse punt door enkel verder te gaan naar links gelegen punten. In onderstaande figuur is de tour in (a) geen bitonische tour, en de tour in (b) wel.
Een optimale bitonische tour is een bitonische tour van minimum lengte. Gebruik makend van de techniek van dynamisch programmeren kan een polynomiaal algoritme voor het bepalen van een optimale bitonische tour opgesteld worden.
Opgave
Implementeer een Python functie bitonic_tour die als parameter de naam van een bestand krijgt, waarin elke regel de x- en y-coordinaat van een punt in het vlak bevat, gescheiden een spatie. We nummeren de punten startend vanaf 1. De punten zijn gesorteerd volgens stijgende x-coordinaat. De functie geeft de lengte van een optimale bitonische tour terug, evenals de lijst van nummers van punten die een optimale bitonische tour bepalen (startend met punt 1 en punt 2).
Voorbeeld
In onderstaand voorbeeld veronderstellen we dat het bestand data10_1.txt1 zich in de huidige directory bevindt.
>>> bitonic_tour("data10_1.txt")
(2.9819834995879733, [1, 2, 3, 8, 9, 10, 7, 6, 5, 4, 1])
