Reduser søkerommet på en smart måte

Noen ganger er brute force akkurat litt for tregt. Løsningen er å redusere det du søker gjennom uten å miste noe korrekt svar. 🙂

Et kraftig triks er å fastsette én variabel ved å gå gjennom mulighetene for den, og deretter løse resten raskere. Du bytter ut ett fullstendig søk med mange små søk.

Fastsett det første elementet, og bruk deretter binærsøk eller hashing for å finne partneren. Da blir et søk på O(n i andre) omtrent til O(n log n).

Stopp tidlig på enhver vei som ikke kan slå det beste svaret ditt så langt. En gren du hopper over, koster ingenting å utforske.

Hvis du sorterer først, kan du ofte bryte ut av en løkke tidlig. Når verdiene har passert en terskel, vet du at resten ikke kan hjelpe.

Hvis det gir samme resultat å bytte om på to elementer, trenger du bare å søke gjennom én rekkefølge. Ved å telle hvert tilfelle én gang kan du halvere eller redusere arbeidet enda mer.

Del elementene i to halvdeler, gå gjennom begge, og kombiner resultatene. Da reduseres et søk på 2^n til omtrent 2^(n/2) arbeid.

Hvis det samme delproblemet dukker opp igjen, lagrer du resultatet og bruker det på nytt. Memoisering fjerner hele gjentatte grener fra søket.

Beregn en optimistisk grense for en gren. Hvis selv det beste mulige utfallet der taper, kan du hoppe over grenen helt og spare tid.

Hver begrensning må være trygg: Beskjær bare stier som faktisk ikke kan vinne. Test mot ren brute force for å bekrefte at du ikke har mistet noen svar.

Bruk disse triksene når brute force er nær grensen, men fortsatt for tregt. Fastsett en variabel, beskjær grener eller del opp søket, så passer det ofte innenfor tidsgrensen.

Reduser søket ved å fastsette en variabel, beskjære håpløse grener, utnytte symmetri eller møtes på midten. Sørg for at hver begrensning er trygg. 🚀