Tilnærmingsstrategier

Tilnærmingsstrategier refererer til planer og metoder som brukes for å finne løsninger som er tilstrekkelig gode når det er upraktisk eller umulig å beregne eller bevise eksakt løsning innenfor rimelig tid eller ressurser. De fokuserer på å redusere problembeskrivelsens kompleksitet ved å søke i et mindre eller enklere løsningrom i stedet for å undersøke hele rommet. Tilnærmingsstrategier brukes bredt i informatikk, matematikk, operasjonsforskning, ingeniørfag og økonomi.

Klassifisering inkluderer heuristikker, tilnærmingsalgoritmer og metaheuristikker. Heuristikker er regelbaserte teknikker som gir raske, ofte tilfredsstillende løsninger men uten garanti for optimalitet. Tilnærmingsalgoritmer kan gi garanterte prestasjonsgrenser i forhold til optimal løsning, for eksempel gjennom tilnærmingsordninger som FPTAS. Metaheuristikker er generelle rammeverk som søker i store løsningrom med fleksible regler; eksempler er lokal søk som hill climbing, tabu-søk, genetiske algoritmer og simulert annealing.

Bruksområder inkluderer ruteplanlegging, ressursallokering, produksjonsplanlegging og grafalgoritmer på store datasett. Fordeler inkluderer rask konvergens og evne til å håndtere komplekse eller store problemer; ulemper inkluderer manglende garanti for optimalitet og avhengighet av parametere og problemspesifikke antagelser.

Historisk har tilnærmingsstrategier utviklet seg fra enkle heuristikker til mer sofistikerte metoder, spesielt i møte med NP-vanskelige problemer. Se også: heuristikk, optimering, tilnærmingsalgoritmer.