- Algorytm wspinaczki górskiej to lokalny algorytm wyszukiwania, który w sposób ciągły porusza się w kierunku rosnącej wysokości/wartości, aby znaleźć szczyt góry lub najlepsze rozwiązanie problemu. Kończy się, gdy osiągnie wartość szczytową, w której żaden sąsiad nie ma wyższej wartości.
- Algorytm wspinaczki górskiej jest techniką stosowaną do optymalizacji problemów matematycznych. Jednym z szeroko omawianych przykładów algorytmu wspinaczki górskiej jest Problem komiwojażera, w którym należy zminimalizować drogę przebytą przez sprzedawcę.
- Nazywa się to również zachłannym wyszukiwaniem lokalnym, ponieważ skupia się wyłącznie na dobrym bezpośrednim sąsiedztwie, a nie poza nim.
- Węzeł algorytmu pokonywania wzniesień składa się z dwóch elementów, którymi są stan i wartość.
- Wspinaczka górska jest najczęściej stosowana, gdy dostępna jest dobra heurystyka.
- W tym algorytmie nie musimy utrzymywać i obsługiwać drzewa lub wykresu wyszukiwania, ponieważ zachowuje on tylko jeden bieżący stan.
Cechy wspinaczki górskiej:
Poniżej przedstawiono kilka głównych cech algorytmu wspinaczki górskiej:
Diagram przestrzeni stanów dla wspinaczki górskiej:
Krajobraz przestrzeni stanów jest graficzną reprezentacją algorytmu pokonywania wzniesień, która przedstawia wykres pomiędzy różnymi stanami algorytmu i funkcją celu/kosztem.
Na osi Y przyjęliśmy funkcję, która może być funkcją celu lub funkcją kosztu, oraz przestrzeń stanów na osi x. Jeśli funkcją na osi Y jest koszt, celem poszukiwań jest znalezienie minimum globalnego i minimum lokalnego. Jeśli funkcją osi Y jest funkcja celu, wówczas celem wyszukiwania jest znalezienie maksimum globalnego i maksimum lokalnego.
Różne regiony w krajobrazie przestrzeni stanów:
Lokalne maksimum: Maksimum lokalne to stan lepszy od stanów sąsiednich, ale istnieje też inny stan, który jest od niego wyższy.
Alisa Manyonok
Globalne maksimum: Maksimum globalne to najlepszy możliwy stan krajobrazu przestrzeni stanów. Ma największą wartość funkcji celu.
Stan aktulany: Jest to stan na diagramie krajobrazowym, w którym aktualnie obecny jest agent.
Płaskie maksimum lokalne: Jest to płaska przestrzeń w krajobrazie, w której wszystkie państwa sąsiadujące z obecnymi stanami mają tę samą wartość.
Ramię: Jest to obszar płaskowyżu, który ma podjazdową krawędź.
jak otworzyć plik json
Rodzaje algorytmów wspinaczki górskiej:
- Prosta wspinaczka górska:
- Wspinaczka górska o najbardziej stromym podejściu:
- Wspinaczka stochastyczna:
1. Prosta wspinaczka górska:
Proste wspinanie się po wzniesieniach to najprostszy sposób wdrożenia algorytmu wspinania się po wzniesieniach. Ocenia tylko stan węzła sąsiedniego na raz i wybiera pierwszy, który optymalizuje bieżący koszt i ustawia go jako stan bieżący . Sprawdza tylko, czy jest to jeden stan następczy, a jeśli okaże się lepszy od bieżącego stanu, wówczas przeniesie się w tym samym stanie. Algorytm ten ma następujące cechy:
- Mniej czasochłonne
- Mniej optymalne rozwiązanie i rozwiązanie nie jest gwarantowane
Algorytm prostej wspinaczki górskiej:
- Jeśli jest to stan docelowy, zwróć sukces i wyjdź.
- W przeciwnym razie, jeśli jest lepszy niż bieżący stan, przypisz nowy stan jako stan bieżący.
- W przeciwnym razie, jeśli nie jest lepszy niż stan bieżący, wróć do kroku 2.
2. Wspinaczka na najbardziej strome wzniesienie:
Algorytm najbardziej stromego wznoszenia jest odmianą prostego algorytmu wspinaczki pod górę. Algorytm ten sprawdza wszystkie sąsiednie węzły bieżącego stanu i wybiera jeden węzeł sąsiedni, który jest najbliżej stanu docelowego. Algorytm ten zajmuje więcej czasu podczas wyszukiwania wielu sąsiadów
Algorytm wspinaczki na najbardziej strome wzniesienie:
- Niech SUCC będzie takim stanem, że każdy następca obecnego stanu będzie od niego lepszy.
- Dla każdego operatora mającego zastosowanie do bieżącego stanu:
- Zastosuj nowy operator i wygeneruj nowy stan.
- Oceń nowy stan.
- Jeśli jest to stan docelowy, zwróć go i zakończ, w przeciwnym razie porównaj go z SUCC.
- Jeśli jest lepszy niż SUCC, to ustaw nowy stan na SUCC.
- Jeśli SUCC jest lepszy niż bieżący stan, ustaw bieżący stan na SUCC.
3. Wspinaczka stochastyczna:
Stochastyczna wspinaczka górska nie sprawdza wszystkich sąsiadów przed przejściem. Zamiast tego ten algorytm wyszukiwania wybiera losowo jeden sąsiedni węzeł i decyduje, czy wybrać go jako stan bieżący, czy zbadać inny stan.
Problemy w algorytmie wspinaczki górskiej:
1. Maksimum lokalne: Maksimum lokalne to stan szczytowy w krajobrazie, który jest lepszy niż każdy z sąsiednich stanów, ale występuje również inny stan, który jest wyższy niż lokalne maksimum.
Rozwiązanie: Technika wycofywania się może być rozwiązaniem lokalnego maksimum w krajobrazie przestrzeni stanów. Utwórz listę obiecujących ścieżek, aby algorytm mógł cofnąć się w przestrzeni poszukiwań i zbadać także inne ścieżki.
2. Płaskowyż: Plateau to płaski obszar przestrzeni poszukiwań, w którym wszystkie sąsiednie stany bieżącego stanu zawierają tę samą wartość, ponieważ algorytm ten nie znajduje najlepszego kierunku ruchu. Poszukiwania związane ze wspinaczką górską mogą zaginąć na obszarze płaskowyżu.
Rozwiązanie: Rozwiązaniem problemu plateau jest podjęcie dużych lub bardzo małych kroków podczas poszukiwań, aby rozwiązać problem. Wybierz losowo stan, który jest daleko od stanu bieżącego, tak aby algorytm mógł znaleźć obszar inny niż plateau.
program powitalny Java
3. Grzbiety: Grzbiet jest specjalną formą lokalnego maksimum. Ma obszar wyższy niż otaczające go obszary, ale sam ma nachylenie i nie można do niego dotrzeć jednym ruchem.
Rozwiązanie: Stosując wyszukiwanie dwukierunkowe lub poruszając się w różnych kierunkach, możemy rozwiązać ten problem.
Symulowanego wyżarzania:
Algorytm pokonywania wzniesień, który nigdy nie zmierza w stronę niższej wartości, z pewnością będzie niekompletny, ponieważ może utknąć na lokalnym maksimum. A jeśli algorytm zastosuje spacer losowy, przesuwając następcę, to może się zakończyć, ale nie będzie wydajny. Symulowanego wyżarzania jest algorytmem zapewniającym zarówno wydajność, jak i kompletność.
W sensie mechanicznym Wyżarzanie to proces utwardzania metalu lub szkła do wysokiej temperatury, a następnie stopniowego chłodzenia, dzięki czemu metal może osiągnąć stan krystaliczny o niskiej energii. Ten sam proces jest stosowany w symulowanym wyżarzaniu, w którym algorytm wybiera losowy ruch, zamiast wybierać najlepszy ruch. Jeśli losowy ruch poprawi stan, wówczas podąża tą samą ścieżką. W przeciwnym wypadku algorytm podąża ścieżką, której prawdopodobieństwo jest mniejsze niż 1, lub schodzi w dół i wybiera inną ścieżkę.