Innholdsfortegnelse:
Definisjon - Hva betyr Hill Climbing?
Hill climbing er en matematisk optimaliseringsheuristisk metode som brukes for å løse beregningsmessige utfordrende problemer som har flere løsninger. Det er en iterativ metode som tilhører den lokale søkefamilien som starter med en tilfeldig løsning og deretter forbedrer iterativt løsningen ett element av gangen til den kommer til en mer eller mindre optimalisert løsning.
Techopedia forklarer Hill Climbing
Hill climbing er en optimaliseringsteknikk som brukes til å finne en "lokal optimal" løsning på et beregningsproblem. Det starter med en løsning som er veldig dårlig sammenlignet med den optimale løsningen, og deretter forbedres iterativt derfra. Det gjør dette ved å generere "nabo" -løsninger som er relativt et trinn bedre enn den nåværende løsningen, plukker de beste og deretter gjentar prosessen til den kommer frem til den mest optimale løsningen fordi den ikke lenger kan finne noen forbedringer.
varianter:
- Enkel - Den første nærmeste noden eller løsningen som blir funnet er valgt.
- Brattest stigning - Alle tilgjengelige etterfølgerløsninger blir vurdert, og deretter blir den nærmeste valgt.
- Stokastisk - En naboløsning velges tilfeldig, og det blir deretter bestemt om du vil gå videre til den løsningen basert på forbedringsmengde i forhold til gjeldende node.
Hill klatring gjøres iterativt - det går gjennom en hel prosedyre og den endelige løsningen lagres. Hvis en annen iterasjon finner en bedre sluttløsning, erstattes den lagrede løsningen eller tilstanden. Dette kalles også haglklatring, da den ganske enkelt prøver forskjellige stier til den treffer den beste, akkurat som hvordan en hagle er unøyaktig, men fremdeles kan treffe målet på grunn av den store spredningen av prosjektiler. Dette fungerer veldig bra i mange tilfeller fordi det viser seg at det er bedre å bruke CPU-ressurser på å utforske forskjellige veier enn å nøye optimalisere fra en første tilstand.
