Begræns søgerummet på en intelligent måde

Nogle gange er udtømmende søgning lige akkurat for langsom. Løsningen er at indskrænke det, du søger igennem, uden at miste noget korrekt svar. 🙂

Et effektivt trick er at fastlåse én variabel ved at gennemløbe dens værdier og derefter løse resten hurtigere. Du bytter en fuld søgning ud med mange små søgninger.

Fastlås det første element, og brug derefter binær søgning eller hashing til at finde dets partner. Det ændrer en gennemgang i O(n i anden) til omtrent O(n log n).

Stop tidligt på enhver sti, der ikke kan slå dit bedste svar indtil videre. En gren, du springer over, koster ingen gennemgangstid.

Hvis du sorterer først, kan du ofte afbryde en loop tidligt. Når værdierne overskrider en grænse, ved du, at resten ikke kan hjælpe.

Hvis det giver samme resultat at bytte to elementer, skal du kun søge i én rækkefølge. Når du tæller hvert tilfælde én gang, kan du halvere arbejdet eller mere.

Del elementerne i to halvdele, gennemgå hver af dem, og kombinér derefter resultaterne. Det reducerer en søgning i 2^n tilfælde til omkring 2^(n/2) arbejde.

Hvis det samme delproblem opstår igen, skal du gemme resultatet og genbruge det. Memoisering fjerner hele gentagne grene fra søgningen.

Beregn en optimistisk grænse for en gren. Hvis selv det bedst mulige resultat dér er dårligere, skal du springe den helt over og spare tiden.

Hver afskæring skal være sikker: Fjern kun stier, der reelt ikke kan vinde. Test mod en enkel udtømmende søgning for at bekræfte, at du ikke har mistet nogen svar.

Brug disse tricks, når udtømmende søgning er lige ved at være hurtig nok, men stadig for langsom. Fastlås en variabel, skær grene væk, eller del problemet, så passer søgningen ofte inden for tidsgrænsen.

Indskrænk søgningen ved at fastlåse en variabel, skære håbløse grene væk, udnytte symmetri eller mødes på midten. Sørg for, at hver afskæring er sikker. 🚀