Poszukiwanie najkrótszych dróg

Czy każdy problem można traktować jako zadanie znalezienia najlepszego rozwiązania w przestrzeni bardzo wielu rozwiązań? Jest w tym sporo prawdy: poniższy program demonstracyjny służy jakże praktycznemu celowi znalezienia najkrótszej drogi łączącej zadane punkty. Cel ten można osiągać dwojako: albo wymyślać metodę wybierania kolejnych, najkorzystniejszych miast na naszej drodze, albo przeglądać wielkie ilości potencjalnych dróg w poszukiwaniu tej najkrótszej. A ile jest różnych dróg łączących n miast? prawie n silnia, czyli dla 10 miast mamy do sprawdzenia 3628800 dróg, dla 30 miast - 265252859812191058636308480000000 dróg, a dla 50 miast... jeszcze więcej. Jak widać, trudno je wszystkie sprawdzić niezależnie od dostępnej komukolwiek mocy obliczeniowej.

Czy dałoby się do tego zatrudnić proces ewolucyjny? Oczywiście! Wyobraźmy sobie, że każda droga to osobnik. Mutacje osobnika to zmiany drogi. Krzyżowanie osobników to wymiana fragmentów dróg. Genotyp to zapis kolejnych numerów miast. A dopasowanie do środowiska to po prostu długość drogi! (która jest minimalizowana, wystarczy przyjąć odwrotność długości drogi by uzyskać zadanie maksymalizacji). Zbiór dróg stanowi populację. Proste, prawda?

Jak wiemy z wykładów na temat optymalizacji, istnieje dużo więcej metod optymalizacji. Nie trzeba stosować od razu procesu ewolucyjnego. Co więcej - metody optymalizacji są na tyle uniwersalne, że da się je przystosować niemal do każdego problemu poszukiwania najlepszego rozwiązania. Pokazywany tutaj problem komiwojażera jest tylko jednym z niezliczonych przykładów! Sam problem komiwojażera ma wiele uogólnień i praktycznych zastosowań w transporcie i logistyce, realizowanych na przykład przez usługę OptiFacility.

Co pokaże poniższy programik? Klikając myszką dodajesz miasta (prawy przycisk je usuwa). A potem możesz testować różne metody poszukiwania najkrótszej drogi która je łączy. Przycisk "heurystyka" prowadzi drogę według zasady "zawsze idę do najbliższego miasta". Inne przyciski demonstrują inne sposoby poszukiwania najlepszych rozwiązań. Miłych eksperymentów!