Den lokala sökalgoritmen är en metod för att hitta den bästa lösningen i närheten av det aktuella tillståndet. Denna teknik används ofta för att förfina ungefärliga lösningar genom att iterativt modifiera enskilda komponenter för att upptäcka bättre tillstånd.
Hur det fungerar
- Initialisering: Börja med ett initialt tillstånd.
- Generera grannar: Generera angränsande tillstånd genom att ändra en komponent i det aktuella tillståndet.
- Utvärdering: Utvärdera kvaliteten på grannstater med hjälp av en objektiv funktion.
- Välj bästa tillstånd: Välj den angränsande staten med det bästa objektiva värdet.
- Upprepa: Iterera genom steg 2 till 4 tills du inte kan hitta någon bättre grannstat.
Exempel: Optimera Fibonacci funktionen
Betrakta optimeringsproblemet för Fibonacci funktionen F(x) = F(x-1) + F(x-2) med F(0) = 0, F(1) = 1. Vi vill hitta värdet på x för vilket F(x) är maximerad. Vi kan använda metoden för lokal sökning för att iterativt utforska längre från varje steg.
Kodexempel i C++
I det här exemplet använder vi metoden lokal sökning för att optimera funktionen Fibonacci. Vi itererar genom olika värden på x och beräknar Fibonacci värdet vid varje x. När ett bättre värde hittas uppdaterar vi det bästa värdet och dess motsvarande x.