Pytania: Programowanie zachłanne

Algorytm zachłanny

Algorytm, który podejmuje lokalnie optymalne decyzje na każdym etapie, mając nadzieję na globalne optymum.

Zastosowanie programowania zachłannego

Stosuje się w problemach takich jak plecak, pokrywanie wierzchołków, czy znajdowanie minimalnego drzewa rozpinającego.

Prawda czy fałsz: Algorytmy zachłanne zawsze dają optymalne rozwiązania.

Fałsz, ponieważ nie wszystkie problemy są rozwiązywalne przy użyciu algorytmów zachłannych.

Różnica między algorytmem zachłannym a dynamicznym

Zachłanny wybiera lokalnie najlepsze opcje, podczas gdy dynamiczny rozwiązuje problemy przez przechowywanie wyników podproblemów.

Greedy Choice Property

Własność, która mówi, że decyzja lokalnie optymalna prowadzi do rozwiązania globalnie optymalnego.

Kryteria zastosowania algorytmu zachłannego

Problem musi spełniać warunki: własność wyboru zachłannego oraz właściwość optymalności.

Uzupełnij zdanie: W problemie plecaka, algorytm zachłanny preferuje ___.

Najpierw przedmioty o największej wartości do wagi.

Minimalne drzewo rozpinające

Struktura, która łączy wszystkie wierzchołki grafu z minimalnym kosztem.

Kryteria wystarczalności algorytmu

Algorytm musi być poprawny, efektywny oraz prosty do implementacji.

Prawda czy fałsz: Algorytmy zachłanne mają wyższy czas działania niż algorytmy dynamiczne.

Fałsz, algorytmy zachłanne są zazwyczaj szybsze i prostsze.

Algorytm Kruskala

Zachłanny algorytm do znajdowania minimalnego drzewa rozpinającego w grafie.

Algorytm Dijkstra

Zachłanny algorytm do znajdowania najkrótszej ścieżki w grafie z nieujemnymi wagami.

Greedy Algorithm vs Brute Force

Zachłanny algorytm jest szybszy, ale nie zawsze optymalny, podczas gdy Brute Force daje rozwiązanie optymalne, ale wolniej.

Przykłady problemów zachłannych

Kryptografia, plecak, pokrywanie wierzchołków, problem change-making.

Złożoność czasowa algorytmu Dijkstra

Złożoność czasowa z wykorzystaniem kopca wynosi $\displaystyle O((V + E) \log V)$.

Właściwość optymalności

Mówi, że najlepsze lokalne rozwiązanie prowadzi do najlepszego globalnego rozwiązania.

Złożoność algorytmu Kruskala

Złożoność wynosi $\displaystyle O(E \log E)$, gdzie $\displaystyle E$ to liczba krawędzi.

Jakie struktury danych wspierają algorytmy zachłanne?

Struktury takie jak kopce, listy oraz zbiory rozłączne.

Uzupełnij zdanie: Złożoność algorytmu zachłannego często wynosi ___ w najlepszym przypadku.

O(n log n) lub O(n) w zależności od problemu.

Prawda czy fałsz: Algorytmy zachłanne są zawsze optymalne.

Fałsz, niektóre problemy wymagają innych podejść.

Ostateczna decyzja w algorytmie zachłannym

Podejmowana jest na podstawie bieżącej analizy dostępnych opcji.

Dlaczego algorytmy zachłanne są efektywne?

Skracają czas obliczeń przez unikanie przeszukiwania wszystkich możliwości.

Zastosowania w praktyce

Stosowane w systemach rekomendacji, grafach, logistyce.

Co to jest problem plecaka?

Problem optymalizacyjny polegający na maksymalizacji wartości przedmiotów w plecaku o ograniczonej pojemności.

Przykład zachłannego wyboru

Wybór najcięższego przedmiotu, który można zabrać do plecaka.

Złożoność czasowa algorytmu plecakowego

Złożoność wynosi O(n * W), gdzie n to liczba przedmiotów, a W to pojemność plecaka.