Spisu treści:
Definicja - Co oznacza wspinaczka górska?
Wspinaczka pod górę to heurystyczna metoda optymalizacji matematycznej stosowana do rozwiązywania trudnych obliczeniowo problemów, które mają wiele rozwiązań. Jest to metoda iteracyjna należąca do lokalnej rodziny wyszukiwania, która rozpoczyna się od rozwiązania losowego, a następnie iteracyjnie ulepsza to rozwiązanie po jednym elemencie, aż dojdzie do mniej lub bardziej zoptymalizowanego rozwiązania.
Techopedia wyjaśnia Hill Climbing
Wspinaczka pod górę jest techniką optymalizacji stosowaną w celu znalezienia „lokalnego optymalnego” rozwiązania problemu obliczeniowego. Zaczyna się od rozwiązania, które jest bardzo słabe w porównaniu do rozwiązania optymalnego, a następnie iteracyjnie się poprawia. Robi to poprzez generowanie „sąsiednich” rozwiązań, które są stosunkowo o krok lepsze niż obecne rozwiązanie, wybiera najlepsze, a następnie powtarza proces, aż dojdzie do najbardziej optymalnego rozwiązania, ponieważ nie może już znaleźć żadnych ulepszeń.
Warianty:
- Prosty - wybierany jest pierwszy najbliższy znaleziony węzeł lub rozwiązanie.
- Największe wzniesienie - rozważane są wszystkie dostępne rozwiązania następcze, a następnie wybierane jest najbliższe.
- Stochastyczny - sąsiednie rozwiązanie jest wybierane losowo, a następnie decyduje się, czy przejść do tego rozwiązania na podstawie stopnia poprawy w stosunku do bieżącego węzła.
Wspinaczka jest wykonywana iteracyjnie - przechodzi całą procedurę, a ostateczne rozwiązanie jest przechowywane. Jeśli inna iteracja znajdzie lepsze rozwiązanie końcowe, zapisane rozwiązanie lub stan zostanie zastąpione. Nazywa się to również wspinaniem na strzelbę, ponieważ po prostu wypróbowuje różne ścieżki, aż trafi na najlepszą, tak jak strzelba jest niedokładna, ale wciąż może trafić w cel ze względu na szeroki rozrzut pocisków. W wielu przypadkach działa to bardzo dobrze, ponieważ okazuje się, że lepiej jest wydawać zasoby procesora na badanie różnych ścieżek niż staranną optymalizację od stanu początkowego.
