Referanseside · Kapittel 16

Begreper & formler

Alle nøkkelbegrepene og formlene fra Grådige algoritmer, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards8 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Grådige valg

Algoritmen gjør det beste valget lokalt ved hvert steg.

02The greedy choice property

En egenskap ved grådige algoritmer der lokale optimale valg fører til et globalt optimalt resultat.

03Optimal delstruktur

Kravet om at lokale valg kan føre til en optimal global løsning.

04Aktivitetsutvalg

Klassisk problem der man velger flest mulig ikke-overlappende aktiviteter.

05Huffman-koding

Greedy-algoritme for å lage optimal prefikskode for symboler basert på frekvens.

06Kruskal og Prim

Greedy-algoritmer for minimum spennende trær.

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

Velg aktivitet i med minst f_{i} som ikke overlapper

Greedy-strategi for aktivitetsutvalg: sorter etter sluttid og velg grådige valg som ikke overlapper.

C = i = 1 \sum n f_{i} d_{i}

Total kostnad for Huffman-koding hvor $f_{i}$ er frekvensen til symbol $i$ og $d_{i}$ er dybden i treet.