Algorytmy na grafach

Graf zorientowany: G = (V, E)

gdzie: V - skończony niepusty zbiór wierzchołków,

E ⊆ V × V - zbiór krawędzi,

krawędzie są parami wierzchołków.

Graf niezorientowany: G = (V, E)

gdzie: V - skończony niepusty zbiór wierzchołków

E ⊆ 2^V - zbiór krawędzi, ∀e∈E : e = 2

krawędzie są dwuelementowymi podzbiorami.

Na ogół oznaczamy: V = n, E = m.

Liczba krawędzi:

W grafie zorientowanym: 0 ≤ m ≤ n*n

W grafie niezorientowanym: 0 ≤ m ≤ n*(n-1)/2

Reprezentacja komputerowa

Utożsamiamy: V = {1,...,n}

1. Tablica sąsiedztwa:

A[i, j] = 1, jeśli (i, j) ∈ E

0, jeśli (i, j) ∉ E

jej wielkość nie zależy od liczby krawędzi w grafie.

Dla grafu niezorientowanego jest symetryczna, z zerami na przekątnej.

2. Listy sąsiedztwa (listy następników):

Tablica L[n] list (często oznaczana również Adj - "adjacency")

L[i] jest nagłówkiem listy zawierającej wszystkie j, takie że (i, j) jest krawędzią. Kolejność na listach dowolna.

Dla grafu niezorientowanego każda krawędź (i, j) reprezentowana jest w liście L[i] oraz w liście L[j].

Terminologia

• Stopień wierzchołka: liczba jego sąsiadów

• Ścieżka od wierzchołka u do wierzchołka w: ciąg wierzchołków v₀, v₁, ..., v_k taki, że (v_i, v_i+1) ∈ E, i=0,...,k-1, v₀ = u, v_k = w (mówimy również: wierzchołek w jest osiągalny z wierzchołka u)

• Ścieżka prosta (elementarna): wierzchołki na ścieżce nie powtarzają się (być może za wyjątkiem v₀ = v_k)

• Cykl: ścieżka zamknięta, tzn. v₀ = v_k

• Długość ścieżki: liczba krawędzi na ścieżce (tutaj: k)

• Odległość od wierzchołka v do wierzchołka u: długość najkrótszej ścieżki od u do v (przyjmujemy ∞ jeśli v nie jest osiągalny z u)

• Podgraf grafu G=(V, E) : graf H=(V', E') taki, że V' ⊆ V, E' ⊆ E

• Podgraf indukowany grafu G=(V, E) : graf H=(V', E') taki, że V'⊆V, E' = {(u, v) ∈ E u, v ∈ V' }

Definicje - dla grafu niezorientowanego G=(V, E) :

• G jest spójny: każdy wierzchołek jest osiągalny z każdego wierzchołka

• Spójna składowa grafu G : maksymalny podgraf indukowany H taki, że H jest spójny

• G jest drzewem: gdy G jest spójny i nie zawiera cykli (często z wyróżnionym wierzchołkiem zwanym korzeniem)

• Drzewo rozpinające dla spójnego niezorientowanego grafu G=(V,E): drzewo T=(V', E') takie, że V'=V, E' ⊆ E (czyli podgraf bez cykli, łączący wszystkie wierzchołki)

Dla grafu zorientowanego:

• G jest silnie spójny: gdy każdy wierzchołek jest osiągalny z każdego wierzchołka

• Silnie spójna składowa grafu G: maksymalny podgraf indukowany H taki, że H jest silnie spójny

Najkrótsze ścieżki w grafach

Graf G = (V, E) (zorientowany lub niezorientowany)

funkcja w : E -> R wagi krawędzi, ozn. V = n, E = m

Def. odległość od wierzchołka u do wierzchołka v

d(u, v) := długość najkrótszej ścieżki idącej od u do v

Czy d(u, v) zawsze istnieje ?

Nie. Jeśli graf zawiera cykl o ujemnej długości, to powtarzanie tego cyklu daje ścieżki o coraz mniejszej długości.

Zakładamy, że graf nie zawiera cykli o ujemnej długości.

Problem: najkrótsze ścieżki przy ustalonym źródle s.

dla zadanych G = (V, E), w : E ->R, ustalonego s ∈ V, znaleźć d(s,v) dla każdego v ∈ V.

Uwaga 1.

W ogólnym przypadku nie da się znaleźć d(s, v) tylko dla v, bo jeśli nie znamy d(s, x), to skąd wiemy, że nie ma krótszej ścieżki idącej z s do v przez x ?

Uwaga 2.

Obliczając d(s, v) dla wszystkich v ∈ V, można równocześnie zapamiętywać informację o najkrótszej ścieżce, zapamiętując zawsze poprzednik węzła na takiej ścieżce (jak w algorytmie poniżej)

Fakt:

Dla każdej krawędzi (u, v) : d(s, v) <= d(s, u) + w(u, v).

Dowód: bo jeśliby d(s, v) > d(s, u) + w(u, v), to istniałaby ścieżka z s do v, przechodząca przez u, o krótszej długości niż d(s, v)

Metoda ogólna

podstawa większości algorytmów obliczania d(s, v):

- w tablicy D[ ], D[v] przechowuje wyliczone dotychczas najlepsze oszacowanie od góry dla d(s, v); początkowo równe plus nieskończoność.

- w odpowiedniej kolejności, odpowiednią liczbę razy wykonywać procedurę Relax - poniżej

- gdy kolejne iteracje nie poprawiają oszacowań D[ ], zachodzi D[v]=d(s, v).

Reprezentacja grafu: dowolna; wagi pamiętane wraz z krawędziami.

procedure Init ; (* inicjalizacja *)

begin

for each v ∈ V do

(* tlumaczy się na "for i:=1,...,n" *)

begin

D[v] := PlusInfty ; (* + nieskończoność *)

P[v] := Empty ;

(* poprzednik na najkrótszej ścieżce do v *)

end

end

procedure Relax (u, v : vertex) ;

(* (u, v) jest krawędzią *)

begin

if ( D[v]> D[u]+w[u,v] )

begin

D[v] := D[u]+w[u,v] ; (*poprawiono oszacowanie*)

P[v] := u ; (* nowy poprzednik na ścieżce *)

end

end

Koszt:

- inicjalizacja: O(n)

- pojedyncza Relax: O(1)

Algorytm DIJ (Dijkstra)

Dodatkowo zakładamy, że wagi krawędzi są nieujemne.

• W zbiorze Q przechowuj wierzchołki v, dla których D[v] jeszcze nie ma ostatecznej wartości; początkowo Q=V i ustaw D[s]=0.

• W kolejnych krokach znajduj u∈Q taki że D[u] najmniejsze. Fakt: w tym momencie D[u] = d(s, u). Usuń u z Q i popraw pozostałym v∈Q ich D[v], względem u.

procedure DIJ

(G-graf, w-wagi krawędzi(nieujemne), s-źródło) ;

begin

Init ;

D[s] := 0 ;

Q := V ; (* lista wierzchołków *)

while (Q <> ListaPusta)

begin

u := Del_Min (Q) ;

(* usunięcie najmniejszego z Q *)

for each v ∈ L[u] do

(* L[u] - lista następników węzła u *)

Relax (u, v) ;

end

end

Uwaga: Wywołanie Relax (u, v) gdy v ∉ Q, nic nie psuje (nie zmienia D[v]), ale można tego nie robić testując tablicą bitową przynależność do Q.

Złożoność - gdy Q jest zwykła listą: O(n²)

• wyszukanie i usunięcie minimum: O(n)

• przeglądnięcie listy następników i wykonanie Relax : O(n)

• pętla zewnętrzna iterowana n razy

Gdy Q kopiec, reprezentacja grafu listami sąsiedztwa: O(m log n)

bo, w sumie po wszystkich iteracjach pętli zewnętrznej:

• Del_Min: O(n log n)

• Relax: O(m log n) (każda krawędź raz , koszt przesiewania log n)

Problem minimalnego drzewa rozpinającego:

Graf G = (V, E) niezorientowany, spójny; w : E R wagi krawędzi.

(wagi pamiętane w tablicy lub listach sąsiedztwa).

Problem: znaleźć drzewo rozpinające dla G o minimalnym koszcie.

Tzn. E'⊆E taki, że T=(V, E') jest drzewem, oraz ∑_e∈E' w(e) jest najmniejsza z możliwych (zachodzi oczywiście E'=n-1)

Algorytm J-P (Jarnik, Prim)

Idea:

Zaczynając od drzewa złożonego z jednego dowolnego wierzchołka dodawaj do niego kolejne wierzchołki wraz z krawędzią łączącą dany wierzchołek z drzewem.

- W zbiorze Q przechowuj wierzchołki v, pozostające jeszcze poza konstruowanym drzewem.

- W tablicy D, dla każdego wierzchołka v ze zbioru Q D[v] jest wagą najkrótszej krawędzi z v do węzła w drzewie,

- W tablicy P, P[v] jest równe numerowi węzła w drzewie, do którego odległość jest pamiętana w D[v].

- W kolejnym kroku znajdź u∈Q takie że D[u] najmniejsze. Dodaj do drzewa węzeł u wraz z krawędzią (P[u], u). Usuń u z Q i popraw pozostałym v∈Q ich D[v], względem u.

Dane: G=(V,E,w) - graf z wagami krawędzi

r∈V - korzeń (wierzchołek startowy)

for each u∈V do D[u] := +∞ ;

D[r] := 0 ;

P[r] := -1 ; (* r - korzeń - nie ma poprzednika *)

Q := V ; (* Q jest np. listą, tablicą itp. *)

F := ∅ ; (* zbiór krawędzi drzewa *)

while (Q <> ∅) do

begin

u := min (Q) ; (* tzn. D[u] minimalne, w Q *)

Q := Q - {u} ; (* usuń z Q najmniejszy *)

F := F ∪ { (u, P[u]) ;

(* u już w drzewie, popraw oszacowania *)

(* dla jego sąsiadów poza drzewem *)

for each v ∈ L[u] do

if ((v∈Q) and (w[u,v] < D[v]))

begin (* teraz u najbliższy w drzewie dla v *)

D[v] := w[u,v] ;

P[v] := u

end

end

Złożoność: O(n²)

Modyfikacje (kopiec) analogiczne jak dla algorytmu DIJ.

Problemy obliczeniowo trudne, teoria NP-zupełności

Problem obliczeniowo łatwy:

posiada algorytm o wielomianowej złożoności czasowej

Przykłady:

- sortowanie listy

- wyszukiwanie elementu w zbiorze

- znajdowanie najkrótszych ścieżek w grafie

- rozwiązywanie układu równań liniowych

Problem obliczeniowo trudny:

nie posiada algorytmu o wielomianowej złożoności.

Znaczenie zagadnienia:

Problemu trudnego obliczeniowo nie da się rozwiązać, nawet na najszybszych komputerach, nawet dla danych umiarkowanego rozmiaru, i najprawdopodobniej nigdy nie będzie się dało.

Teoria złożoności obliczeniowej posługuje się formalnym modelem obliczeń (najczęściej: maszyną Turinga), i dotyczy rozpoznawania języków formalnych. W praktyce wygodniej posłużyć się pojęciem:

Problem decyzyjny Q:

Określony jest przez opis instancji (czyli danych wejściowych) w terminach zbiorów, relacji, liczb itp. oraz pytanie typu “tak-nie”.

Formalnie:

Zbiór instancji D(Q) - dziedzina problemu.

Podzbiór Y(Q) ⊆ D(Q) instancji, na które odpowiedź brzmi "tak".

Rozwiązanie problemu decyzyjnego: algorytm, który dla każdej instancji kończy obliczenie z prawidłową odpowiedzią "tak-nie".

Formalnie: algorytm odpowiada maszynie Turinga, rozpoznającej język słów, które są opisami instancji z podzbioru Y(Q)

Przykład: problem komiwojażera (TSP):

I: n - liczba miast, d(i,j) ∈N - odległość, dla każdej pary miast (i,j), oraz ograniczenie B ∈N.

?: istnieje droga komiwojażera o długości nie większej niż B, przechodząca przez każde miasto dokładnie raz i wracająca do miejsca startu.

Przykładowe rozwiązanie problemu komiwojażera :

Rozważyć każdą permutację zbioru miast i sprawdzić, czy któraś z nich definiuje wymaganą ścieżkę; jeśli znajdzie się taka to odpowiedz “tak”, w przeciwnym przypadku “nie”.

Złożoność: rzędu co najmniej n! , dyskwalifikująca rozwiązanie dla celów praktycznych

Wersje decyzyjne problemów vs. wersje optymalizacyjne:

OPT-TSP:

dla podanych odległości d(i,j) znajdź najkrótszą drogę komiwojażera.

Wersje optymalizacyjne na ogół bardziej praktyczne, nie są łatwiejsze obliczeniowo (trudniej jest policzyć globalne optimum).

Zatem wykazanie, że dany problem decyzyjny jest trudny implikuje, że skojarzony z nim problem optymalizacyjny też jest trudny.

Metoda ogólna dowodzenia trudności obliczeniowej problemu decyzyjnego Q:

udowodnić, że Q jest nie łatwiejszy obliczeniowo niż inny problem R, o którym wcześniej ktoś udowodnił. że jest trudny.

Narzędzie do takiego dowodu: transformacja wielomianowa.

Transformacja wielomianowa

przekształcenie danych (czyli instancji) problemu R w dane dla problemu Q tak, by pokazać, że Q jest nie łatwiejszy niż R.

Formalnie oznaczamy: R ∝ Q

Problem decyzyjny R jest wielomianowo transformowalny do problemu Q, jeśli istnieje funkcja F : D(R) D(Q), realizowalna algorytmem o złożoności wielomianowej, taka, że

∀I∈D(R): I∈Y(R) ⇔ f(I)∈Y(Q)

Problem cyklu Hamiltona (HC):

I: Graf niezorientowany G

?: G ma cykl Hamiltona (cykl przechodzący przez każdy wierzchołek dokładnie raz)

Fakt: HC ∝ TSP

Dowód: konstruujemy funkcję F

argument funkcji F: instancja HC, czyli graf G=(V,E)

wartość funkcji F: instancja TSP, czyli n, d(i,j), B

n = V 

d(i,j) = 1, jeśli (i,j) jest krawędzią w grafie

2, w przeciwnym przypadku

B = n (koniec definicji funkcji F)

• Funkcję F łatwo zrealizować algorytmem wielomianowym.

• G ma cykl Hamiltona ⇔ Komiwojażer ma ścieżkę o długości B.

Koniec dowodu.

Wniosek: jeśli miałbym algorytm A wielomianowy dla TSP, to składając F z A dostałbym również algorytm wielomianowy dla HC (czyli TSP jest trudniejszy niż HC).

Własność transformacji wielomianowej:

Jeśli R ∝ Q to: 1. Q łatwy R łatwy

2. R trudny Q trudny

Klasy problemów P i NP.

Klasa P: (polynomial)

Ogół problemów decyzyjnych rozwiązywalnych w czasie wielomianowym (problemy obliczeniowo łatwe)

Klasa NP: (nondeterministic polynomial)

Ogół problemów decyzyjnych rozwiązywalnych w czasie wielomianowym algorytmem niedeterministycznym.

Algorytm (komputer) niedeterministyczny:

Model czysto abstrakcyjny. Posiada dwie fazy obliczeń:

1. zgaduje dowolny obiekt (fizycznie: ciąg znaków, np. bitów), zapisuje go w pamięci roboczej

2. wykonuje obliczenia traktując jako dane wejściowe oryginalną instancję oraz zapisany obiekt.

Definicja : algorytm niedeterministyczny K rozwiązuje problem decyzyjny Q jeśli dla każdej instancji I zachodzi:

• I∈Y(Q) istnieje taki obiekt, że jeśli zostanie odgadnięty, to algorytm zakończy się akceptacją

• I ∉ Y(Q) dla dowolnego odgadniętego obiektu algorytm odpowie “nie”

Algorytm niedeterministyczny inaczej:

sprawdzenie, czy dany obiekt jest “świadkiem” faktu, że I∈Y(Q).

Komiwojażer - alg. niedeterministyczny:

1. Zgadnij ciąg wierzchołków

2. Sprawdź, czy ciąg ten jest poprawną drogą komiwojażera o odpowiedniej długości, i jeśli tak - odpowiedz “tak', wpp. “nie”.

Złożoność: O(n) - wielomianowa, TSP ∈ NP.

Równoważna definicja klasy NP:

NP to ogół problemów decyzyjnych, których rozwiązania są weryfikowalne w czasie wielomianowym

(to ile trwa znajdowanie tych rozwiązań jest tutaj nieistotne).

Fakt: P ⊆ NP

(bo każdy zwykły algorytm deterministyczny, może być traktowany jako niedeterministyczny, który pomija odgadnięty obiekt)

Fakt (z życia):

Dla wielu problemów z klasy NP (w tym: TSP), mimo usilnych starań, nie znaleziono algorytmu wielomianowego, stąd hipoteza:

Hipoteza: NP - P ≠ ∅

czyli: w klasie NP są problemy obliczeniowo trudne. Próbą ich charakteryzacji jest definicja klasy NPC.

Klasa NPC (inaczej: NP - zupełne)

Problem Q jest NP-zupełny, jeśli:

1. Q ∈ NP, oraz

2. ∀ R∈NP : R ∝ Q

Problem NP-zupełny jest najtrudniejszy w NP, tzn. jeśliby posiadał algorytm wielomianowy, to wszystkie problemy w NP byłyby łatwe.

Jeśli hipoteza jest prawdziwa, to problemy NP-zupełne są trudne obliczeniowo.

Przy aktualnym stanie wiedzy:

problem NP-zupełny traktowany jest jako trudny obliczeniowo.

Największy nierozstrzygnięty problem informatyki teoretycznej:

P ≠ NP ???

Jak stwierdzić, że dany problem Q jest NP-zupełny ?

1. znaleźć go na liście w podręczniku do algorytmiki, albo

2. wykazać samemu

metoda: dobrać R ∈ NPC i skonstruować transformację R ∝ Q,

Np. Wykazano, że HC jest NP-zupełny. Pokazaliśmy, że:

1. TSP ∈ NP.

2. HC ∝ TSP

TSP jest NP-zupełny

Skąd wziął się pierwszy problem NP-zupełny ?

Problem spełnialności formuł logicznych (SAT):

I: formuła zdaniowa nad pewnymi zmiennymi logicznymi, w koniunkcyjnej postaci normalnej, np. ( x oznacza "nie x")

(x₁∨x₂∨x₄) ∧ (x₂∨x₃) ∧ (x₁∨x₂∨x₃∨x₄) ∧ (x₂∨x₄)

?: czy istnieje przypisanie zmiennym wartości 0, 1 tak, by formuła była spełniona

Twierdzenie (Cook, 1971):

SAT jest NP-zupełny

Dowód: zapis za pomocą formuły logicznej faktu, że dana niedeterministyczna maszyna Turinga akceptuje słowo wejściowe x.

Niestety, najprawdopodobniej w NP są jeszcze problemy pośrednie: ani łatwe, ani NP-zupełne.

Twierdzenie (Ladner 1976)

Jeśli P ≠ NP to NP - (P ∪ NPC) ≠ ∅

Jeśli trafimy na taki problem, nic o nim nie potrafimy powiedzieć (chyba że przy okazji rozwiążemy problem czy P ≠ NP).

Przykłady problemów NPC:

• Cykl Hamiltona (ale cykl Eulera jest łatwy)

• Komiwojażer

(ale najkrótsze ścieżki oraz min. drzewo rozpinające są łatwe)

• Pokrycie wierzchołkowe

dla danego grafu i liczby K, czy istnieje podzbiór K wierzchołków taki, że każda krawędź ma przynajmniej jeden koniec w tym zbiorze

• Kolorowanie grafu

I: G = (V,E) graf niezorientowany, K - liczba naturalna

?: G jest K-kolorowalny, tzn. każdemu wierzchołkowi można przypisać kolor, tak aby końce każdej krawędzi miały różne kolory, używając nie więcej niż K kolorów.

Szczególny przypadek: kolorowanie mapy. Każda mapa jest 4-kolorowalna, ale problem, czy jest 3-kolorowalna jest NPC.

Układanie harmonogramu zajęć może być sprowadzone do kolorowania.

• Pokrycie zbiorami

znaleźć możliwie najmniejszą podrodzinę rodziny podzbiorów, aby pokryty został każdy element zbioru (crew scheduling !)

• Izomorfizm podgrafu

dane grafy G, H, pytanie czy G ma podgraf identyczny z H

(częste zastosowanie: sztuczna inteligencja, rozpoznawanie obrazów)

• Klika (szczególny, nadal trudny przypadek poprzedniego):

znaleźć największy podgraf w którym każdy z każdym jest połączony krawędzią

• Podział

Dany zbiór elementów o podanych wagach. Czy da się podzielić je na dwa rozłączne podzbiory, których suma wag jest taka sama ?

• Plecak

Zbiór elementów o podanych wagach i wartościach, żądana wartość V i pojemność plecaka B. Czy istnieje podzbiór elementów, których suma wag nie przekracza B, a suma wartości wynosi co najmniej V?

• Szeregowanie czynności - wiele wersji, np.:

I: n zadań, m stanowisk, każde zadanie musi przejść przez stanowiska 1,....,m , w tej kolejności, zadanie i-te zajmuje na stanowisku j-tym t(i,j) czasu, oraz dane jest ograniczenie B

?: istnieje kolejność wykonywania zadań, tak aby zakończyły się przed czasem B

• Programowanie całkowitoliczbowe (ale programowanie liniowe

jest w P, chociaż praktycznie stosowany algorytm sympleks jest wykładniczy)

• Pakowanie

Jak jest minimalna liczba pudełek o ustalonej pojemności, które pomieszczą zbiór elementów o zadanych rozmiarach.

• Pakowanie 2-wymiarowe

minimalna długość paska materiału potrzebna do wycięcia zadanych kształtów.

Ważne problemy podejrzewane o to, że są pośrednie:

• Izomorfizm grafów

• Liczby pierwsze

• Liczby złożone

Zakładana trudność obliczeniowa dwóch ostatnich jest podstawą współczesnej kryptografii.

(Nieliczne) problemy, dla których wykazano trudność obliczeniową (tzn. że na pewno wymagają czasu wykładniczego):

1. Szachy, warcaby (uogólnione, N x N), inne gry (problem istnienia strategii wygrywającej w danej konfiguracji)

2. problemy z logiki matematycznej

3. problemy z teorii języków formalnych

Metody pokonywania problemu trudnego obliczeniowo

dotyczą wersji optymalizacyjnych (np. szukanie minimum)

1. Dokładna analiza, być może jest łatwy, bo ograniczony do szczególnego rodzaju instancji

(np. kolorowanie, gdy graf nie ma cykli, jest bardzo łatwe, a sprawdzenie tego też jest łatwe)

2. Heurystyki szukające optimum, redukujące specjalnymi technikami czas obliczeń (często nieskutecznie), np.

metoda rozgałęzień i ograniczeń ('branch & bound')

3. Algorytmy (albo: strategie) aproksymacyjne :

czas szybki, wynik poprawny ale niedokładny, z gwarancją ograniczenia wielkości błędu, postaci

A(I) <= c OPT (I), dla każdej instancji I

A(I) - wielkość (koszt) wyniku algorytmu aproksymacyjnego

c - stała, niezależna od instancji, na pewno większa niż 1

(dla problemu maksymalizacyjnego nierówność odwrotna).

Np. Strategia "2MST"

TSP, z nierównością trójkąta (tzn. d(i,j) <= d(i,k) + d(k,j), ∀i,j,k ); (jest to, mimo ograniczenia, dalej problem NPC)

1. Znajdź minimalne drzewo rozpinające dla zbioru miast (traktowanego jako graf pełny).

2. Obejdź drzewo standardowa metodą przeglądu grafu, krawędzie trawersowane zarówno w przód jak i w tył wypisuj - utworzą cykl.

3. W tym cyklu usuń powtarzające się wierzchołki (dokonując skrótów) - powstanie cykl elementarny C, jest to wynik strategii.

Fakt: C <= 2 * OPT

Dowód: MST <= OPT, bo cykl komiwojażera, po rozcięciu jest ścieżką, czyli szczególnym przypadkiem drzewa rozpinającego.

Zatem cykl tworzony w kroku 2 ma długość <= 2*OPT.

Wykonanie skrótów, z nierówności trójkąta, nie wydłuża cyklu.

Poszukiwania strategii aproksymacyjnych

dla danego problemu trudnego obliczeniowo

Możliwe są 3 przypadki:

1. Nie istnieje strategia o powyższych własnościach (tzn. posiadająca skończoną stała c)

Np. TSP (bez ograniczeń). Tw.: Jeśli istnieje taka strategia, to HC jest łatwy, więc P=NP.

2. Istnieje taka strategia, np.

- dla problemu pokrycia wierzchołkowego istnieje prosta strategia o współczynniku 2, i prawdopodobnie nie ma lepszej.

- dla TSP z nierównością trójkąta istnieje strategia o współczynniku 1.5.

3. Istnieje rodzina strategii o współczynnikach dowolnie bliskich 1, np.

- dla problemu plecakowego

- dla TSP, gdy odległości jak w przestrzeni Euklidesowej

Problemy nierozstrzygalne

(jeszcze gorsza sytuacja)

Problem nierozstrzygalny:

Nie posiada algorytmu rozwiązującego go.

tzn. każdy algorytm dla takiego problemu dla niektórych danych albo podaje zły wynik, albo nie kończy działania (zapętla się).

Przykłady problemów nierozstrzygalnych:

1. Dany jest skończony zestaw wzorów płytek. Czy dla dowolnej powierzchni istnieje kolekcja płytek o takich wzorach, którą można pokryć te powierzchnię (płytki musza się stykać jednakowymi krawędziami - uogólnienie domina)

2. Problem stopu - czy dany program na zadanym zestawie danych wejściowych nie zapętli się

3. Równoważność programów: czy dane dwa dowolne programy realizują taką samą funkcję

4. Równania diofantyczne (10 problem Hilberta: dane równanie w postaci wielomianu wielu zmiennych o współczynnikach całkowitych; pytanie: czy ma ono rozwiązanie całkowitoliczbowe)

5. Również pewne problemy przetwarzania tekstów (problem odpowiedniości Posta) oraz z logiki (problemy istnienia dowodów prawdziwości formuł logicznych).

8

---