Video: Cluj-Napoca "Bandă dedicată transportului în comun" sau INCOMPETENŢĂ? 2024
Argumentarea lacomă este adesea folosită ca parte a unui proces de optimizare. Algoritmul vizează problema într-un singur pas și se concentrează doar pe pasul de la mână. Fiecare algoritm lacomă face două ipoteze:
- Puteți face o singură alegere optimă într-un anumit pas.
- Alegerea opțiunii optime la fiecare pas, puteți găsi o soluție optimă pentru problema generală.
Puteți găsi mulți algoritmi lacomi, fiecare optimizat pentru a efectua anumite sarcini. Iată câteva exemple comune de algoritmi lacomi folosiți pentru analiza grafică și comprimarea datelor și motivul pentru care ați putea dori să le utilizați:
- Arborele minim de propagare a lui Kruskal (MST): Acest algoritm demonstrează de fapt unul dintre principiile algoritmilor lacomi pe care oamenii nu le-ar putea gândi imediat. În acest caz, algoritmul alege marginea dintre două noduri cu cea mai mică valoare, nu cea mai mare valoare pe măsură ce cuvântul greșit ar putea să transmită inițial. Acest tip de algoritm vă poate ajuta să găsiți cea mai scurtă cale între două locații pe o hartă sau să efectuați alte sarcini legate de grafic.
- MST lui Prim: Acest algoritm împarte la jumătate un grafic nedirecționat (unul în ce direcție nu este luat în considerare). Apoi selectează marginea care leagă cele două jumătăți astfel încât greutatea totală a celor două jumătăți este cea mai mică posibilă. S-ar putea să găsiți acest algoritm folosit într-un joc de labirint pentru a găsi cea mai mică distanță dintre începutul și sfârșitul labirintului.
- Huffman Encoding: Acest algoritm este destul de faimos în calculatoare, deoarece constituie baza multor tehnici de compresie a datelor. Algoritmul atribuie un cod fiecărei intrări de date unice într-un flux de intrări, astfel încât cea mai frecvent utilizată intrare de date primește cel mai scurt cod. De exemplu, litera E ar primi în mod normal cel mai scurt cod atunci când comprimați textul în limba engleză, deoarece îl utilizați mai des decât orice altă literă din alfabet. Prin schimbarea tehnicii de codare, puteți comprima textul și îl puteți face considerabil mai mic, reducând timpul de transmisie.
