Kombinatoryka - programowanie

Dzisiejsze zajęcia będą składały się z szeregu ćwiczeń dotyczących implementacji w języku Python niektórych zagadnień wiążących się z optymalizacją kombinatoryczną. Waszym zadaniem będzie samodzielna praca nad rozwiązaniem zadań, których celem jest przygotowanie do nadchodzących ćwiczeń z optymalizacji. Ponieważ wyniki pracy z zadań wcześniejszych będą potrzebne do rozwiązywania zadań późniejszych, prosimy o rozwiązywanie zadań po kolei.

Uwaga: przed kolejnymi zajęciami obejrzyj ich opis i przygotuj się do nich.

Do pobrania
Notebook z zadaniami

Zad.1

• Jaki wzór wyraża zależność między liczbą punktów, a liczbą odcinków?
• Stwórz:
  • tablicę nazw wszystkich punktów ("A", "B", …), słownik mapujący nazwę na indeks oraz tablicę współrzędnych punktów
  • metody:
    • zwracającą łączną liczbę punktów
    • zwracającą odległość między dwoma punktami podanymi jako argumenty (np. ("A", "B") -> 4)
• Zaprezentuj wynik działania powyższych funkcji oraz zwizualizuj problem (metoda *display_route()*)

Zad.2

• Odpowiedz na pytania:
  • jakie pojęcie z kombinatoryki pozwala opisać "trasę" łączącą dane punkty w taki sposób, że łączy ona wszystkie punkty i przechodzi przez każdy punkt tylko raz?
  • jaki wzór wyraża zależność między liczbą punktów a liczbą możliwych do zbudowania tras?
• Stwórz klasę służącą do przechowywania informacji o pojedynczej, losowej trasie, zawierającą:
  • metody:
    • metodę tworzącą losową trasę: losowy ciąg liczb (bez powtórzeń) z zakresu od 0 do n-1, gdzie n to liczba punktów
    • metodę podstawiającą za liczby w ciągu liczb punkty w taki sposób, aby na miejscu liczby i, był punkt i-ty z tablicy punktów
    • metodę wyliczającą 'naiwną' (Euklidesowską) długość cyklicznej "trasy" (liczy się też odległość między punktem ostatnim i pierwszym), lub dla chętnych https://pl.wikipedia.org/wiki/Ortodroma
• Zaprezentuj wynik działania powyższych funkcji oraz zwizualizuj trasę (metoda *display_route(route)*)

Zad.3

• Odpowiedz na pytania:
  • ile może powstać tras podobnych do "trasy A", jeśli trasa podobna to taka, która różni się od "trasy A" zamianą dwóch punktów na miejscach (jaki wzór wyraża zależność między liczbą punktów a liczbą tras podobnych do trasy wyjściowej?)
• Rozszerz klasę Route o możliwość przechowywania informacji o trasach podobnych.
• Klasa powinna zawierać:
  • metody:
    • generator zwracający trasy podobne do trasy przechowywanej w obiekcie klasy Route.
• Zaprezentuj wynik działania powyższych funkcji oraz zwizualizuj różnice między trasą oryginalną a podobną (metoda *display_route(route1, route2)*)

Zad. 4 (dla chętnych i do poćwiczenia w domu)

• Stwórz klasę służącą do generowania wszystkich tras (wraz z oceną ich długości). Klasa może zawierać również metody zwracające najkrótszą i najdłuższą trasę.