Dlaczego komiwojażera ?
Komiwojażer ma do odwiedzenia pewna liczbę miast. Chciałby dotrzeć do każdego z nich i wrócić do miasta, z którego wyruszył. Znamy odległości między tymi miastami. Problemem, który chcemy rozwiązać jest sposób w jaki komiwojażer powinien zaplanować trasę podróży, aby w sumie przebył możliwie najkrótszą drogę.
Przez odległość miedzy miastami będziemy rozumieć odległość w kilometrach (choć mógłby to być np. czas trwania podróży miedzy tymi miastami albo jej koszt - na przykład cena biletu lotniczego).
Problem zaimplementujemy w języku Java. Proszę pobrać szablon programu, dostępnego w zakładce pliki, u dołu strony.
Proszę rozpakować archiwum TSP.students.zip na pulpicie.
Gdy przy próbie uruchomienia środowiska Eclipse - pojawi się błąd mówiący o braku wersji uruchomieniowej Javy (JRE). Proszę ją pobrać z http://www.java.com/pl/download/manual.jsp
Przydatne linki:
Thinking in Java - bardzo dobry, w sumie najlepszy podręcznik programowania w języku Java - do ściągniecia za darmo
Pliki do pobrania
- TSP.students.zip - plik z kodem do uzupełnienia na zajęciach
- TSP.all.zip - plik uzupełniony o kod pisany na zajęciach
- Środowisko uruchomieniowe Java
- Środowisko programistyczne Eclipse
Przykłady systemów obrazujących algorytmy optymalizacji
- Proszę przeprowadzić proces odnajdywania optymalnego rozwiązania i zapoznać się z różnymi algorytmami optymalizacji poznanymi na wykładzie, przy pomocy programu OptiVis. Proszę zapoznać się z różnymi dostępnymi w katalogu programu gotowymi funkcjami. http://www.alife.pl/opt/p/index.html
- Wizualizacja róznych algorytmów rozwiązania problemu komiwojażera - http://www.alife.pl/opt/p/tsp
- Algorytm kolonii mrówek w problemie komiwojażera - http://www.alife.pl/opt/p/aa
- Proszę zapoznać się z różnymi algorytmami rozwiązania problemu komiwojażera - TSP (Travelling salesman problem - opis w treści zajęć ) oraz sposobu w jaki można modyfikować ich działanie przy pomocy parametrów (proszę znaleźć odpowiedź na pytanie: na co wpływają parametry)