In deze oefening schrijven we een algoritme dat zo efficiënt mogelijk vliegtuigen toekent aan uitgaande vluchten op een vliegveld. Het vraagstuk is tweevoudig:

1. Gegeven een reeks geplande vluchten, is het mogelijk deze uit te voeren met een specifieke collectie beschikbare vliegtuigen?
2. Zo ja, wat is de optimale planning?

Men wil graag zo weinig mogelijk plaatsen leeg laten op de vliegtuigen, vooral voor langeafstandsvluchten.

De kost van een geplande vlucht is gedefinieerd als het aantal lege plaatsen vermenigvuldigd met de gevlogen afstand. We willen de som van deze kost voor alle vluchten minimaliseren, d.w.z.

met \(f_i\) en \(p_i\) respectievelijk de \(i\)-de vlucht en het hiervoor gekozen vliegtuig.

Voor de duidelijkheid vermelden we hier nog enkele (voor de hand liggende) regels:

• Een vliegtuig met capaciteit \(c\) kan niet gebruikt worden voor een vlucht met meer dan \(c\) passagiers.
• Een vliegtuig met bereik \(b\) kan niet gebruikt worden voor een vlucht met afstand groter dan \(b\).
• Elk vliegtuig mag slechts eenmaal gebruikt worden, aangezien alle vluchten tegelijk gepland en vervolgens uitgevoerd worden.

Gevraagd wordt om dit vraagstuk op te lossen met een backtracking algoritme dat alle geldige oplossingen genereert en hiervan de beste teruggeeft, of aangeeft dat de beschikbare vliegtuigen niet volstaan om alle vluchten te plannen. Optioneel kan je dit verder uitwerken tot een branch-and-bound algoritme door begrenzingen toe te voegen.

Opgave

Vluchten en vliegtuigen worden voorgesteld door respectievelijk de klassen Flight en Airplane. Deze zijn voor jullie al ingevuld in de boilerplate hieronder. Een vlucht bestaat uit een aantal passagiers (passengers) en een afstand (distance). Een vliegtuig kan een gegeven aantal passagiers (capacity) vervoeren en heeft een maximum bereik (radius) dat aangeeft hoe ver het vliegtuig kan vliegen met een volledig gevulde tank.

Schrijf een functie shedule(flights, airplanes) die twee lijsten als argumenten meekrijgt. De lijst flights bevat alle vluchten die gepland moeten worden en de lijst airplanes bevat alle beschikbare vliegtuigen. De functie moet een lijst teruggeven met op positie i het vliegtuig dat gebruikt moet worden voor de vlucht op positie i van de flights lijst. Wanneer het onmogelijk is om alle vluchten in te plannen met de beschikbare vliegtuigen moet de funtie None teruggeven.

Voorbeelden

>>> flights = [Flight(10, 200), Flight(10, 300)]
>>> airplanes = [Airplane(20, 300), Airplane(15, 300)]
>>> shedule(flights, airplanes)
[Airplane(20, 300), Airplane(15, 300)]

>>> flights = [Flight(10, 300)]
>>> airplanes = [Airplane(9, 500)]
>>> shedule(flights, airplanes)
None