Technika Zachlanna

Definicja

Algorytmem zachłannym (ang. greedy algorithm) nazywamy algorytm, który przetwarza podane dane byle jak i intuicyjnie najczęściej to działa. A formalnie: w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm zachłanny nie patrzy czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji. Typowe zadanie rozwiązywane metodą zachłanną ma charakter optymalizacyjny.

Przykłady

Ciągły problem plecakowy

Mamy przedmioty o różnych wartościach i wagach i podaną pewną pojemność plecaka. W odróżnieniu od znanego nam wcześniej problemu, przedmioty możemy dzielić na fragmenty. Jak rozwiązać problem? Oczywiście zachłannie: najpierw liczymy stosunki wartości do wagi hi= ci / wi następnie sortujemy je malejąco i wstawiamy do plecaka dopóki suma jest mniejsza od naszej pojemności. Jeśli istnieje optymalne rozwiązanie to ono właśnie tak robi.

Wojownicy

Mamy stoczyć walkę z armią nieprzyjaciela. Każdy wojownik jest obdarzony pewną siłą: jeśli nasz wojownik i ma siłę ai , a wojownik j przeciwnika ma siłę bi i ai>bj to znaczy, że wojownik nasz wojownik i wygrywa z wojownikiem j. Za każdy wygrany pojedynek dostajemy 1 pkt, za przegrany tracimy 1 pkt, załóżmy że nie ma remisów, każdy wojownik walczy tylko raz, jak ustawić walki, żeby wyjść najkorzystniej? Sortujemy siły nasze i siły nieprzyjaciela, następnie sprawdzamy czy nasz najsilniejszy wygrywa z ich najsilniejszym: jeśli tak, to toczymy walkę, jeśli nie to poświęcamy naszego najsłabszego wojownika, gdyż skoro nasz najsilniejszy przegrywa to każdy nasz wojownik będzie przegrywać. I tak póki nie stoczymy wszystkich walk.
A co gdyby były remisy? Tak samo, a jeśli pojawiają nam się remisy to parujemy. Dlaczego? Gdyż dwa remisy są niegorsze od sparowania "na krzyż" czyli od parowania najlepszego z najgorszym i najgorszego z najlepszym.

Kajaki

Mamy pewną ilość kajaków i ludzi o różnych wagach, do każdego kajaka może wejść jedna lub dwie osoby jeśli suma ich wag jest mniejsza niż pojemność kajaka. Jak dobrać ludzi, żeby jak najwięcej sobie popływało? Na początek sortujemy ich po wagach. Następnie dobieramy najlżejszego z najcięższym, można zapytać dlaczego? Jeżeli najlżejszy wejdzie z najcięższym, to najlżejszy może wejść z każdym, więc w optymalnym rozwiązaniu najlżejszy sobie popływa, więc sparujmy go z tym najcięższym i lećmy dalej póki nie skończą nam się kajaki.

Smoki

Na początek posortujmy sobie pastwiska w kolejności nierosnącej, następnie sumujmy sobie ilość owieczek z kolejnych pastwisk odejmując kolejne liczby naturalne, czyli (najliczniejsze) + (prawie_najliczniejsze - 1) + (prawie_prawie_najliczniejsze - 2) +… dopóki wynik w nawiasie jest większy od 0. A teraz dlaczego to działa: nie da się wziąć więcej owieczek, gdyż nie posiadamy tyle ruchów żeby ich wziąć. A jak z kolejnością? Smok leci w i zjada owieczki ze skrajnych lewych i prawych pastwisk z naszego rozwiązania. Po każdym dniu tracimy (ilość_pastwisk_z_rozwiązania - ilość_pastwisk_opróżnionych przez smoka) owieczek. Wynik działań smoka można zapisać jako: pastwisko_odwiedzone_jako_pierwsze + pastwisko_odwiedzone_jako_drugie + …odwiedzone_jako_ostatnie - 0 - 1 - 2 - 3 -…- n. A wiemy że dodawanie i odejmowanie jest przemienne więc można to zapisać jako (najliczniejsze) + (prawie_najliczniejsze - 1) + (prawie_prawie_najliczniejsze - 2) +…

Ławka

Co robi najpierw? Oczywiście sortujemy, tyle że tym razem po końcach przedziałów czyli po right. Tworzymy sobie tablice Z (Z[i]= ilość zdjęć które zrobiliśmy do końca przedziału i). Skoro zdjęcia możemy robić w dowolnym momencie to teraz bierzemy sobie przedział który najwcześniej się kończy i w chwili kiedy się kończy robimy przestępcy tyle zdjęć ile potrzeba. Biorąc następnego przestępce sprawdzamy ile zdjęć zrobiliśmy pomiędzy początkiem a końcem jego przedziału i w chwili kiedy jego przedział się kończy to dorabiamy mu tyle zdjęć ile potrzeba. Aby nie dostać TLE, szukając zdjęć które robiliśmy od początku do końca przedziału, robimy to binarnie.

PS: w ramach jakichkolwiek nieścisłości czy problemów lub błędów proszę pisać !

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License