Referanseside · Kapittel 34
Begreper & formler
Alle nøkkelbegrepene og formlene fra Tilnærmingsalgoritmer, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Øv med flashcards7 kort fra dette kapittelet
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
01Tilnærmingsforhold
For et minimeringsproblem er der er algoritmens resultat.
02Greedy tilnærming
Bruker lokale valg for å bygge en god (men ikke nødvendigvis optimal) løsning.
05Traveling Salesman (TSP)
For metrisk TSP finnes en 2-approksimasjon ved å bruke MST.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.