Złożoność obliczeniowa/Test 7: Algorytmy aproksymacyjne: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
mNie podano opisu zmian
 
(Nie pokazano 1 wersji utworzonej przez jednego użytkownika)
Linia 1: Linia 1:
<quiz>Problemy NP-optymalizacyjne
<quiz>
Problem NP-optymalizacyjny <math>\Pi</math>  
Problem NP-optymalizacyjny <math>\Pi</math>  
<wrongoption>jest wersją optymalizacyjną pewnego problemu NP-zupełnego</wrongoption>
<wrongoption>jest wersją optymalizacyjną pewnego problemu NP-zupełnego</wrongoption>
Linia 8: Linia 8:




<quiz>Stała aproksymacji
<quiz>
Jeśli <math>A</math> jest algorytmem <math>4/5</math>-aproksymacyjnym dla problemu maksymalizacji <math>\Pi</math>, to  
Jeśli <math>A</math> jest algorytmem <math>4/5</math>-aproksymacyjnym dla problemu maksymalizacji <math>\Pi</math>, to  
<wrongoption><math>A</math> jest algorytmem optymalizacyjnym dla <math>\Pi</math></wrongoption>
<wrongoption><math>A</math> jest algorytmem optymalizacyjnym dla <math>\Pi</math></wrongoption>
Linia 17: Linia 17:




<quiz>Algorytm skojarzeniowy dla pokrycia wierzchołkowego
<quiz>
Algorytm skojarzeniowy dla pokrycia wierzchołkowego  
Algorytm skojarzeniowy dla pokrycia wierzchołkowego  
<wrongoption>znajduje zawsze rozwiązanie optymalne</wrongoption>
<wrongoption>znajduje zawsze rozwiązanie optymalne</wrongoption>
Linia 26: Linia 26:




<quiz>Aproksymacja dla problemu maksymalnego przekroju<quiz>
<quiz>
Algorytm zachłanny dla problemu MAX CUT  
Algorytm zachłanny dla problemu MAX CUT  
<wrongoption>posiada stałą aproksymacji równą 2</wrongoption>
<wrongoption>posiada stałą aproksymacji równą 2</wrongoption>
Linia 35: Linia 35:




<quiz>Nieaproksymowalność problemu komiwojażera
<quiz>
Wykazujemy, że problem komiwojażera nie posiada <math>a</math>-aproksymacji dla żadnej stałej <math>a</math>,  
Wykazujemy, że problem komiwojażera nie posiada <math>a</math>-aproksymacji dla żadnej stałej <math>a</math>,  
<rightoption>tylko przy założeniu <math>P\neq NP</math></rightoption>
<rightoption>tylko przy założeniu <math>P\neq NP</math></rightoption>
Linia 44: Linia 44:




<quiz>Aproksymowalność problemu komiwojażera
<quiz>
Problem komiwojażera ma strategię <math>a</math>-aproksymacyjną  
Problem komiwojażera ma strategię <math>a</math>-aproksymacyjną  
<rightoption>jeśli spełniona jest nierówność trójkąta, dla <math>a=3/2</math></rightoption>
<rightoption>jeśli spełniona jest nierówność trójkąta, dla <math>a=3/2</math></rightoption>
<wrongoption>jeśli spełniona jest nierówność trójkąta, wykorzystującą algorytm znajdowania skojarzenia w grafie dwudzielnym</wrongoption>
<wrongoption>jeśli spełniona jest nierówność trójkąta, wykorzystującą algorytm znajdowania skojarzenia w grafie dwudzielnym</wrongoption>
<wrongoption>bez założenia o nierówności trójkata, dla <math>a=2</math></wrongoption>
<wrongoption>bez założenia o nierówności trójkata, dla <math>a=2</math></wrongoption>
<rightoption>dla pewnej stałej <math>a</math>, jeśli wagi krawędzi należą do zbioru <math>\1,2\ }</math></rightoption>
<rightoption>dla pewnej stałej <math>a</math>, jeśli wagi krawędzi należą do zbioru <math>1,2</math></rightoption>
</quiz>
</quiz>




<quiz>Strategia zachłanna dla problemu plecakowego
<quiz>
Aproksymacyjny algorytm zachłanny dla problemu plecakowego  
Aproksymacyjny algorytm zachłanny dla problemu plecakowego  
<wrongoption>upakowuje najpierw elementy o największej wartości</wrongoption>
<wrongoption>upakowuje najpierw elementy o największej wartości</wrongoption>

Aktualna wersja na dzień 21:43, 28 sie 2023

Problem NP-optymalizacyjny Π

jest wersją optymalizacyjną pewnego problemu NP-zupełnego

jest wersją optymalizacyjną pewnego problemu z klasy NP

posiada wielomianowo obliczalną funkcję kosztu rozwiązania

posiada wielomianową procedurę sprawdzania, czy dane rozwiązanie jest rozwiązaniem dopuszczalnym


Jeśli A jest algorytmem 4/5-aproksymacyjnym dla problemu maksymalizacji Π, to

A jest algorytmem optymalizacyjnym dla Π

A jest algorytmem 5/6-aproksymacyjnym dla Π

A jest algorytmem 3/4-aproksymacyjnym dla Π

z definicji, jest to sytuacja niemożliwa


Algorytm skojarzeniowy dla pokrycia wierzchołkowego

znajduje zawsze rozwiązanie optymalne

jest algorytmem 5/2-aproksymacyjnym

jest algorytmem 15/8-aproksymacyjnym

nigdy nie znajduje rozwiązania optymalnego


Algorytm zachłanny dla problemu MAX CUT

posiada stałą aproksymacji równą 2

posiada stałą aproksymacji równą 1/2

nie posiada stałej aproksymacji

nie ma złożoności wielomianowej


Wykazujemy, że problem komiwojażera nie posiada a-aproksymacji dla żadnej stałej a,

tylko przy założeniu P≠NP

redukując problem cyklu Hamiltona

redukując problem cyklu Eulera

zacieśniając problem komiwojażera do instancji o kosztach krawędzi ograniczonych przez 2


Problem komiwojażera ma strategię a-aproksymacyjną

jeśli spełniona jest nierówność trójkąta, dla a=3/2

jeśli spełniona jest nierówność trójkąta, wykorzystującą algorytm znajdowania skojarzenia w grafie dwudzielnym

bez założenia o nierówności trójkata, dla a=2

dla pewnej stałej a, jeśli wagi krawędzi należą do zbioru 1,2


Aproksymacyjny algorytm zachłanny dla problemu plecakowego

upakowuje najpierw elementy o największej wartości

upakowuje najpierw elementy o najmniejszej wadze

ma stałą aproksymacji równą 1/2

ma stałą aproksymacji równą 2

żadna z pozostałych odpowiedzi nie jest poprawna

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa/Test_7:_Algorytmy_aproksymacyjne&oldid=80117”